206. 反转链表
def reverseList(self, head: ListNode) -> ListNode:
prev = NoListNodene
cur = head
while(cur):
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
124. 二叉树中的最大路径和
def maxPathSum(self, root: TreeNode) -> int:
self.res = float("-inf")
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
left = max(left, 0)
right = max(right, 0)
self.res = max(self.res, root.val + left + right)
return root.val + max(left, right)
dfs(root)
return self.res
23. 合并K个升序链表
def mergeKLists(self, lists):
import heapq
head = point = ListNode(0)
heap = []
for l in lists:
while l:
heapq.heappush(heap, l.val)
l = l.next
while heap:
val = heappop(heap)
point.next = ListNode(val)
point = point.next
return head.next
25. K 个一组翻转链表
# 翻转一个子链表，并且返回新的头与尾。反转前的head是反转后的new_tail，反转后的头是prev指针
def reverse(self, head: ListNode, tail: ListNode):
prev = None
cur = head
new_tail = head
while prev != tail:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev, new_tail
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
pre = dummy
while head:
tail = pre
# 查看剩余部分长度是否大于等于 k
for i in range(k):
tail = tail.next
if not tail:
return dummy.next
nex = tail.next
head, tail = self.reverse(head, tail)
# 把子链表重新接回原链表
pre.next = head
tail.next = nex
pre = tail
head = tail.next
return dummy.next
92. 反转链表 II
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverse_linked_list(head: ListNode):
# 也可以使用递归反转一个链表
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
# 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
# 建议写在 for 循环里，语义清晰
for _ in range(left - 1):
pre = pre.next
# 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
right_node = pre
for _ in range(right - left + 1):
right_node = right_node.next
# 第 3 步：切断出一个子链表（截取链表）
left_node = pre.next
curr = right_node.next
# 注意：切断链接
pre.next = None
right_node.next = None
# 第 4 步：同第 206 题，反转链表的子区间
reverse_linked_list(left_node)
# 第 5 步：接回到原来的链表中
pre.next = right_node
left_node.next = curr
return dummy_node.next
786. 第 K 个最小的素数分数
def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
def cmp(x: Tuple[int, int], y: Tuple[int, int]) -> int:
return -1 if x[0] * y[1] < x[1] * y[0] else 1
n = len(arr)
frac = list()
for i in range(n):
for j in range(i + 1, n):
frac.append((arr[i], arr[j]))
frac.sort(key=cmp_to_key(cmp))
return list(frac[k - 1])
42. 接雨水
def trap(self, height: List[int]) -> int:
if not height:
return 0
left_max = [height[0]]
for i in range(1, len(height)):
left_max.append(max(left_max[i-1],height[i]))
right_max = [0]*(len(height)-1) + [height[-1]]
for i in range(len(height)-2, -1, -1):
right_max[i] = max(right_max[i+1],height[i])
res = 0
for i in range(len(height)):
res = res + min(left_max[i],right_max[i] )-height[i]
return res
209. 长度最小的子数组
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left=0
mincount=float('inf')
cursum=0
for right in range(len(nums)):
cursum+=nums[right]
while cursum>=target:
mincount=min(mincount,right-left+1)
cursum=cursum-nums[left]
left+=1
return mincount if mincount!=float('inf') else 0
509. 斐波那契数
def fib(self, n: int) -> int:
res = [0]*(n+1)
if n==0:
return 0
if n==1:
return 1
res[0] = 0
res[1] = 1
for i in range(2, n+1):
res[i] = res[i-1] + res[i-2]
return res[-1]
470. 用 Rand7() 实现 Rand10()
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数
def rand10(self):
num = (rand7()-1)*7 + rand7()
while num>40:
num = (rand7()-1)*7 + rand7() #拒绝采样，重新生成
return num%10 +1
# https://leetcode.cn/problems/implement-rand10-using-rand7/solution/cong-zui-ji-chu-de-jiang-qi-ru-he-zuo-dao-jun-yun-/
329. 矩阵中的最长递增路径
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0
@lru_cache(None)
def dfs(row: int, column: int) -> int:
best = 1
for dx, dy in Solution.DIRS:
newRow, newColumn = row + dx, column + dy
if 0 <= newRow < rows and 0 <= newColumn < columns and matrix[newRow][newColumn] > matrix[row][column]:
best = max(best, dfs(newRow, newColumn) + 1)
return best
ans = 0
rows, columns = len(matrix), len(matrix[0])
for i in range(rows):
for j in range(columns):
ans = max(ans, dfs(i, j))
return ans
560. 和为 K 的子数组
def subarraySum(self, nums: List[int], k: int) -> int:
hashtable = {0:1}
ret = 0
pre_sum = 0
for num in nums:
pre_sum += num
ret += hashtable.get(pre_sum - k, 0)
hashtable[pre_sum] = hashtable.get(pre_sum, 0) + 1
return ret
# 所以判断当前元素与k之间的差值是否是前若干元素总和即可，注意计数时并不都是+1，如果前若干元素总和=nums[j]-k的子数组个数大于1，则要全部加上，因为是不同的子数组。(因为中间可能有一段和为0，座椅可能有多个)
51. N 皇后
剑指 Offer 51. 数组中的逆序对
def reversePairs(self, nums: List[int]) -> int:
count = 0
alist = []
for n in nums:
idx = bisect.bisect(alist, n)
alist.insert(idx, n)
count = count + len(alist)-idx-1
return count
611. 有效三角形的个数
def triangleNumber(self, nums: List[int]) -> int:
res = 0
nums.sort()
for i in range(2, len(nums)):
l, r = 0, i - 1
while l < r:
if nums[l] + nums[r] <= nums[i]:
l += 1
else:
res += r - l
r -= 1
return res
85. 最大矩形
def maximalRectangle(self, matrix: List[List[str]]) -> int:
# time O(mn), space O(n)
if not matrix or not matrix[0]:
return 0
self.res = 0
def helper(arr):
stack = []
for i in range(len(arr)):
while stack and arr[i] < arr[stack[-1]]:
idx = stack.pop()
width = i - stack[-1] - 1
height = arr[idx]
self.res = max(self.res, width * height)
stack.append(i)
r, c = len(matrix), len(matrix[0])
cnts = [0] * (c + 2)
for i in range(r):
for j in range(c):
if matrix[i][j] == '1':
cnts[j + 1] += 1
else:
cnts[j + 1] = 0
helper(cnts)
return self.res
912. 排序数组
def sortArray(self, nums: List[int]) -> List[int]:
def QuickSort(left, right):
if left >= right: return nums
index = random.randint(left, right)
pivot = nums[index]
nums[index], nums[left] = nums[left], nums[index]
i, j = left, right
while i < j:
while i < j and nums[j] > pivot:
j -= 1
nums[i] = nums[j]
while i < j and nums[i] <= pivot:
i += 1
nums[j] = nums[i]
nums[i] = pivot
QuickSort(left, i-1)
QuickSort(i+1, right)
return nums
QuickSort(0, len(nums)-1)
return nums
572. 另一棵树的子树
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
if not s and not t:
return True
if not s or not t:
return False
return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def isSameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)
def canJump(self, nums: List[int]) -> bool:
n, reach = len(nums), 0
for i in range(n):
if i > reach:
return False
reach = max(reach, i + nums[i])
return True
45. 跳跃游戏 II
def jump(self, nums: List[int]) -> int:
n = len(nums)
maxPos, end, step = 0, 0, 0
for i in range(n - 1):
if maxPos < i:
return
maxPos = max(maxPos, i + nums[i])
if i == end: #我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。
end = maxPos
step += 1
return step
887. 鸡蛋掉落
ans = N
# 暴力枚举从第 i 层开始扔，碎了往下试探并少一个鸡蛋，没碎往上试探
for i in range(1, N + 1):
ans = min(ans, max(self.superEggDrop(K - 1, i - 1) + 1, self.superEggDrop(K, N - i) + 1))
return ans
#dp[x][y] 表示 x次操作y个鸡蛋 可以确认多少层,即不管你这个鸡蛋在dp[x][y]及其下面那一层会碎，我们都能查出f。看看dp[m] 怎么由dp[m-1]转换过来。假设dp[m - 1][i - 1] 确定了一个楼层A。那么dp[m - 1][i]表示鸡蛋没碎可以往上再试探的楼层数量
def superEggDrop(self, K: int, N: int) -> int:
dp = [[0] * (K + 1) for _ in range(N + 1)]
m = 0
while dp[m][K] < N:
m += 1
for i in range(1, K + 1):
dp[m][i] = dp[m - 1][i - 1] + dp[m - 1][i] + 1
return m
206. 反转链表
def reverseList(self, head: ListNode) -> ListNode:
prev = None
cur = head
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
92. 反转链表 II
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
def reverse_linked_list(head: ListNode):
# 也可以使用递归反转一个链表
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
dummy_node = ListNode(-1)
dummy_node.next = head
pre = dummy_node
# 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
# 建议写在 for 循环里，语义清晰
for _ in range(left - 1):
pre = pre.next
# 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
right_node = pre
for _ in range(right - left + 1):
right_node = right_node.next
# 第 3 步：切断出一个子链表（截取链表）
left_node = pre.next
curr = right_node.next
# 注意：切断链接
pre.next = None
right_node.next = None
# 第 4 步：同第 206 题，反转链表的子区间
reverse_linked_list(left_node)
# 第 5 步：接回到原来的链表中
pre.next = right_node
left_node.next = curr
return dummy_node.next
def isSymmetric(self, root: TreeNode) -> bool:
# write code here
if not root:
return True
def Traversal(left, right):
if left is None and right is None:#如果是叶节点，直接返回True
return True
#如果左右节点相同，继续判断左-左和右-右，以及左-右和右-左
elif left and right and left.val == right.val:
return Traversal(left.left, right.right) and Traversal(left.right, right.left)
else:
return False
return Traversal(root.left, root.right)
226. 翻转二叉树
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return None
tmp_left = root.left
root.left = self.invertTree(root.right)
root.right = self.invertTree(tmp_left)
return root
295. 数据流的中位数
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.big_heap = []
self.small_heap = []
def addNum(self, num: int) -> None:
if len(self.big_heap) == len(self.small_heap):
heapq.heappush(self.small_heap, -num)
heapq.heappush(self.big_heap, - heapq.heappop(self.small_heap))
else:
heapq.heappush(self.big_heap, num)
heapq.heappush(self.small_heap, - heapq.heappop(self.big_heap))
def findMedian(self) -> float:
if len(self.big_heap) == len(self.small_heap):
return ( self.big_heap[0] - self.small_heap[0]) / 2
else:
return self.big_heap[0]
110. 平衡二叉树
def isBalanced(self, root: TreeNode) -> bool:
def dfs(root):
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
return max(left,right) +1
if not root:
return True
l = dfs(root.left)
r = dfs(root.right)
if abs(l-r)<=1:
return self.isBalanced(root.left) and self.isBalanced(root.right)
else:
return False
