| 3.1 |
找出 0~n-1 中任意一个重复的数字 |
0 1 2 3 4 5 6
--------------------
p
(2) 3 (1) 0 2 5 3
p
(1) (3) 2 0 2 5 3
p
(3) 1 2 (0) 2 5 3
p
0 1 (2) 3 (2) 5 3
|
for i in 0..len:
while i != A[i]:
if A[i] == A[A[i]]:
return A[i]
swap(A[i], A[A[i]])
|
| 3.2 |
不修改输入找出 1~n 中任意一个重复的数字 |
4 3 5 2 3 2 6 7
range [1, 7]
count 8
range [1, 4][5,7]
count 5 3
range [1,2][3, 4]
count 2 3
range [3][4]
count 2 1
|
while low <= high:
middle = low + (high - low) // 2
if low == high:
...
low, high = low, middle if ... else middle + 1, high
|
| 4 |
“二维数组中的查找” |
7
(0,3) (0,1)
A[:][:] A[:][:2]
[1 (2)| 8 9] [1 2 ]
[2 4 | 9 12] [2 4 ]
[4 7 |10 13] [4 (7)]
[6 8 |11 15] [6 8 ]
|
|
| 5.2 |
从后往前合并排序数组 |
|
|
| 6 |
从尾到头打印链表 |
|
栈 |
| 7 |
前序+中序重建二叉树 |
Pre-order:
[1] 2 4 7 | 3 5 6 8
[2] 4 7
[4] 7
[3] 5 | 6 8
[6] 8
In-order:
4 7 2 [1] 5 3 8 6
4 7 [2]
[4] 7
5 [3] 8 6
8 [6]
|
construct(preorder, inorder):
if length == 1:
return Node
root.left = construct(child_preorder, child_inorder)
root.right = construct(child_preorder, child_inorder)
return root
|
| 8 |
找出二叉树中序遍历序列的下一个节点 |
|
中序线索二叉树 |
| 9.1 |
“用两个栈实现队列” |
In Out
[a b c], []
[], [c b] pop() -> a
[], [c] pop() -> b
[d e], [] pop() -> c
[], [e] pop() -> d
|
if out.length == 0:
while in.length > 0:
out.push(in.pop())
return out.pop()
|
| 9.2 |
“用两个队列实现一个栈” |
< <, < a b (c)<
< a (b)<, < < pop() -> c
< a <, < < pop() -> b
< a (d)< push(d)
< a <, < < pop() -> d
|
|
| 10.1 |
斐波那契数列 |
|
公式 |
| 10.2 |
青蛙跳台阶，一次1级或2级 |
|
f(n) = f(n-1) + f(n-2), 斐波那契数列 |
| 10.3 |
青蛙跳台阶，一次 1~n 级 |
n=1, a[1]=1
n=2, a[2]=2
n=3, a[3]=4
...
|
数学归纳法， f(n) = 2**(n-1) |
| 10.4 |
盖瓷砖 |
0 1 2 3 4 5 6 7
|*| | | | | | | |
|*| | | | | | | |
0 1 2 3 4 5 6 7
|*|*| | | | | | |
| | | | | | | | |
|
f(8) = f(7) + f(6), 斐波那契数列 |
| 11 |
“旋转数组的最小数字” |
0 1 2 3 4
------------
3 4 [5] 1 2 3<5>2, L = mid + 1
[1] 2 3>1<2, R = mid
[1]
0 1 2 3 4 5 6
----------------
1 2 0 [1] 1 1 1 1==1==1, ?
2 0 [1] 1 1 1 2>1==1, R = mid
2 [0] 1 2>0<1, R = mid
[2] 0 2==2>1, L = mid + 1
[0]
0 1 2 3 4 5
---------------
1 1 [1] 2 0 1 1==1==1, ?
2 [0] 1 2>0<1, R = mid
[2] 0 2==2>1, L = mid + 1
[0]
|
while numbers[left] >= numbers[right]:
if left + 1 == right:
return numbers[right]
middle = (left + right) // 2
if numbers[left] == numbers[middle] and numbers[middle] == numbers[right]:
???
|
| 12 |
“矩阵中的路径” |
a [b] t g
c [f][c] s
j d [e] h
|
DFS |
| 13 |
“机器人的运动范围” |
|
DFS/BFS |
| 14 |
“剪绳子” |
l = 0, a[0] = 0
l = 1, a[1] = 1
l = 2, a[2] = 2
l = 3, a[3] = 3
l = 4, a[4] = max(a[3]*a[1], a[2]*a[2]) = 4
l = 5, a[5] = max(a[4]*a[1], a[3]*a[2]) = 6
l = 6, a[6] = max(a[5]*a[1], a[4]*a[2], a[3]*a[3]) = 9
|
2和3很特殊，见下 |
|
数论题。“当n>=5时，我们尽可能多地剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两段长度为2的绳子（或不剪）。” |
| 15.1 |
“二进制中1的个数” |
n & (n-1)
1111 & 1110 = 1110 1
1110 & 1101 = 1100 2
1100 & 1001 = 1000 3
1000 & 0111 = 0 4
|
|
| 15.2 |
“判断一个整数是不是2的整数次方” |
|
|
| 15.3 |
Diff 整数 m 和 n 的二进制位 |
|
异或中1的位数 |
| 16 |
实现pow() |
|
快速幂 |
| 17 |
输出所有的 n 位数 |
|
Arbitrary integer |
[0-9][...
0[0-9][...
09[0-9]
|
itertools.product()
|
| 18.1 |
篡改链表 |
|
|
| 18.2 |
链表消消乐 |
None * N
[1]->[2]->[3]->[3]->[4]->[4]->[4]->[5]
HT
[] (append)
3 * N
[3]->[3]->[4]->[4]->[4]->[5]
H T
[]->[1]->[2] (no append)
3 * N
[3]->[3]->[4]->[4]->[4]->[5]
H T
[]->[1]->[2] (no append)
4 * N
[4]->[4]->[4]->[5]
H T
[]->[1]->[2] (no append)
None * N
[5]
H T
[]->[1]->[2] (append)
H T
[]->[1]->[2]->[5]
|
first, second = None, head
while second:
tail = second.next
if tail and second.value == tail.value:
v = second.value
to_delete = second
while to_delete and to_delete.value == v:
tail = to_delete.next
to_delete = tail
if first:
first.next = tail
else:
new_head = tail
second = tail
else:
first, second = second, tail
|
| 19 |
实现正则引擎 |
|
|
| 20 |
Parse string to number |
|
|
| 21 |
调整数组中数字的顺序使奇数位于前半部分，偶数位于后半部分 |
p q
1 2 3 4 5
q p
1 5 3 4 2
|
2 way partition
left, right = 0, len(arr) - 1
while left < right:
while left < right and arr[left] & 1 == 1:
left += 1
while left < right and arr[right] & 1 == 0:
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
|
| 22.1 |
“链表中倒数第k个节点” |
3
[1]->[2]->[3]->[4]->[5]->[6]
R
[1]->[2]->[3]->[4]->[5]->[6]
L R
[1]->[2]->[3]->[4]->[5]->[6]
L R
|
second = head
for i in 0, 1, ... k-2:
if second.next:
second = second.next
else:
return None
first = head
while second.next:
first, second = first.next, second.next
|
| 22.2 |
“求链表的中间节点” |
Odd:
[1]->[2]->[3]->[4]->[5]
p,q
p q
p q
Even:
[1]->[2]->[3]->[4]->[5]->[6]
p,q
p q
p q
p q
|
|
| 23 |
“链表中环的入口节点” |
t h
[1]->[2]->[3]->[4]
| |
[6]<-[5]
t
[1]->[2]->[3]->[4]
| |
[6]<-[5] h
h t
[1]->[2]->[3]->[4]
| |
[6]<-[5]
[1]->[2]->[3]->[4]
| |
[6]<-[5] t,h
t
[1]->[2]->[3]->[4]
| |
[6]<-[5] h
t
[1]->[2]->[3]->[4]
| |
h [6]<-[5]
t,h
[1]->[2]->[3]->[4]
| |
[6]<-[5]
|
Floyd's tortoise and hare
reunion(head):
slow, fast = head, head.next
while slow and fast:
if slow == fast:
return slow
slow = slow.next
fast = fast.next
if fast:
fast = fast.next
return None
circle_length(any_point):
length = 1
point = any_point.next
while point != any_point:
length += 1
point = point.next
return length
meetingPoint = reunion(head)
// ----------------------------
L = circle_length(meetingPoint)
fast = head
for _ in 0, 1, ... L-1:
fast = fast.next
slow = head
while fast != slow:
slow, fast = slow.next, fast.next
|
| 24 |
“反转链表” |
P * N
[] [a]->[b]->...->[h]->[i]->[j]->...
L1 L2
P * N
[]<-[a]<-[b] ...->[h]->[i]->[j]->...
L1 L2
P * N
[]<-[a]<-[b]<-...<-[h]<-[i] [j]->...
L1 L2 R1 R2
Special case: P * N
[]<-[a]<-[b]<-...<-[h]<-[i]
R1 R2
|
first, second = None, head
while second:
third = second.next
if third:
new_head = second
second.next = first
first, second = second, third
|
| 25 |
“合并两个排序的链表” |
* N
[3]->[5]->[7]
* N
[2]->[4]->[6]->[8]
H T
[]->[1]
|
|
| 26 |
“树的子结构” |
|
find + check |
| 27 |
“二叉树的镜像” |
8 8
6 10 10 6
5 7 9 11 11 9 7 5
8
10 6
9 11 5 7
8
10 6
11 9 7 5
|
|
| 28 |
二叉树是否对称 |
|
|
| 29 |
顺时针打印矩阵 |
A[:][:], →, x0 += 1
1 2 3 4
----------
[1] 5 6 7 8
[2] 9 10 11 12
[3] 13 14 15 16
[0 1 2 3]
A[1:][:], ↓, y1 -= 1
[0 1 2]
[1] 5 6 7 | 8
[2] 9 10 11 |12
[3] 13 14 15 |16
A[1:][:3], ←, x1 -= 1
[0 1 2]
[1] 5 6 7
[2] 9 10 11
--------
13 14 15
A[1:3][:3], ↑, y0 += 1
[1 2]
5 | 6 7 [1]
9 |10 11 [2]
A[1:3][1:3], →, x0 += 1
6 7
-----
[2] 10 11
[1 2]
A[2:3][1:3], ↓, y1 -= 1
[1]
[2] 10 | 11
A[2:3][1:2], ←, x1 -= 1
[1]
[2] 10
A[2:2][1:2]
|
round = 0
while round*2 < total_columns and round*2 < total_rows:
col_end, row_end = total_columns-1-round, total_rows-1-round
// →
for i in round, round+1, ..., col_end:
print(matrix[round][i])
// ↓
for i in round+1, round+2, ..., row_end:
print(matrix[i][col_end])
// ←
if round < row_end:
for i in col_end-1, col_end-2, ..., round:
print(matrix[row_end][i])
// ↑
if round < col_end:
for i in row_end-1, row_end-2, ..., round+1:
print(matrix[i][round])
|
| 30 |
实现栈的min() |
Data Min
3 3
3 4 3 3
3 4 2 3 3 2
3 4 2 1 3 3 2 1
3 4 2 3 3 2
3 4 3 3
3 4 0 3 3 0
|
|
| 31 |
“栈的压入、弹出序列” |
1,2,3,4,5
4,5,3,2,1 4,3,5,1,2
[1,2,3][5] -> 4
[1,2,3][] -> 5
[1,2][] -> 3
[1][] -> 2
[][] -> 1
[1,2,3][5] -> 4
[1,2][5] -> 3
[1,2][] -> 5
[1,2][] -> 1 X
|
|
| 32 |
二叉树 层序遍历 |
|
BFS |
| 33 |
BST 后序遍历序列 |
[5 7 6][9 11 10][8]
[5][7][6]
[9][11][10]
7 4 6 [5]
X
|
|
| 34 |
二叉树路径和 |
[10]
[5] [12]
[4][7] 22
19 22
|
先序遍历 |
| 35 |
度为2的链表的复制 |
|
|
| 36 |
BST 转双向链表 |
|
中序线索二叉树 |
| 37 |
序列化二叉树 |
Deserialize:
1 2 4 $ $ $ 3 5 $ $ 6 $ $
(2 3 )
(4 $) (5 6 )
($ $) ($ $) ($ $)
def traverse():
root = dq.popleft()
if root == '$':
return None
root = Node(root)
root.left = traverse()
root.right = traverse()
return root |
先序遍历 |
| 38.1 |
“字符串的排列” |
a,b,c,d
[a|b,c,d]
a[b|c,d]
ab[c|d]
abc[d]
ab[d|c]
abd[c]
a[c|b,d]
ac[b|d]
acb[d]
ac[d|b]
acd[b]
a[d|c,b]
ad[c|b]
adc[b]
ad[b|c]
adb[c]
[b|a,c,d]
...
b[d|c,a]
...
bd[a|c]
bda[c]
[c|b,a,d]
...
c[d|a,b]
...
cd[b|a]
cdb[a]
[d|b,c,a]
...
d[a|c,b]
...
da[b|c]
dab[c]
|
itertools.permutations() |
| 38.2 |
“字符串的组合” |
a,b,c,d
0 0 0 0
0 0 0 1
...
1 1 1 1
Lexicographically ordered:
l = 1, a, b, c, d
l = 2, a[b,c,d] ab, ac, ad
b[c,d] bc, bd
c[d] cd
d[] X
l = 3, ab[c,d] abc, abd
ac[d], bc[d] acd, bcd
ad[], bd[], cd[] X
l = 4, abcd
|
itertools.combinations() |
| 39 |
“数组中出现次数超过一半的数字” |
|
Boyer–Moore majority vote algorithm |
| 40 |
“最小的k个数” |
Top 4
while p < K:
K p
[4 5 1 6 2 7 3][8]
4 5 1 6 2 7 [3]
2 1 5 6 4 7 [3]
p |
[2 1][3][6 4 7 5]
6 4 7 [5]
4 6 7 [5]
| p
[4][5][7, 6]
|
Partial sorting |
|
heapq |
| 41 |
数据流中位数 |
|
类AVL树 |
When balanced:
small large
[1 2 4] [6 8 9]
Push to small: [1 2 4 7] [6 8 9]
Pop to large: [1 2 4] [6 7 8 9]
When unbalanced:
small large
[1 2 4] [6 7 8 9]
Push to large: [1 2 4] [3 6 7 8 9]
Pop to small: [1 2 3 4] [6 7 8 9]
|
LeetCode 295 |
| 42 |
“连续子数组的最大和” |
1 -2 3 10 -4 7 2 -5
1 -2 [3] 10 -4 7 2 -5 Restart
1 [-1] 2 [13] [9] [16] [18] [13] 累加
|
动态规划 |
| 43 |
“1~n整数中1出现的次数” |
|
|
| 44 |
求0123456789101112131415...中任意位数字 |
+10
0 ... 9
|0|...|9|
0 + 9 = 9
0 + 9*1 = 9
+180
1 0 ... 9 9
|10|11|...|188|189|
10 + 89 = 99
10 + 89*2 = 188
+2700
1 0 0 ... 9 9 9
|190|191|192|...|2887|2888|2889|
100 + 899 = 999
190 + 899*3 = 2887
+36000
1 0 0 0 ... 9 9 9 9
|2890|2891|2892|2893|...|38886|38887|38888|38889|
1000 + 8999 = 9999
2890 + 8999*4 = 38886
1001 = 190 + 811 = 190 + 270*3 + 1
|0|1|2|
100 + 270 = 3 7 0
|
|
| 45 |
字符串拼接排成最小的数 |
def cmpkey(x, y):
if y + x > x + y:
return 1
elif y + x < x + y:
return -1
else:
return 0
key=functools.cmp_to_key(cmpkey)
key=functools.cmp_to_key(
lambda x, y: int(y + x) - int(x + y)
) |
LeetCode 179 |
| 46 |
字符串分解 |
12258 ('0', '1', ..., '25')
rtl:
8 1 dp['8'] = 1
58 '5'|dp['8'] => 1 dp['58'] = 1
258 '2'|dp['58'] => 1,
'25'|dp['8'] => 1 dp['258'] = 2
2258 '2'|dp['258'] => 2,
'22'|dp['58'] => 1 dp['2258'] = 3
12258 '1'|dp['2258'] => 3,
'12'|dp['258'] => 2 dp['12258'] = 5
ltr:
1 1 dp['1'] = 1
12 dp['1']|'2' => 1
|'12' dp['12'] = 2
122 dp['12']|'2' => 2,
dp['1']|'22' => 1 dp['122'] = 3
1225 dp['122']|'5' => 3,
dp['12']|'25' => 2 dp['1225'] = 5
12258 dp['1225']|'8' => 5 dp['12258'] = 5
|
|
| 47 |
拿礼物 |
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
1←11←14←22
↑
13←15←24←30
↑ ↑
18←25←29 41
↑ ↑
21 32←48←53
dp: [18][25][24][30]
24 30
18 25 (29)
dp: [18][25][29][30]
30
18 25 29 (41)
dp: [18][25][29][41]
|
Follow-up: LeetCode 741. Cherry Pickup |
| 48 |
“最长不含重复字符的子字符串” |
a r a b c a c f r
0
{a} 1
{a,r} 2
1
{r,a} 2
{r,a,b} 3
{r,a,b,c} 4
3
{b,c,a} 3
5
{a,c} 2
{a,c,f} 3
{a,c,f,r} 4
|
|
| 49 |
“丑数” |
2 3 4 5
x2 [4 6 ✓
x3 [6
x5 [10
2 3 4 5 6
x2 [8 ✓
x3 [6 9
x5 [10
2 3 4 5 6 -8-
x2 [10
x3 [9 ✓
x5 [10
2 3 4 5 6 8 9
x2 [10 ✓
x3 [12
x5 [10
2 3 4 5 6 8 9 10
x2 [12 ✓
x3 [12
x5 [15
2 3 4 5 6 8 9 10 12
x2 [16
x3 [15 ✓
x5 [15
|
|
| 50.1 |
“字符串中第一个只出现一次的字符” |
0 1 2 3 4 5 6 7 8
a b a c c d e f f
a: [0, 2]
b: [1, 1]
c: [3, 2]
d: [5, 1]
e: [6, 1]
f: [7, 2]
|
|
| 50.2 |
从字符串中删除字符 |
|
if c in set(s) |
| 50.3 |
字符串去重 |
|
|
| 50.4 |
Anagram |
set('silent') == set('listen')
set('evil') == set('live')
|
|
| 50.5 |
“字符流中第一个只出现一次的字符” |
g o o g l e
g:0
g:0, o:1
g:0, o:-1
g:-1, o:-1
|
collections.OrderedDict |
| 51 |
“数组中的逆序对” |
7 5 6 4
[7][5] [6][4]
+1*1 +1*1
[5,7] [4,6]
[5,7] [6] [4] +1*2 (5,4), (7,4)
[7] [6] [4,5]
[7] [] [4,5,6] +1*1 (7,6)
[4,5,6,7]
|
归并排序 |
| 52 |
“两个链表的第一个公共节点” |
p1
[1]->[2]->[3]
\
[6]->[7]
/
[4]->[5]
p2
|
|
| 53.1 |
实现 bisect_left, bisect_right |
|
|
| 53.2 |
[0, ..., n-1] 中缺失的一个数字 |
[0, ..., m-1, m+1, ..., n-1]
= >
0 m-1, m n-2
|
|
| 53.3 |
找出数组中任意一个数值等于其下标的元素 |
[-3,-1,1,3,5]
< = >
0 1 2 3 4
|
|
| 54 |
“二叉搜索树的第k大节点” |
k = 3
5
[2] / \
3 7
/ \ / \
2 4 6 8
[1] [3]
|
中序遍历 |
| 55.1 |
“二叉树的深度” |
(4)
1
(3) / \ (2)
2 3
/ \ \
4 5 6 (1)
(1) / (2)
7
(1)
|
求最短路径有陷阱 |
| 55.2 |
“平衡二叉树” |
(4,T)
1
(3,T) / \ (2,T)
2 3
/ \ \
4 5 6 (1,T)
(1,T) / (2,T)
7
(1,T)
|
|
| 56.1 |
一个整数数组里只有两个数字只出现一次，其它数字都出现了两次 |
[2,4,3,6,3,2,5,5]
2^4^3^6^3^2^5^5 = 0010
__1_ __0_
[2,3,6,3,2] [4,5,5]
2^3^6^3^2 = 6 4^5^5 = 4
|
|
| 56.2 |
一个数组中只有一个数字只出现一次，其它数字都出现了三次 |
|
二进制的每一位加起来，能被3整除的位，那个数的对应位是0，否则是1 |
| 57.1 |
“和为s的两个数字” |
s = 15
[1,2,4,7,11,15]
1 15 = 16
1 11 = 12
2 11 = 13
4 11 = 15
|
|
| 57.2 |
所有和为s的连续正整数序列 |
n = 2: 7.5 7.5
7 8
n = 3: 5 5 5
4 5 6
n = 4: 3.25 3.25 3.25 3.25
n = 5: 3 3 3 3 3
1 2 3 4 5
|
|
| 58.1 |
“翻转单词顺序” |
"I am a student." s
".tneduts a ma I" reversed s
"student. a am I"
"student. a ma I"
|
|
| 58.2 |
“左旋转字符串” |
2
"abcdefg" s
"gfedcba" reversed s
"cdefgba"
"cdefgab"
|
|
| 59.1 |
“滑动窗口的最大值” |
max queue: [large, >= medium, >= small]
[2 3 4] 2 6 2 5 1
4@2
2 [3 4 2] 6 2 5 1
4@2, 2@3
2 3 [4 2 6] 2 5 1
6@4
2 3 4 [2 6 2] 5 1
6@4, 2@5
2 3 4 2 [6 2 5] 1
6@4, 5@6
2 3 4 2 6 [2 5 1]
5@6, 1@7
|
|
| 59.2 |
实现队列的 max() |
|
同理 |
| 60 |
n个骰子点数之和的概率分布 |
n <= s <= 6n
1 2 3 4 5 6 ... 6n
n = 1: [1,1,1,1,1,1, ..., 0] frequency
n = 2: a2[i] = a1[i-1] + a1[i-2] + a1[i-3]
+ a1[i-4] + a1[i-5] + a1[i-6]
...
|
|
| 61 |
判断随机抽的5张扑克牌是不是一个顺子 |
|
|
| 62 |
约瑟夫环 |
m = 3
n = 1, f(1) = 0
n > 1, f(n) = (f(n-1) + 3) % n
n = 2, f(2) = (f(1) + 3) % 2 = 1
0
1
n = 3, f(3) = (f(2) + 3) % 3 = 1
0
1
2
n = 4, f(4) = (f(3) + 3) % 4 = 0
0
1
3 2
n = 5, f(5) = (f(4) + 3) % 5 = 3
0
4 1
3 2
|
|
| 63 |
买卖某股票一次可能获得的最大利润 |
[9,11,8,5,7,12,16,14]
0 2 0 0 2 7 11 9
9 8 5 (min)
|
|
| 64 |
利用构造函数/虚函数/函数指针/模板类型求 1+2+...+n |
|
|
| 65.1 |
实现加法器 |
数位加
^ 0, 0 => 0
1, 1 => 0
1, 0 => 1
进位
& 0, 0 => 0
1, 0 => 0
1, 1 => 1
a 00111
b 11111
^ 11000
& 00111 01110
^ 10110
& 01000 10000
^ 00110
& 10000 100000
^ 100110
& 000000 000000
a + b = 100110
|
|
| 65.2 |
交换两个变量的值 |
a = a + b sum of a, b
b = a - b get a using b
a = a - b get b using a
a = a ^ b diff of a, b
b = a ^ b get a using b
a = a ^ b get b using a
|
|
| 66 |
“构建乘积数组” |
B0 C0 [1][A1,A2,...,An-2,An-1] Dn-1
B1 C1 [A0] [A2,...,An-2,An-1] Dn-2
B2 C2 [A0,A1] [...An-2,An-1] Dn-3
...
Bn-2 Cn-2 [A0,A1,...,An-3] [An-1] D1
Bn-1 Cn-1 [A0,A1,...,An-3,An-2][1] D0
|
|
| 67 |
实现 atoi() |
|
|
| 68.1 |
二叉搜索树中两个节点的最底公共祖先 |
8
/ \ 3 < 4 < 6
4 9 4 [4]
/ \ / \ /
2 6 [6]
/ \ / \ \ / /
1 3 5 7 [3] [1]
|
|
| 68.2 |
树中两个节点的最底公共祖先 |
A
(2) / \
B C
(1) / \
D E (1)
/ \ /|\
[F] G [H]I J
(1) (1)
|
|
