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

本页面需要浏览器支持(启用)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. DP

No. dynamic programming Flag
no-gd 31. n个骰子的点数 dp[i][j] ,表示投掷完 i 枚骰子后,点数 j 的出现次数 ✔️
  Summary 20 dynamic programming
(4.1) DP表示状态
easy 1. 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 对称的二叉树
  1.3 二叉树的镜像: root.left = self.mirrorTree(root.right) swap后+递归
  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
17
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)