抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >
image

1.1 二分查找, while l <= r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1

l, r = 0, len(nums) - 1

while l <= r:
mid = (r - l)//2 + l

if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
else:
return mid

return -1

34. 在排序数组中查找元素的第一个和最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:

if not nums:
return [-1, -1]

def binSearch(nums, t, flag):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] > t:
r = mid - 1
elif nums[mid] < t:
l = mid + 1
else:
if flag == "L":
r = mid - 1
else:
l = mid + 1

if flag == 'L' and r + 1 < len(nums) and nums[r + 1] == t:
return r + 1
if flag == 'R' and l - 1 >= 0 and nums[l - 1] == t:
return l - 1
return -1

return [binSearch(nums=nums, t=target, flag='L'), binSearch(nums=nums, t=target, flag='R')]

88. 合并两个有序数组 - 逆向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
"""
Do not return anything, modify A in-place instead.
"""
pa, pb = m-1, n-1
tail = m+n-1

while not (pa == -1 and pb == -1):
if pa == -1:
A[tail] = B[pb]
pb -= 1
elif pb == -1:
A[tail] = A[pa]
pa -= 1
elif A[pa] > B[pb]:
A[tail] = A[pa]
pa -= 1
else:
A[tail] = B[pb]
pb -= 1
tail -= 1

return A[:]

15. 3Sum - for for while , second_ix & third_ix 两边夹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()

# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合,随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])

return ans

11. Container With Most Water 双指针 - 移动 l 和 r 较小的一方才可能增加 area

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
area = 0
while l < r:
area = max(area, min(height[l], height[r]) * (r-l))
if height[l] < height[r]:
l += 1
else:
r -= 1
return area

2. DFS / Stack

2.1 字符串解码 “3[a2[c]]” == “accacc”, stack == [(3, ""), (2,"a")]

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = "", 0
elif c == ']':
cur_multi, last_res = stack.pop()
res = last_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res

215. 数组中的第K个最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from heapq import heapify, heappush, heappop 
# python中的heap是小根堆: heapify(hp) , heappop(hp), heappush(hp, v)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
if k == 0 or k > n:
return []

hp = nums[:k]

heapify(hp)

for i in range(k, n):
v = nums[i]
if v > hp[0]:
heappop(hp)
heappush(hp, v)

return hp[0]

3. dynamic programming

Using dynamic programming to solve problems is generally 3 steps:

  1. state
  2. Find the state transition equation
  3. Boundary processing

When analyzing the state of the problem, don’t analyze the whole, just analyze the last stage! Because dynamic programming problems are divided into multiple stages, the state representation of each stage is the same, and our final answer is in the last stage.

3.1

爬楼梯 climbing-stairs , ✔️ 新建{}or[] ,滚动数组

1
2
3
4
5
6
7
8
class Solution:
def climbStairs(self, n: int) -> int:
dp = {}
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
No. dynamic programming Flag
no-gd 31. n个骰子的点数 dp[i][j] ,表示投掷完 i 枚骰子后,点数 j 的出现次数 ✔️
  Summary 20 dynamic programming
(4.1) DP表示状态
easy Climbing Stairs , 新建{}or[] ,滚动数组
2. 连续子数组的最大和
addition 63. 多少种 不同路径 II, store = [[0]*n for i in range(m)] 二维初始化

addition
Edit Distance/编辑距离【word1 转换成 word2】
   1. dp = [ [0] * (m + 1) for _ in range(n + 1)]
   2. dp[i][j] = min(A,B,C)

✔️❎
addition 5. Longest Palindromic Substring/最长回文子串
1. 枚举子串的长度 l+1,从小问题到大问题
2. 枚举子串的起始位置 i, j=i+l 子串结束位置, dp[i][j] = (dp[i+1][j-1] and s[i]==s[j])
✔️❎
good 把数字翻译成字符串 Fib ✔️❎
addition Leetcode 64. Minimum Path Sum, 最小路径和 grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
addition 115. Distinct Subsequences I Hard
addition 940. 不同的子序列 II Hard
addition Interleaving String/交错字符串 Hard

4. sliding window & hash

No. Question Flag
(6). sliding Window
  65. 最长不含重复字符的子字符串 滑动窗口 ✔️❎
  14. 和为s的连续正数序列    [sliding window]

input:target = 9
output:[[2,3,4],[4,5]]
✔️❎
(7). 模拟
  21. 圆圈中最后剩下的数字

1. 当数到最后一个结点不足m个时,需要跳到第一个结点继续数
2. 每轮都是上一轮被删结点的下一个结点开始数 m 个
3. 寻找 f(n,m) 与 f(n-1,m) 关系
4. A: f(n,m)=(m+x)%n
5. Python 深度不够手动设置 sys.setrecursionlimit(100000)
东大 Lucien 题解,讲得最清楚的那个。官方讲解有误




✔️❎
  35. 顺时针打印矩阵 left, right, top, bottom = 0, columns - 1, 0, rows - 1 ✔️❎
  56. 把数组排成最小的数, sorted vs sort, strs.sort(key=cmp_to_key(sort_rule)) ✔️❎
  70. 把字符串转换成整数
     int_max, int_min, bndry = 231-1, -231, 2**31//10
     bndry=2147483647//10=214748364 ,则以下两种情况越界
     res > bndry or res == bndry and c >’7’
✔️❎

5. linkedList

No. Question Flag
(3). linkedList
  7. 从尾到头打印链表:
reversePrint(head.next) + [head.val]
  8. 反转链表 pre, cur = head, head.next   pre.next = None   (循环版 双指针)
image
  10. 合并两个排序的链表    [Recursion]
p.next = self.mergeTwoLists(l1.next, l2)
addition 旋转单链表 (F1. 环 F2. 走n-k%n 断开)
举例: 给定 1->2->3->4->5->6->NULL, K=3
则4->5->6->1->2->3->NULL
addition 92. 翻转部分单链表 reverse(head: ListNode, tail: ListNode)
举例:1->2->3->4->5->null, from = 2, to = 4 结果:1->4->3->2->5->null
addition 链表划分, 描述: 给定一个单链表和数值x,划分链表使得小于x的节点排在大于等于x的节点之前
addition 82. 删除排序链表中的重复元素 II 链表1->2->3->3->4->4->5 处理后为 1->2->5.
addition 输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912

6. stack

No. Question Flag
(2). Stack
  394. 字符串解码 [a]2[bc]
  28. 包含min函数的栈
  29. 最小的k个数【堆排的逆向】 heapq.heappop(hp),heapq.heappush(hp, -arr[i]) ✔️❎
  36. 滑动窗口的最大值 (同理于包含 min 函数的栈) deque.popleft(),双端队列+单调 ✔️❎
  59 II. 队列的最大值 , 维护个单调的deque
   import queue, queue.deque(), queue.Queue(), deq[0], deq[-1]
✔️❎
(5). DFS / BFS
  66. 矩阵中的路径 , 经典好题: 深搜+回溯 def dfs(i, j, k): ✔️❎
  61. 机器人的运动范围 bfs good
   from queue import Queue, q.get() q.pup()
✔️❎

7. string

8. Tree 剑指

No. Question Flag
easy
(1). Tree
  1.1 平衡二叉树
abs(maxHigh(root.left) - maxHigh(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
  1.2 对称的二叉树
return root == None or isSymmetricHelper(root.left, root.right)
  1.3 二叉树的镜像递归+swap后
root.left = self.mirrorTree(root.right)
root.left = self.mirrorTree(root.right)
root.left = right;root.right = left
  1.4 二叉搜索树的第k大节点    [中序遍历 倒序, 右-中-左] ✔️❎
good 1.5 (两个节点)二叉树的最近公共祖先    [Recursion] 后序遍历+路径回溯 ✔️❎
good 1.6 (两个节点)二叉搜索树的最近公共祖先    Recursion + 剪枝 ✔️❎
good 1.7 二叉树中和为某一值的路径 递归回溯 ✔❎️
  1.8 二叉搜索树的后序遍历序列
  1.9 二叉搜索树与双向链表
image
additional 求二叉树第K层的节点个数 [Recursion] ,root != None and k==1,返回1
f(root.left, k-1) + f(root.right, k-1)
additional 求二叉树第K层的叶子节点个数 [Recursion]
if(k==1 and root.left and root.right is null) return 1;
✔️❎
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class Solution:
def isBalanced(self, root: TreeNode) -> bool:
def maxHigh(root):
if root == None:
return 0
return max(maxHigh(root.left), maxHigh(root.right)) + 1

if root == None:
return True
return abs(maxHigh(root.left) - maxHigh(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)