3/17 - leetcode - 1963
1、遍历字符串，专注于右括号的匹配
2、遍历过程中，遇到右括号时有两种情况：
2.1、没有左括号匹配，这意味着必须要做出交换，以便腾出一个左括号给匹配到的右括号，则交换加入一个左括号，记作left += 1，答案也要加一，记作 ans += 1
2.2、存在左括号匹配，则直接匹配左括号，左括号减一，记作left - 1，不存在交换则答案不变
3、遍历过程中，遇到左括号只需要直接加一即可，记作 left += 1
class Solution:
def minSwaps(self, s: str) -> int:
n = len(s)
ans = 0
left = 0
for i in range(n):
if(s[i] == ']'):
if(left == 0):
left += 1
ans += 1
else:
left -= 1
else:
left += 1
return ans
3/18 - leetcode - 2614
1、静态方法的调用
2、质数的判断 int(sqrt(num)) + 1 需要强制转换，因为sqrt返回的是浮点数
from math import sqrt
from typing import List
class Solution:
@staticmethod
def judge(num: int) -> bool:
if num < 2:
return False
for i in range(2, int(sqrt(num)) + 1):
if num % i == 0:
return False
return True
def diagonalPrime(self, nums: List[List[int]]) -> int:
n = len(nums) # 预存矩阵大小，避免重复计算
ans = 0
for i in range(n):
ans = max(ans, nums[i][i] if self.judge(nums[i][i]) else 0)
ans = max(ans, nums[i][n - i - 1] if self.judge(nums[i][n - i - 1]) else 0)
return ans
3/19 - leetcode - 2610
1、字典的创建与添加操作
2、 Python 不允许在遍历字典时直接删除元素
2.1、将字典的键单独提取转换为list【】对象
2.2、收集需要删除的字典，在循环外修改
class Solution:
def findMatrix(self, nums: List[int]) -> List[List[int]]:
ans = []
dics = {}
n = len(nums)
for i in range(n):
if nums[i] in dics.keys():
dics[nums[i]] += 1
else:
dics.setdefault(nums[i], 1)
while dics :
a = []
for key in list(dics.keys()):
a.append(key)
dics[key] -= 1
if dics[key] == 0:
dics.pop(key)
ans.append(a)
return ans
3/21 - leetcode - 35
二分查找
1、左闭右闭：left = right存在意义
2、左闭右开“left = right不存在意义
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 左开又开区间
n = len(nums)
left = 0
right = n - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return right + 1
3/22 - leetcode - 26 - 27
双指针算法
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
fast = 1
slow = 1
while fast < n :
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
3/24 - leetcode - 977
双指针算法（头尾双指针）
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left = 0
right = n - 1
ans = [ x*0 for x in range(n)]
i = n - 1
while left <= right :
a = nums[left] ** 2
b = nums[right] ** 2
if a < b:
ans[i] = b
right -= 1
i -= 1
else:
ans[i] = a
left += 1
i -= 1
return ans