2023 7月
新题
455. 分发饼干
注意，python的sort函数是从小到大排序
（以及heapq是最小堆）
以及注意 sorted 和 sort 的区别
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
ans = 0
if s == []:
return 0
g.sort()
s.sort()
cur = len(s) - 1
for i in range(len(g) - 1, -1, -1):
if s[cur] >= g[i]:
ans += 1
cur -= 1
if cur == -1:
return ans
return ans
更简单的写法（显然也可从小到大贪心）
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
n = len(g)
i = 0
for x in s:
if i < n and g[i] <= x:
i += 1
return i
链接：https://leetcode.cn/problems/assign-cookies/solutions/2974809/pai-xu-shuang-zhi-zhen-jian-ji-xie-fa-py-ttn8/
17min
103. 二叉树的锯齿形层序遍历
记得每次循环后清空cur
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
ans = []
cur = []
if root == None:
return []
q = deque([(root, 0)])
while q:
node, layer = q.popleft()
cur.append(node.val)
if len(q) == 0 or layer != q[0][1]:
if layer % 2 == 1:
cur.reverse()
ans.append(cur[:])
cur = []
for sub in [node.left, node.right]:
if sub != None:
q.append((sub, layer + 1))
return ans
5min
344. 反转字符串
我的写法
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
for i in range(len(s) // 2):
s[i], s[len(s) - i - 1] = s[len(s) - i - 1], s[i]
但可以更简单
class Solution:
def reverseString(self, s: List[str]) -> None:
for i in range(len(s) // 2):
s[i], s[-i - 1] = s[-i - 1], s[i]
< 1 min
旧题
199. 二叉树的右视图 11min 犯了和第一次做同样的错误，下标0/-1搞错
3. 无重复字符的最长子串 7min 写得稍微比第一次好些
33. 搜索旋转排序数组 30min...但思路比之前清楚了许多...
215. 数组中的第K个最大元素 emm...快速选择写对非常不容易啊
146. LRU 缓存 todo