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
3/25 - leetcode - 209 - 904
1、滑动窗口，关键在于 不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
2、904
2.1、Counter() – 将元素个数计数，并返回一个字典，key为元素，value为元素个数
2.2、enumerate() – 将数组迭代，返回第一个值是下标，第二个值是元素值
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
cnt = Counter()
left = ans = 0
for right, x in enumerate(fruits):
cnt[x] += 1
while len(cnt) > 2:
cnt[fruits[left]] -= 1
if cnt[fruits[left]] == 0:
cnt.pop(fruits[left])
left += 1
ans = max(ans, right - left + 1)
return ans
3/26 - leetcode - 59
螺旋矩阵
for循环的模拟过程，坚持循环不变量的原则。
创建二维数组 ans = [[0] * n for _ in range(n)]
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
ans = [[0] * n for _ in range(n)]
# 起始位置
startx = 0
starty = 0
# 层数
loop = n // 2
# 中间
mid = n // 2
# 计数器
count = 1
for offset in range(1, loop + 1) :
# 从左到右，左闭右开
for i in range(starty, n - offset):
ans[startx][i] = count
count += 1
# 从上到下，左闭右开
for i in range(startx, n - offset):
ans[i][n - offset] = count
count += 1
# 从右到左，左闭右开
for i in range(n - offset, starty, -1):
ans[n-offset][i] = count
count += 1
# 从下到上，左闭右开
for i in range(n - offset, startx, -1):
ans[i][starty] = count
count += 1
startx += 1
starty += 1
# 如果存在中间值就单独赋值
if n % 2 != 0:
ans[mid][mid] = count
return ans
3/26 - 前缀和
注意区间的闭合
3/27 - 还是前缀和
44. 开发商购买土地（第五期模拟笔试）