LeetCode 算法题(Easy)
LeetCode 算法题(Medium)
LeetCode 算法题(Hard)
剑指 offer
哈希构造方法:
- 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
- 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法：取关键字平方后的中间几位作为散列地址。
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。
- 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
hash冲突在所难免，解决冲突是一个复杂问题。冲突主要取决于：
- 与散列函数有关，一个好的散列函数的值应尽可能平均分布。
- 与解决冲突的哈希冲突函数有关。
- 与负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。
办. ： - 开放定址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。
- 拉链法：把所有同义词，即hash值相同的记录，用单链表连接起来。
排序
排序算法概览
- 比较排序算法: 冒泡, 选择, 插入, 归并, 堆排, 快排
- 非比较排序算法: 计数, 基数, 桶排
- 稳定性: 7 个常用算法, 3 稳(冒泡, 插入, 归并) 4 不稳 (选择, 希尔, 快排, 堆排)
| 排序算法 | 平均时间复杂度 | 最坏/最好时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n^2)$ / $O(n)$ | $O(1)$ | 稳定 |
| 选择排序 | $O(n^2)$ | $O(n^2)$ / $O(n^2)$ | $O(1)$ | 不稳定 |
| 插入排序 | $O(n^2)$ | $O(n^2)$ / $O(n)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(nlogn)$ | 与步长 $d$ 有关 / $O(nlogn)$ | $O(1)$ | 不稳定 |
| 快速排序 | $O(nlogn)$ | $O(n^2)$ / $O(nlogn)$ | $O(logn) \sim O(n)$ | 不稳定 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ / $O(nlogn)$ | $O(n)$ | 稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ / $O(nlogn)$ | $O(1)$ | 不稳定 |
| 计数排序 | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |
| 基数排序 | $O(d\times (n+r))$ | $O(d\times (n+r))$ | $O(n+r)$ | 稳定 |
| 桶排序 | $O(n+m)$ | $O(n+m)$ | $O(n)$ | 稳定 |
冒泡排序
从后往前, 相邻的数据两两比较, 一趟完成后, 第一个元素为最大/小值
时间复杂度: $O(n^2)$
最好情况: $O(n)$, 当某次遍历没有发生交换, 则说明已经有序
最坏情况: $O(n^2)$, 数组刚好是逆序
空间复杂度: $O(1)$
稳定性: 是稳定的, 主要就是 遇到相等的元素时不要进行交换操作 即可
Python 实现1
2
3
4
5
6
7
8
9
10
11
12
13def bubble_sort(arr):
n = len(arr)
for i in range(n):
early_stop = 1 # 早停标志, 如果某次没有执行冒泡过程, 则说明已经有序
for bubble in range(n-1, i, -1):
if arr[bubble-1] > arr[bubble]: # 递增排序, 为了保证稳定性, 不能用 >=
# if arr[i] < arr[j]: # 递减排序
arr[bubble-1], arr[bubble] = arr[bubble], arr[bubble-1]
early_stop = 0
if early_stop:
break
return arr
print(bubble_sort(arr))
C++ 实现1
2
3
4
5
6
7
8
9
10
11void bubble_sort(vector<int> &input){
for(int i=0; i<input.size(); i++){
for(int bubble = input.size()-1; bubble>i; bubble--){
if(input[bubble-1] < input[bubble] ){ //为了保证排序的稳定性, 这里不要用 <=
int temp = input[bubble];
input[bubble] = input[bubble-1];
input[bubble-1] = temp;
}
}
}
}
冒泡排序的改进: 鸡尾酒排序
冒泡排序是只在一个方向上进行排序, 鸡尾酒排序是从前往后和从后往前交替排序(即先找最大, 再找最小). 在面对大部分元素已经有序的数组时, 鸡尾酒排序的时间复杂度接近于 $O(n)$.
选择(交换)排序
步骤:
- 在未排序序列中找到最小(大)元素, 存放到起始位置;
- 然后再从剩余的序列中继续寻找最小(大)元素, 并将其放到起始位置的下一个位置
- 以此类推, 直到所有元素排序完毕.
时间复杂度: $O(n^2)$
最好情况: $O(n^2)$, 复杂度与序列元素分布形式无关
最坏情况: $O(n^2)$, 复杂度与序列元素分布形式无关
空间复杂度: $O(1)$
稳定性: 选择排序是不稳定的排序算法, 不稳定性发生在最小元素与 A[i] 交换的时刻. 因为选择排序在交换两个元素时, 是不考虑其他元素的相对位置的, 所以, 不管怎么样, 只要发生交换, 就一定会造成不稳定. 但是!!! 如果使用链表或者新开辟一个数组的话, 选择排序也是稳定的, 但实际上这种方法就没有交换的过程, 对于链表来说, 是把节点从链表中拿出来, 组成新的链表, 而不会对原来链表中的元素进行交换. 对于新开辟数组来说, 相当于是用空间换取稳定性, 同样也没有交换过程.
Python 实现1
2
3
4
5
6
7
8
9
10
11
12arr = [random.randint(0, 10) for _ in range(10)]
print(arr)
def select_sort(arr):
n = len(arr)
for i in range(n):
select = i # 记录最值标记
for j in range(i+1, n):
if arr[j] < arr[select]: # 递增排序
select = j # 更新最值标记
arr[i], arr[select] = arr[select], arr[i] # 交换最值和当前的i值
return arr
print(select_sort(arr))
插入排序
将数据分为两个部分, 有序部分和无序部分, 一开始有序部分包含只包含第一个元素, 依次将无序部分的元素插入到有序部分 ( 插入的时间复杂度为 $O(n)$ ), 直到所有元素插入完毕.
插入分为数组插入和链表插入(其实堆排序也算是一种插入排序)
下面的时间和空间复杂度均指 数组直接插入, 对于链表, 时间和空间都是 $O(n)$
时间复杂度: $O(n^2)$
最好情况: $O(n)$, 对于已经有序的序列来说, 每一次插入的复杂度都是 $O(1)$, 共插入 $O(n)$ 次.
最坏情况: $O(n^2)$, 对于逆序的序列来说, 每一次插入的复杂度都是 $O(n)$, 共插入 $O(n)$ 次.
空间复杂度: $O(1)$
稳定性: 只要在插入遇到相等元素时, 将新插入的放在最后, 那么就是稳定的.
插入排序不适合对于数据量比较大的排序应用. 但是, 如果需要排序的数据量很小, 比如量级小于千, 那么插入排序还是一个不错的选择. 插入排序在工业级函数库中也有着广泛的应用, 在 STL 的 sort 算法和 stdlib 的 qsort 算法中, 都将插入排序作为快速排序的补充, 用于少量元素的排序(通常为8个或以下).
步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
- 重复步骤3，直到找到已排序的元素刚好新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
Python 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14arr = [random.randint(0, 10) for _ in range(10)]
print(arr)
def insert_sort(arr):
n = len(arr)
for i in range(1, n):
if arr[i] < arr[i-1]: # 只有当可能需要插入时, 才进行搜索, 否则就是已经有序, 这样最好复杂度可以为 O(n)
for j in range(i):
if arr[i] < arr[j]: # 递增排序, 为了保证稳定性, 不能使用 <=
temp = arr[i]
for k in range(i, j, -1):
arr[i] = arr[i-1]
arr[j] = temp
return arr
print(insert_sort(arr))
二分插入排序:
直接插入在查找插入位置时, 可以采用二分查找的方式(因为已经有序), 这样可以减少查找插入位置时花费的时间.
希尔排序
希尔排序(Shell Sort), 也叫 递减增量排序, 其实质是分组插入排序, 是插入排序中一种更高效的改进版本. 插入排序具有以下两点性质:
- 对于几乎已经排好序的数据操作时, 效率很高, 可以达到线性排序的效率;
- 插入排序在每次往前插入时只能将数据移动一位, 这使得效率较低.
因此, 希尔排序的思想是: - 首先选取一个合适的步长(gap < n)作为间隔, 并将所有元素划分成 gap 个子序列, 每个子序列 内部元素之间的距离都是 gap.
- 分别对每个子序列使用直接插入排序.
- 缩小步长 gap 的值, 重复上面的分组和插入排序过程, 直到 gap = 1 为止.
时间复杂度: $O(nlogn)$
最好情况: $O(n^{1.3})$, 实际中的时间复杂度与 gap 的值和序列元素的分布情况有关.
最坏情况: $O(n^2)$, 当 gap 的值为 1 时, 希尔排序就退化成了插入排序.
空间复杂度: $O(1)$
稳定性: 希尔排序是不稳定的算法, 因此对于相同的两个数, 可以由于分在不同的组中而导致它们的相对顺序发生变化. 比如序列：{ 3, 5, 10, 8, 7, 2, 8, 1, 20, 6 }, h=2时分成两个子序列 { 3, 10, 7, 8, 20 } 和 { 5, 8, 2, 1, 6 }, 未排序之前第二个子序列中的8在前面, 现在对两个子序列进行插入排序, 得到 { 3, 7, 8, 10, 20 } 和 { 1, 2, 5, 6, 8 }, 即 { 3, 1, 7, 2, 8, 5, 10, 6, 20, 8 }, 两个8的相对次序发生了改变.
希尔排序举例:
例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为 5 开始进行排序，我们可以通过将这列表放在有 5 列的表中来更好地描述算法，这样他们就应该看起来是这样：1
2
3
413 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们分别对 每列(一组) 进行排序：1
2
3
410 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时 10 已经移至正确位置了，然后再以 3 为步长进行排序：1
2
3
4
5
610 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：1
2
3
4
5
610 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序（此时就是简单的插入排序了）。
Python 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16arr = [random.randint(0, 15) for _ in range(20)]
print(arr)
def shell_sort(arr):
n = len(arr)
gap = round(n/2) # 初始时 gap 为 n / 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while(j >=gap and arr[j-gap] > temp): # 组内元素间隔为 gap, 进行插入排序
arr[j] = arr[j-gap]
j = j-gap
arr[j] = temp
gap = round(gap/2) # gap 缩小一半
return arr
print(shell_sort(arr))
快速排序
时间复杂度: $O(nlogn)$
最好情况: $O(nlogn)$, 每次选取的基准都是中位数, 这样每次都可以均匀的划分出两个分区, 只需要 $logn$ 次划分就能结束递归, 每次划分(Partition)的复杂度是 $O(n)$, 因此, 时间复杂度为 $O(nlogn)$.
最坏情况: $O(n^2)$, 每次选取的基准都是最大(小)元素, 导致只划分出了一个分区, 这样, 需要 $n-1$ 次划分才能结束递归.
空间复杂度: $O(logn)$, 主要是递归造成的栈空间的使用, 具体复杂度取决于递归的深度, 最坏情况下为 $O(n)$.
稳定性: 快速排序是不稳定的排序算法, 不稳定性发生在于基准元素交换的时刻. 快排在划分两边的元素时, 会直接交换某两个元素的位置, 并且这种交换与其他元素的值没有关系, 因此, 如果刚好有相同元素, 很容易就会破坏稳定性.
简单优化:
快排的期望时间复杂度为 $O(nlogn)$ , 最坏时间复杂度为 $O(n^2)$, 为了避免出现最坏的情况, 可进行如下改进:
- 哨兵元素的选择: 为了使每次划分的数不至于使两边相差过大, 我们可以选择三者取中法选择哨兵, 一般根据首尾元素和中间元素进行选择.
- 小数据量的改进: 递归的快排大概在n<13的时候比插入要慢, 所以我们在n<13的时候可以采用插入排序
- 相同数字的改进, 在存在大量相同数字的时候, 可以用两个指针保存相同数字的信息, 在划分时不用把它们算进去, 划分结束后根据相同数字的个数进行填充(这啥意思?//TODO)
- 递归的优化. 快排有两次递归调用, 我们可以用循环代替后面的一次递归.
空间复杂度: $logn$
对于就地快排来说, 它本身使用的空间是 $O(1)$ 的, 但是快排在 递归调用过程中, 就需要消耗一定的空间来保存哨兵及两端元素的下标, 而对于快排的非递归实现中, 需要借助两个栈来模拟系统对于数组low和high的存储情况(递归中的哨兵下标实际上会作为下一次递归的low或者high), :
- 最优的情况下空间复杂度为: $O(logn)$, 每一次都平分数组
- 最差的情况下空间复杂度为: $O(n)$, 每一次两边都极度失衡 (主要与进行迭代的次数有关, 迭代次数多了, 占用的内存就多了)
注意: 最好写出对输入的low和high进行越界检查的部分!! 这个有时候需要特别跟面试官提一声
递归实现:
要知道Partition内部使用<=的原因所在, 写成<, 会造成死循环(当遇到相等元素时, 会无限交换)
另外, 如果令 P=input[low] , 那么一定要 high--在前, 否则会造成元素覆盖
哨兵元素选择: 令中间元素位于 arr[low], 这样下面的快排程序可以直接使用 P=arr[low]1
2
3
4
5items = [arr[low], arr[high], arr[(low+high)//2]]
items.sort()
arr[low] = items[1]
arr[(low+high)//2] = items[0]
arr[high] = items[2]
Python 递归实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18arr = [random.randint(0, 15) for _ in range(20)]
print(arr)
def partition(arr, low, high):
P = arr[low]
while (low < high):
while (low < high and P <= arr[high]): high -= 1
arr[low] = arr[high]
while (low < high and P >= arr[low]): low += 1
arr[high] = arr[low]
arr[low] = P
return low
def quick_sort(arr, low, high):
mid = partition(arr, low, high)
if (mid < high): quick_sort(arr, mid+1, high)
if (mid > low): quick_sort(arr, low, mid-1)
quick_sort(arr, 0, len(arr)-1)
print(arr)
C++ 递归实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22void quickSort(vector<int>& input, int low, int high){
if(input.size()==0 || low<0 || low>=input.size() || high<0 || high>=input.size()){
cout<<"error";
exit(0);
}
int mid = Partition(input, low, high);
if(mid<high) quickSort(input, mid+1, high);
if(mid>low) quickSort(input, low, mid-1);
}
int Partition(vector<int>& input, int low, int high){
int p = input[low];
while(low<high){
// 一定要high在前, 否则会造成数组元素覆盖, 回忆头条面试惨痛经历!
while(low<high && p<=input[high]) high--; //这里注意, 如果忘了写=号, 就会陷入死循环
input[low] = input[high];
while(low<high && p>=input[low]) low++;
input[high] = input[low];
}
input[low] = p;
return low;
}
这里Partition用的是<=，那么在high位元素和p相等时，并不会执行交换，而是会high—, 如果忘了写等号, 就会陷入死循环。
Python 非递归实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25arr = [random.randint(0, 15) for _ in range(20)]
print(arr)
def partition(arr, low, high):
P = arr[low]
while (low < high):
while (low < high and P <= arr[high]): high -= 1
arr[low] = arr[high]
while (low < high and P >= arr[low]): low += 1
arr[high] = arr[low]
arr[low] = P
return low
def quick_sort(arr, low, high):
qs_stack = [low, high]
while len(qs_stack):
high = qs_stack.pop()
low = qs_stack.pop()
mid = partition(arr, low, high)
if mid < high:
qs_stack.extend([mid+1, high])
if mid > low:
qs_stack.extend([low, mid-1])
quick_sort(arr, 0, len(arr)-1)
print(arr)
C++ 非递归实现: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
31
32
33
34int partition(vector<int> &input, int low, int high){
int P = input[low];
while(low<high){
while(low<high && P <= input[high]) high--;
input[low] = input[high];
while(low<high && P >= input[low]) low++;
input[high] = input[low];
}
input[low] = P;
return low;
}
void quick_sort(vector<int> &input, int low, int high){
if(input.size()==0 || low<0 || low>=input.size() || high<0 || high>=input.size()){
cout<<"error";
exit(0);
}
stack<int> qs_stack;
qs_stack.push(high); //入栈顺序一定要注意, 要与后面的操作对应好
qs_stack.push(low);
while(!qs_stack.empty()){
low = qs_stack.top(); qs_stack.pop(); // low后入栈, 所以就应该先出栈
high = qs_stack.top(); qs_stack.pop();
if(low >= high) continue;
int mid = partition(input, low, high);
if(low<mid){
qs_stack.push(mid-1);//入栈顺序一定要注意,
qs_stack.push(low);
}
if(mid<high){
qs_stack.push(high);//入栈顺序一定要注意,
qs_stack.push(mid+1);
}
}
}
归并排序
核心思想是先 递归 分解数组, 再合并数组，使其成为一个新的有序数列
- 将一个序列等分成两部分, 分别进行排序操作
- 将上述两个排序后的序列进行归并
- 重复上述归并操作, 直到所有元素归并完毕
时间复杂度: $O(nlogn)$ 归并排序即使在最坏情况下, 时间复杂度也是 $O(nlogn)$, 这是它的一大优点.
最好情况: $O(nlogn)$
最好情况: $O(nlogn)$
空间复杂度: $(n)$, 需要借助临时数组(也可以不用), 同时, 递归也需要占用空间.
稳定性: 归并排序是稳定的排序算法, 在归并排序过程中, 相同元素有可能出现在同一组内或者不同组内, 如果在同一组内, 则默认就是稳定的, 如果在不同组内, 则根据组的前后位置来判断相同元素的顺序. 因此它是稳定的.
在合并时，由两种选择，一种是不使用额外空间的插入合并，这样会增加时间开销。另一种是使用额外空间的合并，这样不增加时间开销，但是需要额外空间。（当然，如果使用的是链表，则没有这种情况，可以既不增加时间，也不增加空间开销）
Python 常规递归排序: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
30arr = [random.randint(0, 15) for _ in range(20)]
print(arr)
def merge_sort(arr, start, end):
if (start < end) :
mid = (start + end) // 2
merge_sort(arr, start, mid)
merge_sort(arr, mid+1, end)
merge_array(arr, start, mid, mid+1, end)
def merge_array(arr, start1, end1, start2, end2):
res = [] # 辅助数组, 利用插入法将两个有序数组合并
i = start1
j = start2
while (i <= end1 and j <= end2):
if arr[i] <= arr[j]: # start1 数组在前, 所以相等时 arr[i] 先加入, 以此控制稳定性
res.append(arr[i])
i += 1
else:
res.append(arr[j])
j += 1
while (i <= end1):
res.append(arr[i])
i += 1
while (j <= end2):
res.append(arr[j])
j += 1
for i in range(start1, end2+1):
arr[i] = res[i-start1]
merge_sort(arr, 0, len(arr)-1)
print(arr)
C++ 常规递归排序: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
31
32
33
34void mergesort(vector<int>& a,int first, int last){
if(first<last){
mid = (last+first)/2;
mergesort(a, first, mid);
mergesort(a, mid+1, last);
mergeArray(a, first,mid,mid+1,last);
}
}
void mergeArray(vector<int>& a, int first1,int last1,int first2,int last2){
vector<int> temp;
int i = first1;
int j = first2;
while(i<=last1 && j<=last2){
if(a.at(i) < a.at(j)){
temp.push_back(a.at(i));
i++;
}
else{
temp.push_back(a.at(j));
j++;
}
}
while(i<=last1){
temp.push_back(a.at(i));
i++;
}
while(j<=last2){
temp.push_back(a.at(j));
j++;
}
for(int i = 0; i<temp.size(); i++)
a.at(first1+i) = temp.at(i);
}
C++ 原地归并排, 不借助辅助数组, Python 也可以实现原地归并, 但是写法较麻烦, 这样就偏离了 Python 语言本身的优势, 简单易读, 所以这里只给出 C++ 的原地归并排序
1 | void swap_memory(vector<int> &data, int start1, int end1, int start2, int end2){ |
堆排序
时间复杂度: $O(nlogn)$ 堆排序即使在最坏情况下, 时间复杂度也是 $O(nlogn)$, 这是它的一大优点. (完全二叉树)
最好情况: $O(nlogn)$
最坏情况: $O(nlogn)$
空间复杂度: $(1)$, 直接在数组上构建堆, 不需要借助临时数组
稳定性: 堆排序是不稳定的排序算法, 不稳定性发生在弹出堆顶元素, 进行对调整的时刻.
堆简介
堆排序与快速排序，归并排序一样都是时间复杂度为 $O(nlogn)$ 的几种常见排序方法
堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。
如下图,是一个堆和数组的相互关系:
因此,对于给定的某个节点的下标i, 可以很容易计算出这个节点的父节点, 子节点的下标
- Parent(i) = floor((i-1)/2)，i 的父节点下标
- Left(i) = 2i + 1，i 的左子节点下标
- Right(i) = 2(i + 1)，i 的右子节点下标
堆一般分为两种,大顶堆和小顶堆, 前者每个节点的值都大于它的子节点,后者反之
大顶堆:
小顶堆:
用官方数据结构实现堆排序
Python 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18import heapq
arr = [random.randint(0, 15) for _ in range(20)]
print(arr)
def heap_sort(arr):
res = []
heapq.heapify(arr) # 小顶堆, 升序排列
while len(arr):
res.append(heapq.heappop(arr))
return res
def heap_sort2(arr):
res = []
heapq._heapify_max(arr) # 大顶堆, 降序排列
while len(arr):
res.append(heapq._heappop_max(arr))
return res
#print(heap_sort(arr))
print(heap_sort2(arr))
C++ 实现: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
int main() {
std::priority_queue<int> max_heap; // 默认是大顶堆, 降序排列
for (int n : {1,8,5,6,3,4,0,9,7,2}) // 将元素压入堆中
max_heap.push(n);
while (!max_heap.empty()) {
std::cout << max_heap.top() << " ";
max_heap.pop();
}
std::cout << std::endl << std::endl;
//9 8 7 6 5 4 3 2 1 0
std::priority_queue<int, std::vector<int>, std::greater<int> > min_heap; // 小顶堆, 升序排列
for (int n : {1,8,5,6,3,4,0,9,7,2}) // 将元素压入堆中
min_heap.push(n);
while (!min_heap.empty()) {
std::cout << min_heap.top() << " ";
min_heap.pop();
}
std::cout << std::endl << std::endl;
//0 1 2 3 4 5 6 7 8 9
return 0;
}
堆排序原理
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
- 最大堆调整（Max-Heapify）：将堆作调整，使得子节点永远小于父节点
- 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
- 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
基于上面的三种操作,可以进行堆的插入和删除:
- 插入: 将新元素放置在数组末尾,然后进行堆调整
- 删除: 移除堆顶,然后将数组末尾元素置于堆顶,然后进行堆调整(删除主要用于排序)
最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：
代码实现:
1 | // 递归实现 |
创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。
代码实现:
1 | //创建堆 |
创建好堆以后,就可以通过移除堆顶来进行排序,每次将堆顶元素和数组末尾元素进行交换(这样可以不借助额外空间完成排序)，然后对数组的前n-1个元素重新进行堆调整构成新的大顶堆, 重复此过程知道堆中只剩下一个元素, 如下图所示:
1 | //代码实现 |
计数排序
计数排序是 非比较 排序算法, 适用于已知序列中的元素值在 $(0, k)$ 区间内的情况.(整数) 首先将每个元素出现的次数数出来, 然后算出该元素在最终有序序列中的绝对位置, 再依次将初始序列中元素, 根据确定的最终位置进行移动. 计算最终位置采用的思想是, 假设序列中小于元素 a 的个数为 x, 则可以直接将 a 放到第 x+1 位置上, 另外需要注意存在几个相同元素时要做适当调整, 不能将元素放在同一个位置上. 计数排序的步骤如下:
- 统计数组 A 中每个值 A[i] 出现的次数, 存入计数数组C[A[i]], 数组 C 的大小为 k;
- 从前向后, 使数组 C 中的每个值等于其和前一项的相加和, 这样, 数组 C[A[i]] 的含义就变成了代表数组 A 中 小于等于 A[i] 的元素个数.
- 从后往前填充排序数组 B: 将数组元素 A[i] 放在数组 B 的第 C[A[i]] 个位置(下标为 C[A[i]] - 1), 每放一个元素就将 C[A[i]] 递减(从后往前填充可保证对于相同元素的稳定性, 即位置相对靠后的元素在 B 中的位置也相对靠后).
时间复杂度: $O(n+k)$
最好情况: $O(n+k)$
最坏情况: $O(n+k)$
空间复杂度: $(n+k)$, 需要统计每个元素的个数, 同时在进行元素安放时, 也需要额外空间.
稳定性: 计数排序是稳定的排序算法, 因为在计算绝对位置的时候, 可以根据相同元素的前后关系决定绝对位置的前后.
1 | def countSort(nums): |
基数排序
基数排序是 非比较 排序算法. 它首先将所有待比较正整数统一为同样的数位长度, 其中数位短的数前面补零. 然后, 从最低位开始进行基数为 10 的计数排序, 一直到最高位计数排序完后, 数列就变成了一个有序序列.
时间复杂度: $O(d\times (n+r))$, 其中, $d$ 代表位数, $r$ 代表基数, $n$ 代表是数组元素个数, 一趟分配的时间复杂度是 $O(n)$, 一趟收集的时间复杂度是 $O(r)$, 共进行 $d$ 趟分配和收集.
最好情况: $O(d\times (n+r))$
最坏情况: $O(d\times (n+r))$
空间复杂度: $(r+n)$
稳定性: 基数排序是稳定的排序算法, 因为它不需要比较数值的大小.
1 | def radixSort(nums, d=2): # 默认三位数, 如果是四位数, 则 d=4 |
桶排序
桶排序是非比较排序算法. 工作原理是将数组分到有限数量的桶里, 然后每个桶的内部再分别排序(有可能使用别的排序算是或者以递归方式继续使用桶排序进行排序).
时间复杂度: $O(n+m)$, 其中 $n$ 为待排序的元素个数, $m$ 为桶的个数.
最好情况: $O(n+m)$
最坏情况: $O(n+m)$
空间复杂度: $(n)$ 所有桶内的元素个数之和为 n.
稳定性: 桶排序是稳定的排序算法, 因为它不需要比较数值的大小, 没有交换元素的相对位置.
1 | def bucketSort(nums): |
桶排序适用于数据分布相对均匀或者数据跨度范围不大时使用, 否则, 会消耗大量的空间
应用:
(1). 一年的全国高考考生人数为500万，分数使用标准分，最低100 ，最高900 ，没有小数，要求对这500万元素的数组进行排序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为 $O(5000000*log5000000)≈1.112亿$。但是我们发现，这些数据都有特殊的条件： 100=<score<=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进 $f(score)=score-100$ 的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有多少人，501分有多少人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况
(2) 在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可（内存限制为2G意思是可以使用2G空间来运行程序，而不考虑本机上其他软件内存占用情况。） 关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。
分析：既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法。
思想：将整型的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。
第一步:把10G整数每2G读入一次内存，然后一次遍历这536,870,912即（102410241024）* 2 /4个数据。每个数据用位运算”>>”取出最高8位(31-24)。这8bits(0-255)最多表示256个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量NUM[256]。
代价：(1) 10G数据依次读入内存的IO代价(这个是无法避免的，CPU不能直接在磁盘上运算)。(2)在内存中遍历536,870,912个数据，这是一个O(n)的线性时间复杂度。(3)把256个桶写回到256个磁盘文件空间中，这个代价是额外的，也就是多付出一倍的10G数据转移的时间。
第二步：根据内存中256个桶内的数量NUM[256]，计算中位数在第几个桶中。很显然，2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加，发现少于1,342,177,280，把第128个桶数据量加上，大于1,342,177,280。说明，中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(若数据大致是均匀分布的，每个文件的大小估计在10G/256=40M左右，当然也不一定，但是超过2G的可能性很小)。注意，变态的情况下，这个需要读入的第128号文件仍然大于2G，那么整个读入仍然可以按照第一步分批来进行读取。
代价：(1)循环计算255个桶中的数据量累加，需要O(M)的代价，其中m<255。(2)读入一个大概80M左右文件大小的IO代价。
第三步：继续以内存中的某个桶内整数的次高8bit（他们的最高8bit是一样的）进行桶排序(23-16)。过程和第一步相同，也是256个桶。
第四步：一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。
整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上，即10G数据分255个文件写回磁盘上。一般而言，如果第二步过后，内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了（修改者注：我想，继续桶排序但不写回磁盘，效率会更高？）。
树
二叉树
基本概念和性质
二叉树的定义: 二叉树中的每个节点至多有2棵子树, 并且子树有左右之分, 其次序不能任意颠倒。
二叉树的性质:
- 对于非空二叉树: $N_0 = N_2 +1$
- 在于非空二叉树, 第k层上的节点数不超过: $2^{k-1}$
- 高为h的二叉树, 总节点数不超过: $2^h-1$
- 具有N个节点的完全二叉树, 其高度为: $\lceil log_2(N+1) \rceil$ 或 $\lfloor log_2{N} \rfloor +1$
- 对于完全二叉树, 如果各个节点按照顺序存储(从 1 开始), 则节点之间编号具有一定关系:
- 节点 $i$ 的父节点为 $\lfloor \frac{i}{2} \rfloor (i>1)$
- $i$的左右子树分别为: $2i$ 和 $2i+1$ （如果$2i/2i+1 \geq N$, 则无左/右子树
- 给定N个节点, 能够成$h(N)$ 种不同的二叉树: $h(N)=…$
- 设有$i$个枝点, $I$为所有枝点的道路长度总和, $J$为叶的道路长度总和$J=I+2i$
注意: 二叉树不是度为2的树。 度为2的树至少要有3个节点, 而二叉树可以为空;度为2的树的左右子树是相对而言的, 当只有一个孩子时, 就无须分左右
满二叉树与完全二叉树
满二叉树: 除叶子节点外的所有节点均有两个子节点
完全二叉树: 除了叶子节点所在的层之外, 其他层均 “满”, 并且叶子节点是从左往右分布的.
二叉树的遍历
先序遍历: 根节点、左子树、右子树
递归实现
1 | void preOrder(Tree t){ |
非递归实现
对于任一节点, 其可看做是根节点, 因此直接访问, 访问后, 若其左孩子不为空, 则按相同规则访问其左子树, 当访问完左子树之后, 再访问其右子树:
对于任一节点P:
- 访问节点P, 并将P入栈
- 如果P的左孩子不为空, 则令P = P->left, 并转向第一步。若为空, 则将P出栈, 并令P = P->right, 然后转向第一步。
- 直到P为nullptr并且栈为空时, 结束循环
1 | vector<TreeNode*> preOrder; |
中序遍历: 左子树、根节点、右子树
递归
1 | void in_order(TreeNode* pRoot){ |
非递归
对于任一节点, 优先查看其左孩子, 而左孩子节点又可以看作是一个根节点, 则继续优先查看其左孩子, 直到遇到左孩子节点为空的根节点才进行访问。然后再转向查看其右孩子, 右孩子可看作是一个根节点, 继续按上面的规则循环:
对于任一节点P:
- 若其左孩子不为空, 则就P入栈并将P的左孩子置为当前的P, 然后继续查看当前P的左孩子, 直到为空；
- 经过上一步后, P指向了空的左孩子, 因此取栈顶元素并进行出栈操作, 同时访问该栈顶节点, 然后将P置为栈顶节点的右孩子（无需判断右孩子是否为空, 若为空则下一次循环会自动继续取栈顶）
- 知道P为nullptr并且栈为空时循环结束
1 | vector<TreeNode*> inOrder; |
后序遍历: 左子树、右子树、根节点
解法一: 递归
C++ 实现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/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
postorder(root, res);
return res;
}
void postorder(TreeNode* root, std::vector<int>& res) {
if (root == nullptr) return;
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
return;
}
};
Python1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
def post_order(root, res):
if (root.left is not None): post_order(root.left, res)
if (root.right is not None): post_order(root.right, res)
res.append(root.val)
return res
res = []
if root is None: return res
post_order(root, res)
return res
解法二: 迭代
用一个变量 pre 来维护上一个输出的节点, 当上一个输出的节点是当前节点的右孩子的时候, 说明左右都遍历完了.
C++ 实现
1 | class Solution { |
Python1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
pre = None
while(root or stack): # root 非空, 或者, 栈非空
while(root): # 左儿子一直入栈
stack.append(root)
root = root.left
node = stack[-1] # 取栈尾, 注意此时不一定访问栈尾
if node.right is None or node.right == pre: # 只有当右儿子为空或者右儿子已经被访问过时, 才能访问当前节点
res.append(node.val)
pre = stack.pop() # 标记访问的节点, 以便进行右儿子的判断
else:
root = node.right # 继续循环入栈
return res
二叉排序树（Binary Sort Tree, BST）
基本概念和性质
定义: 也叫二叉查找树或有序二叉树。当树不为空时, 该树具有如下性质:
- 左子树上的所有节点值, 均小于其根节点的值
- 右子树上的所有节点值, 均大于其根节点的值
- 左、右子树也分别为二叉排序树
- 没有键值相等的节点
性质: 对二叉排序树进行中根遍历, 即可得到一串有序数列（从小到大）
时间复杂度: 插入与查找的复杂度均为$O(logn)$, 但在最坏情况下为$O(n)$（原因在于树不一定是平衡的）
平衡二叉树
AVL树, 名字来源于其发明者 Adelson-Velsky 和 Landis
红黑树
B+树
字典树/前缀树
基本概念
Trie 树, 又称字典树, 单词查找树或前缀树, 是一种用于快速检索字符串的多叉树结构, 如英文字母的字典树是一个26叉树, 数字的字典树是一个10叉树.
字典树可以利用字符串的公共前缀来节约空间, 如下图所示.
当然, 如果字符串列表中存在大量没有公共前缀的字符串, 则字典树会变得非常消耗内存. 字典树的基本性质可以概括为以下三点:
- 除根节点以外, 每个节点都只包含一个字符(根节点不包含字符)
- 当前节点的所表示的字符串, 就是将从根节点到当前节点的路径上的字符连接起来的字符串.
- 每个节点的所有子节点包含的字符各不相同
基本实现
实现前缀树: https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。三个操作的复杂度分别为($m$ 为前缀树的高度):
insert: $O(m)$search: $O(m)$startsWith: $O(m)$
1 | class Trie: |
相关练习题
高级实现
并查集
并查集: 需要经常使用 “并” 操作, 且需要经常查询元素是否在集合中
- 并查集十分适合用于解决一类 “连接” 问题. 同时并查集也是解决 “图” 相关问题的一个很好的辅助工具
- 如何在社交网络中, 快速判断某个人是否认识另一个人, 网络抖音上的用户关注关系等等.
- 并查集另一个很重要的作用: 可以使用数学中的集合操作.
- 连接问题和路径问题的区别: 连接问题比路径问题所需要问答的问题更少.
- 连接问题: 回答任意两个节点是否相连
- 路径问题: 回答任意两个节点之间的路径
并查集的操作
对于一组数据来说, 并查集主要支持两个操作:
union(p, q): 并, 将 p, q 合并到一颗树中find(p): 查询 p 的根节点
问答的问题:- isConnected(p, q)
并查集的实现:
- QuickFind: 查找的时候很快 $O(1)$, 但是 “并” 的时候较慢 $O(n)$.
- 常用实现: 将每一个元素, 看做是一个节点, 每个节点有一个指向父亲的指针. 两个节点是否相连表现为它们是否拥有同样的根节点. 根节点是父节点为自身的节点.
这种实现使得 “并” 和 “查” 的操作都依赖于 树的高度, 因此在 “并” 的时候, 应该注意尽量使树的高度较小(这一步对性能优化很明显), 而在绝大多数情况下, 树的高度都远远小于 $n$. 针对并查集树的高度的两种优化:- 基于 rank(树高) 的 union 优化
- 路径压缩(在 find 的时候, 将当前节点的父亲指向父亲的父亲, 这样 find 之后, 树的高度有可能变矮), 递归的路径压缩可以让路径上所有节点的父指针都指向跟节点, 这样虽然在逻辑上是最优的, 但是实现时, 通常会利用递归来实现, 而实际使用中, 有时候递归的开销会掩盖这种优化. 经过以上的 rank 优化和路径压缩优化, 并查集的 “并” 和 “查” 的操作, 近乎是 $O(1)$.
代码实现:
1 | class UnionFind: |
相关题目
无向图中连通分量的数目
题目链接: https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/
直接使用并查集, 最后返回集合个数即可除法求值
题目链接: https://leetcode-cn.com/problems/evaluate-division/由斜杠划分区域
题目链接: https://leetcode-cn.com/problems/regions-cut-by-slashes/
图
基本介绍
应用: 交通运输, 社交网络, 互联网, 工作安排…
- 无向图(Undirected Graph)
- 有向图(Directed Graph)
- 无权图(Unweighted Graph)
- 有权图(Weighted Graph)
- 简单图: 没有自环边和平行边, 大多数基础问题不涉及这两个概念
图的表示方式:
- 邻接矩阵( $n\times n$ 的二维矩阵): 可以用 vector 实现, 适合表示稠密图
- 邻接表: 可以用 vector 实现(删除的时候不是 $O(1)$) 或者 list (删除的时候是 $O(1)$), 适合表示稀疏图
图算法中最常见的操作: 遍历邻边
图的基础算法: 图的遍历, 对于遍历过的节点, 需要记录, 以免死循环
- DFS: 邻接表 $O(V+E)$, 邻接矩阵 $O(V^2)$
- BFS: 用队列实现(同样要记录某节点是否已经被加入到队列过), 邻接表 $O(V+E)$, 邻接矩阵 $O(V^2)$
遍历可以求连通分量, 遍历的次数就是连通分量的个数. 同时, 可以将当前连通分量个数作为 id 建立并查集
图中任意两点的路径
检测图中是否有环(可用DFS实现)
BFS 可以求取 无权 图的最短路径
图的构建
利用 Python 的字典, 可以构建图片的有向邻接表.
假设传入的是 (u, v, w) 三元组构成的边的列表, 三元组的元素分别代表: 起始点, 终止点, 权重. 那么, 可以构建出图结构如下:1
2
3
4
5
6
7graph = dict()
for (u, v, w) in edges:
graph[u] = graph.get(u, dict())
graph[u][v] = w
# 使用时, 可以直接利用起点和终点来访问边的权重, 非常方便:
graph[u][v] # 前提是该边存在
图的遍历
BFS:
1 | node = start # node 指向起始节点 |
迷宫的最小路径(旷视)
DFS:1
2
3
4
5
6
7
8
9
10
11node = start # node 指向起始节点
res = [] # 遍历图得到值的集合
visited = [] # 存在访问过的节点
def dfs(node):
visited.append(node)
for adj_node in graph[node].keys():
if adj_node not in visited:
res.append([node, adj_node, graph[node][adj_node]])
dfs(adj_node)
dfs(node)
非递归:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23graph = {
'a' : ['b', 'c'],
'b' : ['a', 'c', 'd'],
'c' : ['a','b', 'd','e'],
'd' : ['b' , 'c', 'e', 'f'],
'e' : ['c', 'd'],
'f' : ['d']
}
def DFS(graph, s):
stack = []
stack.append(s)
seen = set()
seen.add(s)
while len(stack) > 0:
vertex = stack.pop()
nodes = graph[vertex]
for node in nodes:
if node not in seen:
stack.append(node)
seen.add(node)
print(vertex)
DFS(graph, 'a')
相关题目
拓扑排序
最小生成树
定义: 对于一个给定的带权图, 有 V 个节点, 找到连接这 V 个节点的 V-1 条边, 使得所有节点互相可达, 同时, 这 V-1 条边组成的权值之和是最小的.(各个节点均连通, 且连通成本最小). 此时成这个边的子集为该图的最小生成树
两种解决方法: Prim(普利姆), Kruskal(克鲁斯卡尔), 两个算法都是贪心算法
切分定理(Cut Property): 把图中的结点分为两部分, 成为一个切分(Cut), 如果一个边的两个端点, 属于切分(Cut)不同的两边, 这个边就称为横切边(Crossing Edge). 给定任意切分, 横切边中权重最小的边必然属于最小生成树.
Prim
https://zhuanlan.zhihu.com/p/61628249
算法思路: 从任意一个节点开始, 不断将新增的横切边放入最小堆中, 同时将不是横切边的边从堆中删除(Lazy Prim 不会急着删除, 而是在拿出这两条边时, 发现不是横切边, 然后将其扔掉, 选择下一个最小权值边), 选择权值最小的横切边, 加入新的节点, 直到所有节点加入, 最小生成树建成.
时间复杂度: $O(ElogE)$
优化: $O(ElogV)$
创建一个大小为 V 的最小堆, 只存储权值最小的横切边.
算法步骤:
1）以某一个点开始，寻找当前该点可以访问的所有的边
2）在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边
3）寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入
4）此时由所有边构成的树即为最小生成树。
代码实现: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
31
32
33
34
35
36from collections import defaultdict
from heapq import *
vertexs = list("ABCDEFG")
edges = [ ("A", "B", 7), ("A", "D", 5),
("B", "C", 8), ("B", "D", 9),
("B", "E", 7), ("C", "E", 5),
("D", "E", 15), ("D", "F", 6),
("E", "F", 8), ("E", "G", 9),
("F", "G", 11)]
def Prim(vertexs, edges, start_node):
adjacent_vertex = defaultdict(list)
for v1, v2, length in edges: # 构建图
adjacent_vertex[v1].append((length, v1, v2))
adjacent_vertex[v2].append((length, v2, v1))
mst = [] # 存放最小生成树的边
visited = set(start_node) # 记录已访问的节点
adjacent_vertexs_edges = adjacent_vertex[start_node]
heapify(adjacent_vertexs_edges) # 构建以边长为排序依据的最小堆
while adjacent_vertexs_edges:
w, v1, v2 = heappop(adjacent_vertexs_edges)
if v2 not in visited: # 如果当前最小边是横切边, 即第二个节点未访问过
visited.add(v2)
mst.append((v1, v2, w))
for next_vertex in adjacent_vertex[v2]: # 将新增的节点连接的所有横切边都加入到堆中
if next_vertex[2] not in visited:
heappush(adjacent_vertexs_edges, next_vertex)
return mst
print('prim:', Prim(vertexs, edges, 'A'))
Kruskal
算法思路: 先将图中所有的边进行排序, 然后选择最短的那条边, 查看该边加入当前的树中是否会形成 环, 如果不构成环, 那么它就是最小生成树中的边. 可以利用并查集来快速的判断环, 即对于一条边来说, 查看该边的两个节点在当前的树中是否连接, 如果连接, 则说明一旦加入这条边, 就会形成环, 反之不会.
如果横切边有相等的边, 则选择任意一个即可, 此时, 图存在多个最小生成树.
时间复杂度: $O(ElogE + ElogV)$
代码实现: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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51node = dict()
rank = dict()
def make_set(point):
node[point] = point
rank[point] = 0
def find(point):
if node[point] != point:
node[point] = find(node[point])
return node[point]
def merge(point1, point2):
root1 = find(point1)
root2 = find(point2)
if root1 != root2:
if rank[root1] > rank[root2]:
node[root2] = root1
else:
node[root1] = root2
if rank[root1] == rank[root2] : rank[root2] += 1
def Kruskal(graph):
for vertice in graph['vertices']:
make_set(vertice)
mst = set()
edges = list(graph['edges'])
edges.sort()
for edge in edges:
weight, v1, v2 = edge
if find(v1) != find(v2):
merge(v1 , v2)
mst.add(edge)
return mst
graph = {
'vertices': ['A', 'B', 'C', 'D'],
'edges': set([
(1, 'A', 'B'),
(5, 'A', 'C'),
(3, 'A', 'D'),
(4, 'B', 'C'),
(2, 'B', 'D'),
(1, 'C', 'D'),
])
}
print(Kruskal(graph))
单源最短路径
求得某一点到其他任意一点的最短路径, 由此可以构成一个 单源最短路径
拥有负权环的图, 没有最短路径, 因为每在环中转一次, 花费都会变小. 因此, 该单源最短路径算法有解的前提是图中可以有负权边但是不能有负权环
常用算法:
- Dijkstra(迪杰斯特拉): 图中不能有负权边, 复杂度 $O(ElogV)$, 先找到没有访问过的节点的路费最小的节点, 然后查看该节点的邻边, 并更新当前所有路径的最小段路径长度.
- Floyd 算法: 可以处理 有负权但是无负权环 的图, 复杂度 $O(V^3)$
- Bellman-Ford 算法: 自身可以检查是否有负权环. 复杂度 $O(EV)$. 基本思想: 如果一个图中没有负权环, 从一点到另外一点的最短路径, 最多经过所有的 V 个定点, 有 V-1 条边, 若多于 V-1 条边, 存在某一定点经过了两次, 即存在负权环. 对一个点的一次松弛操作, 就是找到经过这个点的另外一条路径, 该路径多一条边, 但是权值更小. 因此需要对所有的点都进行 V-1 次松弛操作
Dijkstra(迪杰斯特拉)
算法思路: 核心思路是以起始点为中心不断向外层扩展, 扩展的同时更新经过节点的最短路径, 具体算法步骤如下所示:
- 初始化起始顶点到其他任意顶点的距离数组, 标记所选的初始顶点距离为 0，其余顶点距离设为无穷大。
- 将除起始顶点外的其他顶点加入到 未访问顶点数组 中.
- 将具有最小当前距离的 非访问顶点 设置为当前顶点 C。
- 对于当前顶点 C 的每个邻居顶点 N：将当前距离 C 与连接 C-N 的边的权重相加。 如果它小于顶点 N 的当前距离，则将其设置为 N 的新当前距离。
- 将当前顶点 C 从 未访问顶点数组 中移除
- 如果还有非访问顶点，重复步骤2，直到所有顶点均访问。
代码实现:
1 | def Dijkstra(edges, N, K): # edges 代表边, 元素为三元组(u, v, w), 分别代表起点终点和权重, N 为图中节点总数, K 为单源最短路径的起始节点编号(1~N) |
另一种实现: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
31
32
33
34inf = float('inf')
matrix_distance = [[0,1,12,inf,inf,inf],
[inf,0,9,3,inf,inf],
[inf,inf,0,inf,5,inf],
[inf,inf,4,0,13,15],
[inf,inf,inf,inf,0,4],
[inf,inf,inf,inf,inf,0]]
def dijkstra(matrix_distance, source_node):
inf = float('inf')
# init the source node distance to others
dis = matrix_distance[source_node]
node_nums = len(dis)
flag = [0 for i in range(node_nums)]
flag[source_node] = 1
for i in range(node_nums-1):
min = inf
#find the min node from the source node
for j in range(node_nums):
if flag[j] == 0 and dis[j] < min:
min = dis[j]
u = j
flag[u] = 1
#update the dis
for v in range(node_nums):
if flag[v] == 0 and matrix_distance[u][v] < inf:
if dis[v] > dis[u] + matrix_distance[u][v]:
dis[v] = dis[u] + matrix_distance[u][v]
return dis
print(dijkstra(matrix_distance, 0))
Floyd(弗洛伊德)
算法思路:
代码实现:1
2
3
4
5
6
7
8
9
10def Floyd(dis):
#min (Dis(i,j) , Dis(i,k) + Dis(k,j) )
nums_vertex = len(dis[0])
for k in range(nums_vertex):
for i in range(nums_vertex):
for j in range(nums_vertex):
if dis[i][j] > dis[i][k] + dis[k][j]:
dis[i][j] = dis[i][k] + dis[k][j]
return dis
print(Floyd(matrix_distance))
背包问题
leetcode上并没有背包问题的题目，但有其类似的题目: 零钱兑换, 一和零,
背包问题只在 lintcode 上有
092. 背包问题
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
最多能装多满, 也就是说本题 每个物体的价值就等于它的重量
题目链接: https://www.lintcode.com/problem/backpack/description
动态规划解法: 设置二维数组, 代表某一特定容量下, 容纳前 i 个物体时, 最大可以装多少重量, 动态规划更新方程为:
1 | class Solution: |
对于 0-1 背包问题, 我们可以将空间复杂度进一步优化, 根据状态转移方程, 当前的 dp 状态只与上一行有关, 因此我们可以先给出第一行 dp 数组的值, 然后从后往前的进行赋值, 如下所示.
1 | class Solution: |
背包问题 II
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
问最多能装入背包的总价值是多大?
本题同样是 0-1 背包问题, 问的是总价值, 因此只需要将 92 题的代码中的 dp 公式根据价值进行状态转移即可. 核心思路相同.
题目链接: https://www.lintcode.com/problem/backpack-ii/description
dp 二维数组1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
"""
@param m: An integer m denotes the size of a backpack
@param A: Given n items with size A[i]
@param V: Given n items with value V[i]
@return: The maximum value
"""
def backPackII(self, m, A, V):
# write your code here
n = len(A)
if n == 0: return 0
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
for j in range(1, m+1):
if j < A[i]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]] + V[i]) # 注意这里用的是 V[i], 代表价值
return dp[-2][-1]
dp 优化到一维数组1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution:
"""
@param m: An integer m denotes the size of a backpack
@param A: Given n items with size A[i]
@param V: Given n items with value V[i]
@return: The maximum value
"""
def backPackII(self, m, A, V):
# write your code here
n = len(A)
if n == 0: return 0
dp = [0] * (m+1)
for i in range(n):
for j in range(m, A[i]-1, -1): # 只需要遍历到 A[i] 即可
dp[j] = dp[j] if j < A[i] else max(dp[j], dp[j-A[i]] + V[i]) # 注意这里用的是 V[i], 代表价值
return dp[-1]
01 背包
问题描述: 有 N 件物品和一个容量为 M 的背包。（每种物品均 只有一件）第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。
上面的 92 题和 125 题均是 01 背包问题, 区别仅在于前者每个物体的价值等于其重量, 后者每个物体有独立的重量和价值.
01 背包问题的最大特点是: 每个物品仅有一件, 可以选择放或者不放.
用 dp[i][j] 代表只考虑前 i 个物品, 背包容量为 j 时可以获得的最大价值, 动态规划方程如下:
把这个过程理解下：在前i件物品放进容量v的背包时，它有两种情况：
- 第一种是第i件不放进去，这时所得价值为:f[i-1][v]
- 第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
优化: 根据上面的状态转移方程, 我们可以利用 逆序 将 dp 数组的空间复杂度从 $O(mn)$ 降低到 $O(m)$. 具体参见上面的题解.
完全背包
完全背包(CompletePack): 有 N 种物品和一个容量为 M 的背包，每种物品都有 无限件 可用。第 i 种物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
基本思路
按照类似的思路定义dp[i][j], 完全背包的状态转移方程如下:
这和 01 背包一样有 $O(NM)$ 个状态需要求解, 但是求解每个状态的时间已经不是常数了, 而是 $O(M/w[i])$. 如下所示
1 | def CompletePack(N, V, weight, value): |
简单优化
完全背包问题有一个很简单有效的优化，是这样的: 若两件物品 i、j 满足 w[i]<=w[j]且 v[i]>=v[j]，则将物品 j 去掉，不用考虑。这个优化的正确性显然: 任何情况下都可将价值小费用高得 j 换成物美价廉的 i，得到至少不会更差的方案。对于随机生成的数据，这个方法往往会大大减少物品的件数，从而加快 速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以 一件物品也去不掉。
这个优化可以简单的 O(N^2)地实现，一般都可以承受。另外，针对背包问题而 言，比较不错的一种方法是:首先将费用大于 V 的物品去掉，然后使用类似计数 排序的做法，计算出费用相同的物品中价值最高的是哪个，可以 $O(M+N)$ 地完成 这个优化.
解法一: 转化成 01 背包问题
既然 0-1 背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为 0-1 背包问题来解。最简单的想法是，考虑到第 i 种物品最多选 $M/w[i]$ 件，于是可以把第 i 种物品转化为 $M/w[i]$ 件费用及价值相同的物品，然后求解这个 0-1 背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将 完全背包问题转化为 0-1 背包问题的思路: 将一种物品拆成多件物品。
更高效的转化方法是: 把第 i 种物品拆成费用为 $w[i]2^k$、价值为 $v[i]2^k$ 的 若干件物品，其中 $k$ 满足 $w[i]\ast 2^k<=M$。这是二进制的思想，因为不管最优策略选几件第 i 种物品，总可以表示成若干个 $2^k$ 件物品的和。这样把每种物品拆成 $O(log(W/w[i]))$ 件物品，是一个很大的改进。
解法二: $O(NM)$ 的算法
该算法使用一维数组, 伪码如下:1
2
3for i=1..N
for w=0..W
dp[w]=max{dp[w],dp[w-cost]+weight}
你会发现，这个伪代码与0-1背包问题只有内层的循环次序不同而已。为什么这样一改就可行呢? 首先想想为什么 0-1背包问题中要按照 w=W..0 的逆序来循环。这是因为 要保证第 i 次循环中的状态 dp[i][w] 是由状态 dp[i-1][w-w[i]] 递推而来。换句话 说，这正是 为了保证每件物品只选一次，保证在考虑“选入第 i 件物品”这件策略时，依据的是一个绝无已经选入第 i 件物品的子结果 dp[i-1][w-w[i]]。而现 在完全背包的特点恰是每种物品可选 无限件，所以在考虑“加选一件第 i 种物品”这种策略时，却 正需要一个可能已选入第 i 种物品的子结果 dp[i][w-w[i]]， 所以就可以并且必须采用 w=0..W 的顺序循环。这就是这个简单的程序为何成立的道理。
Python 代码实现:
1 | def solve3(vlist,wlist,totalWeight,totalLength): |
多重背包
题目
有 N 种物品和一个容量为 M 的背包。第 i 种物品最多有 $num_i$ 件可用，每件耗费的空间是 $w_i$ ，价值是 $v_i$。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。
题目链接: https://www.nowcoder.com/questionTerminal/6ce78d70a25347058004691035d7540b
基本思路
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可。因为对于第 i 种物品有 $num_i + 1$ 种策略：取 $0, 1, num_i$ 件。令 dp[i][w] 表示前 i 种物品恰放入一个容量为 w 的背包的最大价值，则有状态转移方程：
解法一: 转化成 01 背包问题
把第 i 种物体换成 $num_i$ 件 01 物体, 将其转化成 01 背包问题.
解法二: $O(NMk)$
N 代表物体种类数量, M 代表背包容量, k 代表物体最大可使用次数
多重背包是每个物品有不同的个数限制，如第i个物品个数为num[i]。
同样可以用f[i][j]表示前i件物品恰放入一个容积为j的背包可以获得的最大价值，且每个物品数量不超多num[i]。则其状态转移方程为：
1 | def MultiplePack(N, V, weight, value, num): |
混合背包
https://www.jianshu.com/p/efa8fbc0fea4
有的物品只能取一次, 有的物品只能取若干次, 有的物品可以取无限次.
二维费用背包
分组背包
依赖背包
https://www.jianshu.com/p/3e0a5f394bcb
泛化物品
背包变形
输出最优方案
一般而言，背包问题是要求一个最优值，如果要求输出这个最优值的方案，可以参照一般动态规划问题输出方案的方法：记录下每个状态的最优值是由状态转移方程的哪一项推出来的，换句话说，记录下它是由哪一个策略推出来的。便可根据这条策略找到上一个状态，从上一个状态接着向前推即可。
输出字典序最小的最优方案
https://www.jianshu.com/p/3e0a5f394bcb
求方案总数
装满背包总共有多少种装法
LeetCode 039: 组合总和
LeetCode 322: Coin Change, 找零钱
字符串
最长回文子串: LeetCode-题目全解, 005, 马拉车(Manacher)算法
最长公共子串
题目描述
对于两个字符串, 请设计一个时间复杂度为 $O(mn)$ 的算法(这里的 $m$ 和 $n$ 为两串的长度), 求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列 U1,U2,..Un 和 V1,V2,...Vn, 其中 Ui + 1 == Ui+1 , Vi + 1 == Vi+1, 同时 Ui == Vi.
给定两个字符串 A 和 B, 同时给定两串的长度 $n$ 和 $m$.
解法一: 暴力
时间复杂度: $O(mnl)$, $l$ 为公共子串的长度
空间复杂度: $O(1)$
以一个字符串中的每一个字符作为公共子串的起始字符, 在另一个字符串中查找以该字符为起始的公共子串, 每一个字符的查找复杂度为 $O(nl)$, 共有 $m$ 个字符, 因此总的时间复杂度为 $O(mnl)$
1 | class LongestSubstring { |
解法二: 动态规划
时间复杂度: $O(mn)$, 两个 for 循环, 内部复杂度为 $O(1)$.
空间复杂度: $O(mn)$, 需要额外申请 $O(mn)$ 大小的矩阵空间
我们申请一个 dp 矩阵, dp[i][j] 代表以 A[i] 和 B[j] 字符为结尾的公共子串的长度, 那么, 就可以分为如下几种情况:
s[i]!=s[j]: 将dp[i][j]置为 0s[i]=s[j]: 令dp[i][j] = dp[i-1][j-1]+1, 要注意越界保护, 即如果i=0, 或者j=0, 我们就直接令dp[i][j]=1
在进行上面判断的同时, 每更新一次 dp[i][j], 就更新 longest 的值.
1 | class LongestSubstring { |
解法三: 优化的动态规划
时间复杂度: $O(mn)$, 两个 for 循环, 内部复杂度为 $O(1)$.
空间复杂度: $O(2m)$ 或者 $O(2n)$, 选择短的申请 dp 数组.
在解法二的 dp 数组更新公式中, 我们发现, dp[i][j] 只与它左上角的元素 dp[i-1][j-1] 有关, 因此, 我们可以只申请大小为 $2\times m$ 的动态数组即可, 只需每次将上一个数组的值更新为当前数组值, 而当前的数组可以作为未使用的数组来更新公共子串长度.
1 | class LongestSubstring { |
解法四: 再优化的动态规划
时间复杂度: $O(mn)$, 填充 “dp数组”, 复杂度不变
空间复杂度: $O(1)$, 利用一个变量就可以维护我们的 “dp数组”
从解法三中我们已经知道, dp[i][j] 的值只与 dp[i-1][j-1] 的值有关, 在解法二中, 我们是从左到右, 左上到下的维护 “dp数组”, 因此最少需要两行数据空间才能够维护, 如下图所示:
但是实际上, 我们 仅仅只需要当前元素的左上角元素就够了, 也就是说, 如果我们沿着对角线的顺序来填充 “dp数组”, 那么我们 只需要一个变量 就可以完成对整个数组的填充, 如下图所示:
1 | class LongestSubstring { |
1 | # python 实现 |
解法五: 后缀自动机
利用后缀自动机可以实现 $O(n)$ 的空间和时间复杂度, 但是考虑到时间成本问题, 并没有对该解法进行详细解析.
因为要彻底搞懂后缀自动机, 不仅仅要会解最长公共子串, 还应该熟悉其他的字符串题型如: 最小循环串.
最长公共子序列
最长公共子串与最长公共子序列的区别: 前者要求字符连续, 后者字符只需保持相对位置一致即可.
解法一: 动态规划
时间复杂度: $O(mn)$
空间复杂度: $O(mn)$
我们令 dp[i][j] 代表字符串中 i 和 j 之前的最长公共子序列的长度(不包含 A[i] 和 B[j]), 则最终的结果会存在与 dp[n][m] 中.
1 | class LCS { |
解法二: 优化的动态规划
时间复杂度: $O(mn)$
空间复杂度: $O(2m)$, 或$O(2n)$, 与最长公共子串思路一致
该解法与最长公共子串解法三思路一致, 代码如下:
1 | class LCS { |
1 | # python 实现 |
由于最长子序列需要同时用到左上角, 左边, 上边三个元素的值, 因此无法用常数变量来维护, 最少需要两行元素才能维护, 故无法做到常数空间复杂度
删除字符找到最长回文子序列
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。
输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.
输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。
解法:
先将字符翻转, 然后求这两者的 最长公共子序列, 即可找到最长的回文子序列, 然后用字符串长度减去该回文子序列长度即可.
最长递增序列
最长连续递增序列
- 最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的的递增序列。返回其长度
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意：数组长度不会超过10000。
解法一: 滑动窗口(最优)
因为此题要求子序列连续, 每个连续递增子序列之间是不相交的, 因此, 我们可以逐个遍历, 当遇到nums[i-1] >= nums[i]时, 说明一段递增子序列已经结束, 应该开启下一段, 期间我们不断更新最大的连续递增子序列的长度即可
时间复杂度: $O(N)$
空间复杂度: $O(1)$
1 | class Solution: |
最长递增子序列
- 最长递增子序列/最长上升子序列
求最长递增子序列(可以不连续)的长度
给定一个无序的整数数组，找到其中最长上升子序列的长度。 注意两点:
- 数组无序
- 子序列不必是连续的
Example:1
2
3Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up:
Could you improve it to O(n log n) time complexity?
解法四: DP+二分搜索(最优)
时间复杂度: $O(nlogn)$, 每次搜索的复杂度为 $O(logn)$, 总共需要搜索 $n$ 次
空间复杂度: $O(m)$, $m$ 为最长递增序列的长度.
同样还是 DP 解法, 但是我们重新赋予 dp[] 数组另一个含义, 我们令 dp[] 数组内储存的元素的数量刚好等于当前最长递增序列的数量, 注意, dp[] 数组内的值不一定是递增序列的值. 这样, 对于任意的一个数, 我们都将其与dp中的元素比较, 找到第一个大于该数的值, 并将其替换成该数, 此时, 虽然dp中的元素不是递增序列的值, 但是dp中的元素依然是有序的, 不仅维持了dp的长度, 同时还记录了新的有可能产生更长递增序列的值.
核心算过过程如下所示:
- 初始时, 令
dp[]数组为空, 即dp=[]; - 对于每一个元素
num, 我们查找num在dp数组中的upper_bound迭代器(首个大于num的元素的迭代器), 假设取名为upper;(注意,dp数组是有序的, 所以这里的查询复杂度为 $O(logn)$) - 查看
upper-1指向的元素是否和num相等, 如果相等, 则说明该元素已经存在, 那么就跳过该元素, 重新回到步骤2; - 如果
num大于dp数组内的所有元素, 则将num添加进dp数组; 否则, 就将dp数组中大于num的第一个元素的值赋为num. - 重复步骤2,3,4, 直到遍历完数组为止.
为了更好的解释这种解法, 我们通过举例进行说明, 假定输入的数字序列为: [4,10,3,4,10,3,2], 那么我们的 dp[] 数组的变化情况如下:
dp=[],初始时, 数组为空;dp=[4], 遍历元素4, 加入到数组中;dp=[4,10], 遍历元素10, 10大于所有元素, 将其添加到数组中;dp=[3,10], 遍历元素3, 发现第一个大于3的值为4, 将其赋值为3;dp=[3,4], 遍历元素4, 发现第一个大于4的的值为10, 将其赋值为4;dp=[3,4,10], 遍历元素10, 10大于所有元素, 将其添加到数组中;dp=[3,4,10], 遍历元素3, 3在数组中已经存在, 跳过该元素;dp=[2,4,10], 遍历元素2, 发现第一个大于2个值为3, 将其赋值为2.
综上, 我们可以看到, dp 数组的长度始终等于当前数组的最长子序列的长度, 故而, 直接返回 dp.size() 即为最终的结果. 注意, dp 内的值不一定为递增子序列的值.
Python 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def upper_bound(dp, num): # 找到 upper_bound, 即首个大于 num 的值
low = 0
high = len(dp)
while (low < high):
mid = (low + high) // 2
if dp[mid] <= num:
low = mid+1
else: # dp[mid] > num
high = mid
return high
dp = []
for num in nums:
index = upper_bound(dp, num)
if (index!=0 and dp[index-1] == num): continue
if index == len(dp): # 如果dp内的元素均小于该元素, 则递增子序列长度+1
dp.append(num)
else: # 否则, 将首个大于该值的位置变成该值
dp[index] = num
return len(dp)
C++ 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()==0) return 0;
vector<int> dp;
for(auto num : nums){
auto upper = std::upper_bound(dp.begin(), dp.end(), num);
if(upper!=dp.begin() && *(upper-1) == num) continue; // 如果num在dp数组中已经存在, 则跳过该num.
if(upper==dp.end()){
dp.push_back(num); // 当前num比dp数组内的所有值都大, 则添加进dp数组
}else{
*upper = num; // 用更小的值替代当前dp数组内的值
}
}
return dp.size(); // 最终, dp数组的长度即为最长递增序列的长度
}
};
最长递增子序列的个数
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
解法一: 动态规划
时间复杂度: $O(n^2)$
空间复杂度: $O(n)$
线段树解法可以达到 $O(nlogn)$ 的时间复杂度, 但是代码量较多, 此处能解出动态方法足以.
用length[i]存储以第 i 个字符结尾的递增子序列的最长长度, 用count[i]表示该长度下的子序列个数.
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
n = len(nums)
length = [1] * n # 每个字符的最短长度为 1
count = [1] * n # 每个子序列的最少数量为 1
for i in range(n):
for j in range(i):
if nums[j] < nums[i]: # 用第 i 个字符为结尾时, 看与前面的字符是否能组成递增子序列
new_len = length[j] + 1
if new_len > length[i]: # 如果组成后的长度 > 当前长度, 则更新长度和该长度的数量
length[i] = new_len
count[i] = count[j]
elif new_len == length[i]: # 如果 = 当前长度, 将更新长度数量
count[i] += count[j]
max_len = max(length) # 统计 max_len 的总数量
return sum(c for i, c in enumerate(count) if length[i] == max_len)
递增的三元子序列
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的i, j, k, 且满足0 ≤ i < j < k ≤ n-1，
使得arr[i] < arr[j] < arr[k]，返回true; 否则返回false。
说明: 要求算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。
Example 1:1
2Input: [1,2,3,4,5]
Output: true
Example 2:1
2Input: [5,4,3,2,1]
Output: false
解法一: 用辅助变量指向 min 和 mid(最优)
时间复杂度: $O(n)$, 每个元素之遍历一次
空间复杂度: $O(1)$, 无需额外空间
我们利用两个变量 min 和 mid 分别指向三元子序列中的最小元素和中间元素, 最开始时, 二者赋初值为 INT_MAX, 然后遍历数组, 对于数组中的每一个数 num, 进行如下判断:
- 是否小于等于
min, 若满足, 则令min=num; - 若不满足(1), 则说明
num > min, 判断num是否小于等于mid, 若满足, 责令mid=num;(此时mid一定大于min, 且下标也大于min下标) - 若不满足(1)(2), 则说明
num不仅大于min, 而且大于mid, 同时num的下标也大于前两者, 由此, 我们找到了一个满足条件的递增三元组子序列, 可直接返回true. 否则, 重复以上步骤直至遍历完数组 - 如果遍历完整个数组后, 仍然找不到符合条件的序列, 则说明不存在这样的序列, 返回 false.
Python 实现1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
low = float('inf')
mid = float('inf')
for num in nums:
if num <= low: # 如果 num <= low 则令其为 low
low = num
elif num <= mid: # 否则, 令其为 mid
mid = num
else: # 如果 num > low 且 > mid, 说明存在这样的三元组, 因为如果不存在的话, mid 或 low 肯定为 inf
return True
return False
字符串匹配算法-KMP
题目链接
找到子串在字符串中出现的位置
| 算法 | 预处理时间 | 匹配时间 |
|---|---|---|
| 暴力匹配法(朴素字符串匹配) | 无预处理过程 | $O((n-m+1)m)$ |
| Rabin-Karp | $O(m)$ | $O((n-m+1)m$ |
| Finite automaton(优先自动机) | $O(mk)$ | $O(n)$ |
| Knuth-Morris-Pratt(KMP) | $O(m)$ | $O(n)$ |
上表中, $n$ 是原始串(文本)的长度, $m$ 是子串的长度, $k$ 是字符集的大小.
暴力匹配法(朴素字符串匹配)
时间复杂度: $O((n-m+1)\times m)$
空间复杂度: $O(1)$
子串在原始串中的可能起始位置为: 0, 1, 2, …, n-m, 因此共有 $n-m+1$ 种可能性, 我们对每种可能性都进行遍历判断是否为子串, 每次遍历的复杂度为子串的长度 $m$, 因此, 最终的时间复杂度为: $O((n-m+1)\times m$. 该解法没有使用额外的空间.
下图是朴素字符串匹配的下标改变过程:
1 | class Solution { |
Rabin-Karp
Finite automaton(优先自动机)
Knuth-Morris-Pratt(KMP)
时间复杂度: $O(m+n)$, $m$ 为求 next 数组的复杂度, $n$ 为遍历原始串的复杂度
空间复杂度: $O(m)$, next 数组所占空间为子串的长度.
若只想看代码实现, 可以直接跳转到代码部分
在解法一当中, 每次失配时, 我们都是改变原始串(T)的下标 i, 这样复杂度肯定是最高的, 在 KMP 算法中, 我们通过改变子串(P)的下标 j 来降低复杂度, 首先来看两组 KMP 算法的下标 j 的跳跃示意图:
第一组:
第二组:
根据上面的示意图, 我们可以大致体会出 KMP 算法的思想所在, 具体来说就是, 当 T[i] 与 P[j] 失配时, 我们不改变 i 的指向, 而是令 j 指向之前的某一个位置 k, 继续判断 T[i] 与 P[k] 的值, 而这个位置 k, 必须满足性质: 字符串 P 中前面的 k 个字符(0~k-1)和后面的 k 个字符(j-k~j-1)必须相等, 也就是要满足下面的公式:
图片表示如下:
为什么可以直接移动到 k 位置而不需要检查 0~k-1 处的字符? 证明如下:
当
T[i]!=P[j]时, 一定有T[0~i-1]=P[0~j-1]
又因为P[0~k-1]=P[j-k~j-1], 故而一定有P[0~k-1]=P[j-k~j-1]=T[j-k~j-1].
下面, 我们就需要求得这些 k 的值, 并将其存储在 next 数组中, next 数组和长度和 P 相同, 并且其中的值只有 P 有关, 与 T 无关. 当我们求得 next 数组的值以后, 一旦 T[i] 与 P[j] 发生失配, 我们只需要令 j 跳到 k 处即可, 也就是 j=next[j]. 求取 next 数组的代码如下所示:
1 | class Solution { |
我们来仔细分析一下改代码的含义, 首先, 当 j=0 时发生失配, 由于 j 之前再没有可使用的字符的, 因此我们令 next[j]=-1, 此时, 我们不应该挪动 j, 而是应该将 i 指向下一个字符.
其次, 对于 j=1 时的情况, 我们只能将 j 跳到子串的最开始字符处, 因此, 当 j=1 时, 我们令 next[j]=0, 在代码中, 我们使用 k=-1 来代表 j=1 的, 这里 k 的值代表 next[j] 的值.
首先, 假设我们已经得到了 next[0~j] 的值, 我们该如何求 next[j+1] 呢? 有下面两个情况:
情况一: P[k]=P[j], 注意, 这里的 k=next[j], 因此就有 P[0~k-1] = P[j-k~j-1], 又因为 P[k]=P[j], 所以可以得到: P[0~k]=P[0~j], 所以我们可以得到 next[j+1] = k + 1, 在代码中, 我们令 k++; j++, 目的是为了满足 k=next[j]. 图示过程如下所示:
情况二: P[k]!=P[j] 此时我们无法得到 P[0~k]=P[0~j], 因此, 我们必须寻找 更短的 符合条件的 k 值, 因此, 我们令 k=next[k], 注意, 由于 k=next[j], 因此, 这里的赋值语句相当于 k=next[next[j]], 也就是说, 这里相当于是一个自我匹配的过程(令前缀和后缀匹配), 我们用已得到的 next 数组的部分值, 来得到最短的符合条件的 k 值. 如下图所示:
当得到 next 数组后, 我们就可以很容易的实现 KMP 的完整算法了, 注意这里有一个很容易错的点, .size 是无符号整数, 直接与负值比较或者会产生溢出(但如果参与计算后, 则会自动转换成整形, 因为常数默认是整形), 系统会判断-1比无符号的整数大!! 因此, 我们最好利用 int 型变量来持有其 size, 当需要动态的 size 时, 最好根据需要将其转换成 int 类型. 代码如下所示.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
31
32class Solution {
private:
void getNext(vector<int> &next, string &substr){
int m = substr.size();
next[0] = -1;
int k = -1;
int j=0;
while(j<m-1){
if(k==-1 || substr[k]==substr[j])
next[++j]=++k;// 相当于: j++; k++; next[j] = k;
else
k = next[k];
}
}
public:
int strStr(string str, string substr) {
int n=str.size(), m=substr.size();
if(m==0) return 0;
if(n==0) return -1;//当 m!=0, 而 n=0时, 应该返回-1
vector<int> next(substr.size());
getNext(next, substr);
int i=0, j=0;
while(i<n && j<m){
if(j==-1 || str[i]==substr[j]){
i++; j++;
}else
j = next[j];
}
if(j==m) return i-j;
return -1;
}
};
下面是 KMP 算法的 python
1 | # python 实现 |
排列组合问题
Python 快速获取排列组合:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16from itertools import combinations, permutations
combinations(iterable, r) #创建一个迭代器，返回iterable中所有长度为r的子序列，返回的子序列中的项按输入iterable中的顺序排序:
list(combinations(range(1, 4), 2))
[(1, 2), (1, 3), (2, 3)]
list(combinations(range(1, 4), 3))
[(1, 2, 3)]
permutations(iterable [,r]) #创建一个迭代器，返回iterable中所有长度为r的项目序列，如果省略了r，那么序列的长度与iterable中的项目数量相同
list(permutations(range(1,4), 2))
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
list(permutations(range(1,4), 3))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
排列算法
题目连接: next_permutation, prev_permutation
next_permutation
permutations: 不含有重复元素
permutations II: 含有重复元素, 用 next_permutation 可以直接解决
permutations sequence 快速找到第 $k$ 个排列
python 的排列函数:1
2
3import itertools
return list(itertools.permutations(nums)) # itertools 返回的是迭代对象, 因此需要将其转换成list
return list(itertools.permutations(nums, r)) # itertools 返回的是迭代对象, 因此需要将其转换成list, r 代表排列的长度
问题
给定一个排列 P, 求出其后(前)一个排列 P+1(P-1), 关于次知识点的算法题可见Permutations
next_permutation
首先要知道, 这里的 “上一个” 和 “下一个” 是按照字典序的定义进行排序的, 因此对于 “123” 或者 “abc” 这样的字符串, 正序排列就被认为是 最小的或者最前面的 的排列(如 “123”), 而逆序排列被认为 最大的或者最后面的 的排列. 从字典序的角度出发, 当用排列 P 求下一个排列 P+1 时, 我们需要找到 刚好比当前排列大一位 的下一个排列.
因为我们已经知道逆序是最大的排列, 因此, 为了找到比当前排列刚好大一点的排列, 我们首先需要找到一个使排列为 非逆序 的元素, 因此, 我们从后往前找, 找到首个构成非逆序排列的元素, 即要满足 nums[i] < nums[i+1] 的元素 nums[i].
找到该元素后, 为了让新的排列只比当前排列大一位, 我们要将 i 之后的元素中大于 nums[i] 的所有元素中 最小的 那一个, 假设为 nums[j], 令 nums[j]与 nums[i] 位置互换, 注意, 如果不是最小的, 那么互换后一定会变得过大, 因为还存在介于二者之间的排列.
当 nums[j] 与 nums[i] 位置互换后, 由于在 i 之后, j 之前(注意此时已经互换), 仍然 可能 存在比 nums[j] (因为互换了, 所以此时的 nums[j] 是较小的那个元素) 大的其他元素, 因此, 说明在新排列和旧排列之间还存在有其他的排列. 为了使新排列只比旧排列大一位, 我们需要将 [i+1, end] 之内的元素逆置, 逆置后排列刚好比当前的排列大一位. 因为 j 之后的元素都是比原来的 nums[j] 和 nums[i] 小的, j 之前的元素都不小于原来的 nums[j], 并且大于原来的 nums[i], 因此, 逆置后的排列一定是最小的那一种, 故而可以组成只比当前排列大一位的下一个排列, 代码实现可能的版本如下( “321” 的下一个排列是 “123”, 但是会返回 false):
1 | class Solution { |
注意: next_permutation() 函数接受的是迭代器参数, 所以上面的实现只是一种参考, 并非是 STL 源码实现
1 | # python 实现 |
prev_permutation
对于 prev_permutation() 函数的原理原始差不多的, 只不过我们需要找到的是 只比当前排列小一位的前一个排列, 代码示例如下:
1 | bool prevPermutation(vector<int>& nums) { |
1 | # python 实现 |
046. Permutations
全排列, 注意是distict的数字, 故而不需要进行重复检查
Description: 不含重复数字的全排列
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解法一: 递归
时间复杂度: $O(A^n_n)$ , 每一种情况都是 $O(1)$ , 共有 $O(A^n_n)$ 种情况. (对吗?)
用一个变量pos指向nums的第一个位置, 然后将pos与后面所有位置上的数字交换(包括自己), 最终会得到n种可能性, 这n种可能性就是出现在第一位置上的所有可能字符的情况集合, 然后将第一位固定, 并将pos指向下一位, 此时问题转换成了n-1个字符的全排列, 按照这种想法一致递归下去, 就可以找到所有位置上的所有组合情况(用pos==nums.size()判断)
1 | class Solution { |
解法二: 迭代
时间复杂度: $O(n^3)$
空间复杂度: $O(A_n^n)$ 全排列的size
对于n个数的全排列问题, 可以想象成已经获得了n-1个数的全排列, 然后将第n个数插入到n-1个数的n个空位上( 如将3插入到12的空位上分别为: 312,132,123).
Python 实现:1
2
3
4
5
6
7
8
9
10
11
12
13class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = [[]]
for i in range(n):
sub_res = [] # 存在中间结果
for item in res: # 已经得到前 i-1 个元素排列的结果
temp = []
for k in range(len(item)+1): # 将第 i 个元素插入到前 i-1 个元素形成的排列中的各个位置
temp.append(item[:k] + [nums[i]] + item[k:])
sub_res.extend(temp)
res = sub_res # 更新成前 i 个元素的排列结果
return res
C++实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int>> res(1,vector<int>());
for(int i=0; i<num.size(); i++){
vector<vector<int>> tmp_res(std::move(res)); // move之后, res内部会自动被清空, 而且move的效率较高
for(int j=0; j<tmp_res.size(); j++){
for(int k=0; k<=tmp_res[0].size(); k++){ // 注意这里是<=, 因为还要往尾部插
vector<int> tmp(tmp_res[j]);
tmp.insert(tmp.begin()+k, num[i]);
res.push_back(tmp);
}
}
}
return res;
}
};
解法三: 利用C++的内置函数 next_permutation
关于 next_permutation() 的详细解析请看这里
STL中的 next_permutation 函数和 prev_permutation 两个函数提供了对于一个特定排列P, 求出其后一个排列P+1和前一个排列P-1的功能.
1 | class Solution { |
这道题利用 prev_permutation 也可以解决, 但是这里就多了一步 reverse 的操作, 这里贴出来只是帮助理解 STL 函数的内部实现, 对于 Permutation2 题也是同理:1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end(), greater<int>()); // 倒序排序
do{
res.push_back(nums);
}while(prev_permutation(nums.begin(), nums.end()));//使用 prev
return res;
}
};
解法四: 自己实现 next_permutation
用迭代器作为参数:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
template <typename T>
bool nextPermutation(T first, T last) {
auto i = last - 2;
auto j = last - 1;
while (i >= first && *i >= *(i+1)) i--;
if (i >= first) {
while (j >= first && *i >= *j) j--;
std::iter_swap(i, j);
std::reverse(i+1, last);
}
return i>=first ? true : false;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> res;
do {
res.push_back(nums);
} while (nextPermutation(nums.begin(), nums.end()));
return res;
}
};
用数组作为参数:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
private:
bool nextPermutation(vector<int>& nums) {
int n=nums.size();
int i = n-2, j = n-1;
while(i>=0 && nums[i]>=nums[i+1]) i--;
if(i>=0){
while(j>=0 && nums[i]>=nums[j]) j--;
swap(nums[i], nums[j]);
}
reverse(nums.begin()+i+1, nums.end());
return i>=0 ? true : false;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
do{
res.push_back(nums);
}while(nextPermutation(nums));
return res;
}
};
prev_permutation 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
private:
bool prevPermutation(vector<int>& nums) {
int n=nums.size();
int i = n-2, j = n-1;
while(i>=0 && nums[i]<=nums[i+1]) i--;
if(i>=0){
while(j>=0 && nums[i]<=nums[j]) j--;
swap(nums[i], nums[j]);
}
reverse(nums.begin()+i+1, nums.end());
return i>=0 ? true : false;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end(), greater<int>());
do{
res.push_back(nums);
}while(prevPermutation(nums));
return res;
}
};
next_permutation python 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = n - 2
j = n - 1
while (i >= 0 and nums[i] >= nums[i+1]): i -= 1 # 找到i
if (i >= 0):
while (j > i and nums[i] >= nums[j]): j -= 1 # 找到 j
nums[i], nums[j] = nums[j], nums[i] # 交换, 并将 i 之后的进行逆置
nums[i+1:] = nums[i+1:][::-1]
return True if i != -1 else False
def permute(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
res.append(nums.copy()) # 注意这里一定要用copy, 否则后续的更改会影响前面的nums的值
while(self.nextPermutation(nums)):
res.append(nums.copy())
return res
prev_permutation python 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def prevPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = n - 2
j = n - 1
while (i >= 0 and nums[i] <= nums[i+1]): i -= 1 # 找到i
if (i >= 0):
while (j > i and nums[i] <= nums[j]): j -= 1 # 找到 j
nums[i], nums[j] = nums[j], nums[i] # 交换, 并将 i 之后的进行逆置
nums[i+1:] = nums[i+1:][::-1]
return True if i != -1 else False
def permute(self, nums: List[int]) -> List[List[int]]:
nums.sort(reverse=True)
res = []
res.append(nums.copy()) # 注意这里一定要用copy, 否则后续的更改会影响前面的nums的值
while(self.prevPermutation(nums)):
res.append(nums.copy())
return res
解法五: 回溯
在进行回溯时, 每次将当前选择的字符串剔除, 当递归到当前可选字符数为 0 时, 代表找到了其中一种排列. 代码如下
1 | class Solution: |
047. 全排列 II
Description: 带有重复元素的全排列
解法一: 递归+set
时间复杂度:
空间复杂度:
set 插入元素的时间复杂度为 $O(logn)$, $n$ 为当前 set 的大小.
1 | class Solution { |
解法二: STL 的 next_permutation 函数
关于 next_permutation() 的详细解析请看这里
1 | class Solution { |
使用 prev_permutation() 也可解决, 不过需要记得要倒序排序.1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end(), greater<int>()); // 倒序排序
do{
res.push_back(nums);
}while(prev_permutation(nums.begin(), nums.end())); // prev
return res;
}
};
解法三: 自己实现 next_permutation()
python 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def nextPermutation(nums):
n = len(nums)
i = n - 2
j = n - 1
while (i >= 0 and nums[i] >= nums[i+1]): i -=1
if (i>=0):
while (j > i and nums[i] >= nums[j]): j -=1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1:] = nums[i+1:][::-1]
return True if i != -1 else False
nums.sort()
res = []
res.append(nums.copy())
while (nextPermutation(nums)):
res.append(nums.copy())
return res
用迭代器做参数:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
template <typename T>
bool nextPermutation(T first, T last) {
auto i = last - 2;
auto j = last - 1;
while (i >= first && *i >= *(i+1)) i--;
if (i >= first) {
while (j >= first && *i >= *j) j--;
std::iter_swap(i, j);
std::reverse(i+1, last);
}
return i>=first ? true : false;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> res;
do {
res.push_back(nums);
} while(nextPermutation(nums.begin(), nums.end()));
return res;
}
};
用数组做参数:
1 | class Solution { |
解法四: 回溯+排序去重
1 | class Solution: |
- 第 k 个排列
题目链接: https://leetcode-cn.com/problems/permutation-sequence/
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: “213”
示例 2:
输入: n = 4, k = 9
输出: “2314”
解法一: 从高位到低位逐个确定
Python 实现:
1 | class Solution: |
网易笔试, 给出第 K 个排列, 求倒数第 K 个排列
[1, 2, 3] 全排列如下:1
2
3
4
5
6[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
题目给出第 K 个排列, 要求输出倒数第 K 个排列.
解法: 最大变最小, 次大变次小.
例如: 给出 [1, 3, 2], 则将最小的 1 换成最大的 3, 最大的 3 换成最小的 1, 次大的 2 换成次大的 2, 于是, 倒数第 K 个排列为 [3, 1, 2]
permutation sequence
给定 $n$, 则 [1, 2, ..., n] 可能的排列有 $n!$ 种, 要求你快速找到第 $k$ 个排列. 该题目用 next_permutatioin 或者 prev_permutation 求解时会严重超时. 下面给出正确思路
对于 [1,2,3,4]来说, 所有的排列可以分为下面 4 种情况:
- 1 + [2,3,4]
- 2 + [1,3,4]
- 3 + [1,2,4]
- 4 + [1,2,3]
因为, 我们可以利用 $k / (n-1)!$, 确定第一个数字的取值, 然后对于剩下的数字, 迭代的使用该方法确定, 知道确定了所有的 $n$ 个数字为止, 代码实现如下所示:
1 | import math |
组合算法
题目链接:
Combinations: 给定 $n$ 和 $k$, 返回所有可能的 $k$ 元组
Combinations Sum I:返回和为 target 的组合, 数列中的元素可以使用无限次
Combinations Sum II: 返回和为 target 的组合, 数列中的元素可以只可以使用一次
Combinations Sum III: 返回和为 target 的 k 元组, 只可以使用 1~9 的数字
Combinations Sum IV: 返回和为 target 的所有可能情况的个数, 数列中的元素可以使用无限次
1 | import itertools |
Combinations
Combinations: 给定 $n$ 和 $k$, 返回所有可能的 $k$ 元组
解法一: 递归
对于给定的 $n$ 和 $k$, 我们可以先确定一个数字, 该数字一定处于当前数列中的第 $k$ 个到最后一个中, 然后, 对于剩下的 $k-1$ 个数字, 我们可以在选定的数字前面的数列中进行选取, 此时就形成了一个新的给定 $i-1$, $k-1$ 的组合问题.
1 | class Solution: |
解法二: 迭代
迭代的核心思想就是要控制 i 的范围, 使其刚好处在可以与现有 res 中元素形成组合, 有两种不同的实现角度(思路一致, 只不过一个是从前往后组合, 一个是从后往前组合)
1 | # 从前往后组合 |
1 | # 从后往前组合 |
解法三: 回溯
1 | class Solution: |
Combinations Sum I
Combinations Sum I:返回和为 target 的组合, 数列中的元素可以使用无限次, 数列中的数 全部是正数
如果有负数存在, 会有什么问题? 答: 会出现无限长的解, 例如: [-1, 1, -1, 1, …]
1 | Input: candidates = [2,3,5], target = 8, |
解法一: 回溯
下面使用了 sort() 进行排序
1 | class Solution: |
实际上可以不使用 sort, 此时注意当nums[i] > target时, 我们不能直接break, 因为后面还存在其他可能的解, 因此, 需要用continue1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(nums, target, index, path, res):
if (target == 0):
res.append(path)
return
for i in range(index, len(nums)):
if (nums[i] > target):
continue
backtrack(nums, target - nums[i], i, path+[nums[i]], res)
res = []
backtrack(candidates, target, 0, [], res)
return res
Combination Sum II
Combinations Sum II: 返回和为 target 的组合, 数列中的元素可以只可以使用一次
1 | Input: candidates = [10,1,2,7,6,1,5], target = 8, |
解法一: 回溯
1 | class Solution: |
Combination Sum III
Combinations Sum III: 返回和为 target 的 k 元组, 只可以使用 1~9 的数字
解法一: 回溯
1 | class Solution: |
Combinations Sum IV
Combinations Sum IV: 返回和为 target 的所有可能情况的个数(需要用到排列, 该题认为 [1, 1, 2] 和 [2, 1, 1] 是不同的情况), 数列中的元素可以使用无限次
解法一: 回溯
由于该题将 [1, 1, 2] 和 [2, 1, 1] 看做是不同的情况, 因此, 在组合之后, 还要对每种组合进行排列, 但是这样的复杂度非常高, 例如 [1,1,1,1,1,1,1,1,1,,1,1…, 5], 所以该方法会超时
解法二: 动态规划
当我们求取某个值的可能组合数时, 我们可以利用前面已经求得的情况来简化. 如下所示
1 | class Solution: |
回溯
股票问题
卡特兰(catalan)数
定义
卡特兰数又称卡塔兰数, 英文名Catalan number, 是组合数学中一个常出现在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名, 其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …
卡特兰数 $Cn$ 满足以下递推关系:
- $C_{n+1} = C_0 C_n + C_1 C_{n-1} + … + C_n C_0$
- $(n-1)C_n = \frac{n}{2} (C_3C_{n-1} + C_4 C_{n-2} + C_5 C_{n-3} + … + C_{n-2}C_4 + C_{n-1} C_3)$
其他符合卡特兰数的特征:
- 令 $h(0)=1, h(1)=1$, 卡特兰树满足递推式:
- 卡特兰数满足递推式: $h(n) = \frac{4n-2}{n+1} h(n-1)$, 写代码时多用: $h(n+1) = \frac{4n+2}{n+2} h(n)$
- 卡特兰数的解为: $h(n) = \frac{1}{n+1} C_{2n}^{n}$
- 卡特兰数的解为: $h(n) = C_{2n}^{n} - C_{2n}^{n-1}$
常见题型
0-1 类
n 个 0 与 n 个 1 随机组合, 要求从左到右数时, 确保每一个数之前 0 的个数不少于 1 个个数.
解: 考虑 n 对 01, 先固定一对 01, 然后, 在这对的前面, 所有的子序列都是符合要求的, 因此, 结果为: 0 对 n-1 对 + 1 对 n-2 对 + 2 对 * n-3 对…., 所以这是一个卡特兰数.
实际题型举例:
- 括号化问题。一个合法的表达式由()包围, ()可以嵌套和连接, 如(())()也是合法 表达式；现在有 n 对(), 它们可以组成的合法表达式的个数为
- 矩阵连乘： P=a1×a2×a3×……×an, 依据乘法结合律, 不改变其顺序, 只用括号表示成对的乘积, 试问有几种括号化的方案
- 出栈次序问题. 一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列
- 在图书馆一共 2n 个人在排队, n 个还《面试宝典》一书, n 个在借《面试宝典》一书, 图书馆此时没有了面试宝典了, 确保所有人都能借到书, 求他们排队的总数
2n 个人排队买票, 其中 n 个人持 50 元, n 个人持 100 元。每张票 50 元, 且一人只买一张票。初始时售票处没有零钱找零。请问这 2n 个人一共有多少种排队顺序, 不至于使售票处找不开钱
$n\times n$ 的方格地图中, 从一个角到另外一个角, 不跨越对角线的路径数
多边形类
将多边行划分为三角形问题。将一个凸N+2多边形区域分成三角形区域的方法数?类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线, 那么有多少条可能的道路？类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数
二叉树类
给顶节点组成二叉树的问题。给定N个节点, 能构成多少种不同的二叉树
固定根节点, 所有的情况为 左边的情况 右边的情况. 故而, 所以最终为: 0 n-1 对 + 1 n-2 对 + 2 n-3 对 + … , 所以也是卡特兰数.
不同的二叉搜索树: https://leetcode-cn.com/problems/unique-binary-search-trees/
贪心
045. 跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
这道题用 DP 解会超时
解法一: 贪心(最优)
时间复杂度: $O(n)$
空间复杂度: $O(1)$
对于每一点i来说, 它可以只用一步达到i+nums[i]中的任意一点, 此时我们设置一步边界为cur_right, 如果某一次走到位置j, 并且该位置正好是边界cur_right, 则说明, 下一次, 无论我们怎么走, steps都必须要增加, 所以此时, 我们更新steps++, 并且更新cur_right为当前只利用steps步能达到的最远距离. 代码如下
1 | class Solution: |
055. 跳跃游戏-中等
数组的数字为最大的跳跃步数, 根据数组判断是否能跳到最后一位上
Description
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
解法一: 回溯
时间复杂度: $O(2^n)$ 总共有 $2^n$ 种跳法来跳到最后一个位置上(对于任意一个位置, 有经过和不经过两个种可能性)
空间复杂度: $O(n)$
试遍所有的可能性, 正常来说会超时, 并且也肯定不是最佳答案
1 | class Solution { |
解法二: top-down 动态规划(递归)
时间复杂度: $O(n^2)$ , 对于每个点来说, 都是要找到下一个good_position, 则需要进行 $(O)$ 的查找, 又因为总共有 $O(n)$个元素, 所以复杂度为 $O(n^2)$.
空间复杂度: $O(2n)$, 递归需要 $O(n)$ , memo需要 $O(n)$.
设计一个数组, 用来记录当前下标对应位置是否可又达到终点, 如果能, 则该位置为good position, 如果不能, 则为bad position, 刚开始的时候都是unknown position(除了最后一个位置为good).
1 | class Solution { |
解法三: down-top 动态规划(非递归)
时间复杂度: $O(n^2)$ , 对于每个点来说, 都是要找到下一个good_position, 则需要进行 $(O)$ 的查找, 又因为总共有 $O(n)$个元素, 所以复杂度为 $O(n^2)$.
空间复杂度: $O(n)$, 无需递归 , 只需要memo, $O(n)$.
动态规划的非递归版本.
1 | class Solution { |
解法四: 贪心-O(n) 复杂度, 最优
时间复杂度: $O(n)$
空间复杂度: $O(1)$
由上面的down-top递归可以看出, 当前下标位置的点是否为good点, 实际上只取决于当前点是否能够达到右边坐标中(从右往左走)最左边的good(可以看上面的break语句), 如果能够达到, 则当前点一定为good点, 因此, 我们只需要用一个变量left_most_good来维护当前点右边的最左good点下标即可, 无需任何其他空间和操作.(速度极快)
从后往前: Python 实现1
2
3
4
5
6
7
8
9class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
left_most = n-1
for i in range(n-2, -1, -1):
max_step = min(i+nums[i], n-1)
if max_step >= left_most:
left_most = i
return left_most == 0
从后往前: C++ 实现1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
bool canJump(vector<int>& nums) {
int left_most_good = nums.size()-1;
for(int i = nums.size()-2; i>=0; i--){
if(i+nums[i] >= left_most_good){
left_most_good = i;
}
}
return left_most_good==0;
}
};
另一种贪心的形式: 记录当前能够达到的最大位置
从前往后: Python 实现1
2
3
4
5
6
7
8
9class Solution:
def canJump(self, nums: List[int]) -> bool:
right_most = 0 # 当前能达到的最大的位置
for i in range(len(nums)):
if right_most < i: # 如果不可达当前点, 则后面的点均不可达
break
if i+nums[i] > right_most: # 更新能到达的最大位置
right_most = i+nums[i]
return right_most >= len(nums)-1 # 返回最大的位置是否包含最后的节点
从前往后: C++ 实现1
2
3
4
5
6
7
8
9class Solution {
public:
bool canJump(vector<int>& nums) {
int i =0;
for(int reach=0; i<nums.size() && i<=reach; i++ )
reach = max(i+nums[i], reach);
return i==nums.size(); // 或者用 reach >= nums.size()-1 判断
}
};
二分
lower_bound
返回有序数组中首个 大于等于 指定元素的下标
1 | def lower_bound(nums, target): |
upper_bound
返回有序数组中首个 大于 指定元素的下标
设置两个指针, 一个指向起始点, 一个指向超尾, 当二者相遇时, 循环终止, 对于 mid=(low+high)//2, 有两种情况:
- nums[mid] <= target: 说明比 target 大的数字在后面, 令 low = mid+1
- 反之: 当前的 nums[mid] 已经大于 target, 令 high = mid.
1 | def upper_bound(nums, target): |
笔试注意事项
处理输入
Python1
2
3
4
5
6
7
8input() # 仅读取一行, 并且不会读取最后的换行符
sys.stdin.readline() # 仅读取一行, 并且会读取到最后的换行符
# 上述两种读取方式都可以用 split 来将形如 1 2 3 4 的输入进行拆分
sys.stdin.readlines() # 读取多行, 会读取换行符, 需要利用 ctrl+d+enter 或者 ctrl+z+enter 终止
# 注意, 以上三种方法读入的都是字符串, 因此在进行数值型计算或者比较时, 一定要强制转换类型
Python 常见坑
range的参数只能是int. 注意除法运算后的结果通常float:1
2
3a = 10 / 2
for i in range(a): # 报错, a 是 float
print(i)
在嵌套定义函数时, 内部函数可以使用外部函数的变量, 但是只能访问它, 不能改变它, 因为一旦改变, 实际上是新声明了变量, 外部变量变的不可见, 如下所示
合法:1
2
3
4
5
6def test():
def t():
print(a)
a = 1
t()
test()
不合法:1
2
3
4
5
6
7def test():
def t():
a += 1
print(a)
a = 1
t()
test()
笔试常见坑
数字相乘后超出 int 范围, 能用 long long 就用 long long
python 的 sys.stdin.readline().split() 读入的都是字符串, 因此在进行比较时需要注意字符串的比较和数字类型的比较的区别.
python 的 append 方法是对列表直接操作, 不会返回任何结果(返回 None)
python 的for i in range语法的每一次迭代都是基于 range 的, 不会被内部改变, 如下所示, 下面三段程序的输出是一模一样的.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 for i in range(10):
if i % 2 == 0:
i += 1
continue
print(i)
for i in range(10):
if i % 2 == 0:
continue
print(i)
for i in range(10):
if i % 2 == 0:
i = 3
continue
print(i)
笔试题-华为
华为真正的文化核心：以客户为中心，以奋斗者为本，长期坚持艰苦奋斗！