背包-排序-剑指

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：

背包问题

先循环物品
再循环体积
最后循环决策

01背包

二维动态规划

f[i][j] 表示只看前i个物品， 总体积是j的情况下，总价值最大是多少。

result = max {f[n][0-v]}

f[i][j] =

1.不选第i个物品， f[i][j] = f[i - 1][j];
2.选第i个物品， f[i][j] = f[i - 1][j - v[i]] + w[i];

f[i][j] = max{1, 2}

f[0][0] = 0;

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

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int v[N], w[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			if (j >= v[i])
				f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}


	cout << f[n][m] << endl;
	return 0;
}

滚动数组

关于背包问题的初始化。

  1. 恰好装满背包时的最优解。初始化时f[0] = 0, 其余初始化为-INF。
  • 初始化数组f 就是在没有任何物品可以放入背包时的合法状态， 如果要求背包恰好装满，那么此时只有容量为0的背包可以在没有东西放入的情况下“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态。
  1. 背包不是必须装满，只希望价值尽量大。 初始化时f数组全为0

后面输出最大价值时 选择f[m]

这是因为我们把f[N]数组初始化为0了， 即得到最优解时背包不一定是满的。
如果把f[0]初始化为0， 其余为-INF， 这样得到的最优解就是背包恰好装满时的最优解了， 此时最大值就不一定是数组最后一个元素了。

初始化方式： 不超过背包容量时的最大值就是最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;

int f[N];
int v, w;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> v >> w;
        for (int j = m; j >= v; j--)
            f[j] = max (f[j], f[j - v] + w);
    }
   
    cout << f[m] << endl;    
  
    return 0;
}

初始化方式：恰好装满背包时 ， 这时 最大值就不是最后一个元素了。

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, INF = 1000000;

int n, m;

int f[N];
int v, w;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) f[i] = -INF;
    for (int i = 0; i < n; i++) {
        cin >> v >> w;
        for (int j = m; j >= v; j--)
            f[j] = max (f[j], f[j - v] + w);
    }
    int maxw = 0;
   for (int i = 0; i <= m; i++)  maxw = max (maxw, f[i]);
    cout << maxw << endl;    
  
    return 0;
}

完全背包

f[i] 表示 总体积是i的情况下， 最大价值是多少。

result = max{f[0 … m]} // m 是 最大体积

for (int i = 0; i < n; i++) {
for (int j = v[i]; j <= m; j++ )
f[j] = max (f[j], f[j - v[i]] + w[i]);
}

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



#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];  //滚动数组


int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int v, w;
		cin >> v >> w;
		for (int j = v; j <= m; j++)
			f[j] = max(f[j], f[j - v] + w);
	}

	cout << f[m] << endl;

	return 0;
}

多重背包

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
/*
f[i] 表示 总体积是i的情况下， 最大价值是多少。 (i表示当前背包的可用体积)

*/
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N];  //滚动数组


int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {             //循环1. 物品
		int v, w, s;
		cin >> v >> w >> s;
		for (int j = m; j >= v; j--)         //循环2   背包可用体积
			for (int k = 1; k <= s && k*v <= j; k++)  //循环3  每种物品的数量（后面二进制优化不要在这里进行）
				f[j] = max(f[j], f[j - k*v] + k*w);
	}

	cout << f[m] << endl;

	return 0;
}

多重背包的二进制优化方法

数据范围
0 < N <= 1000
0 < V <= 2000
0 < vi, wi, si <= 2000

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
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;

const int N = 2010;

int n, m;
int f[N];  //滚动数组

struct Good {
	int v, w;
};

int main() {
	vector<Good> goods;
	cin >> n >> m;
	//划分物品
	for (int i = 0; i < n; i++) {
		int v, w, s;
		cin >> v >> w >> s;
		for (int k = 1; k <= s; k *= 2) {
			s -= k;
			goods.push_back({ v * k, w * k });
		}
		if (s > 0) goods.push_back({ v * s, w * s });
		
	}
	// 01 背包
	for (auto good : goods) 
		for (int j = m; j >= good.v; j--)
			f[j] = max(f[j], f[j - good.v] + good.w);
	

	cout << f[m] << endl;

	return 0;
}

混合背包

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

#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;

const int N = 1010;

int n, m;
int f[N];  //滚动数组

struct Thing {
	int kind;
	int v, w;
};
vector<Thing> things;


int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int v, w, s;
		cin >> v >> w >> s;
		if (s < 0) things.push_back({ -1, v, w });
		else if (s == 0) things.push_back({ 0, v, w });
		else {
			for (int k = 1; k <= s; k *= 2) { 
				s -= k;
				things.push_back({ -1, v * k, w * k });
			}
			if (s > 0) { 
				things.push_back({ -1, v * s, w * s });
			}
		}
	}

	for (auto thing : things) {
		if (thing.kind < 0) {  //01背包  （多重背包已转换成01背包）
			for (int j = m; j >= thing.v; j--) f[j] = max(f[j], f[j - thing.v] + thing.w);
		}
		else {  //完全背包
			for (int j = thing.v; j <= m; j++) f[j] = max(f[j], f[j - thing.v] + thing.w);
		}
	}
	

	cout << f[m] << endl;

	return 0;
}

二维费用背包

第一重循环 循环物品
第二重循环 循环体积
第三重循环 循环重量

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
/*
f[i][j]   当前可用体积是i重量是j时的最大价值。  从这个问题可以看出， 数组的i \  j实际上就是费用。



*/
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;

const int N = 1010;

int n, v, m;
int f[N][N];  //滚动数组




int main() {
	cin >> n >> v >> m;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int j = v; j >= a; j--)
			for (int k = m; k >= b; k--)
				f[j][k] = max(f[j][k], f[j - a][k - b] + c);
	}

	cout << f[v][m] << endl;

	return 0;
}

分组背包 （多重背包实际上是分组背包的特殊情况）

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int s;
int f[N], v[N], w[N];
/* 与01背包类似。

每组物品至多选一个，因此每组有s+1种决策（输入时要把该组物品一次性输入，因此需要用数组来存储）

   f[j] = max {f[j], f[j- v[0] + w[0], f[j - v[1]] + w[1], f[j - v[2]] + w[2],... f[j - v[s - 1]] + w[s - 1]}

*/

int main () {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int i = 0; i < s; i++) 
            cin >> v[i] >> w[i];
         for (int j = m; j >= 0; j--) 
            for (int k = 0; k < s; k++)
                if (j >= v[k])
                    f[j] = max(f[j], f[j - v[k]] + w[k]);
            
        
    }




    
    cout << f[m] << endl;
    
    
    return 0;
}

有依赖的背包

背包问题求方案数

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
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, mod = 1000000007, INF = 1000000;

int n, m;
int f[N], g[N];

int main() {
	cin >> n >> m;
	g[0] = 1;
	for (int i = 1; i <= m; i++) f[i] = -INF;
	for (int i = 0; i < n; i++) {
		int v, w;
		cin >> v >> w;
		for (int j = m; j >= v; j--) {
			int t = max (f[j], f[j - v] + w);
			int s = 0;
			if (t == f[j]) s += g[j];
			if (t == f[j - v] + w) s += g[j - v];
			if (s >= mod) s -= mod;
			f[j] = t;
			g[j] = s;
		}
	}


int maxw = 0;
for (int i = 0; i <= m; i++) maxw = max (maxw, f[i]);
int res = 0;
for (int i = 0; i <= m; i++)  
	if (maxw == f[i]) {
		res += g[i];
		if (res >= mod) res -= mod;
	}
cout << res << endl;
return 0;
}

背包问题求具体方案

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

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int v[N], w[N], f[N][N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

	for (int i = n; i >= 1; i--) 
		for (int j = 0; j <= m; j++) {
			f[i][j] = f[i + 1][j];
			if (j >= v[i]) f[i][j] = max (f[i][j], f[i + 1][j - v[i]] + w[i]);
		}

	int vol = m;
	for (int i = 1; i <= n; i++)
		if (f[i][vol] == f[i + 1][vol - v[i]] + w[i] && vol >= v[i]) {
			cout << i << ' ';
			vol -= v[i];
		}

	return 0;
}

排序

稳定：相同元素相对位置不变

冒泡排序

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
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

void bubble_sort(vector<int>& q) {
	for (int i = q.size() - 1; i > 0; i--) 
		for (int j = 0; j + 1 <= i; j++)
			if (q[j] > q[j + 1]) {
				swap(q[j], q[j + 1]);
			}
}

int main() {
	int n;
	vector<int> q;

	cin >> n;
	for (int i = 0, t; i < n; i++) {
		cin >> t;
		q.push_back(t);
	}
	 
	bubble_sort(q);

	for (auto x : q) cout << x << " ";
	cout << endl;

	return 0;
}

冒泡排序优化

加入一个标志变量， 当发生元素交换时改变flag状态， 一趟遍历完成后 检查flag ， 如果flag未改变， 说明这趟遍历没有元素逆序， 也就是说序列是有序的， 此时退出循环即可。 

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void bubble_sort (vector<int>& q) {
     for (int i = q.size() - 1; q > 0; q--) {
        bool flag = false;
        for (int j = 0; j + 1 <= i; j++) {
            if (q[j] > q[j + 1]) {
                swap(q[j], q[j + 1]);
                flag = true;
            }           
        }
        if (!flag) break;
    }
}

int main () {
    int n;
    cin >> n;
    vector<int> q;

    for (int i = 0, t; i < n; i++) {
        cin >> t;
        q.push_back(t);
    }

    bubble_sort(q);

    for (auto x : q) {
        cout << x << " "; 
    }

    return 0;
}

选择排序

1
2
3
4
5
6
7
8
9
void selectionSort(vector<int>& q) {
	for (int i = 0; i < q.size(); i++)     //i前面的数已经排好序了
		for (int j = i + 1; j < q.size(); j++) 
			if (q[i] > q[j])          //把当前最小的数放到i这个位置
				swap(q[i], q[j]); 
			
		
	
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertionSort (vector<int>& q) {

for (int i = 1; i < q.size(); i++) {
    int t = q[i], j;          
    for (j = i - 1; j >= 0; j--) {   //注意这些循环的起止条件
        if (q[j] > t) {
            q[j + 1] = q[j];
        } else break;               // 精髓啊！这个else 
    }
    q[j + 1] = t;
}

}

自己写这个插入排序时 在第二个for 循环处 又定义了一个 j， 于是 for循环结束后， nums[j + 1] = temp;这里就会报错， j没有初始化。

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void merge_sort (vector<int>& q, int l, int r) {
    if(l == r) return;     // l >= r 也可以

    int mid = (l + r) / 2; // l + r >> 1 也可以
    merge_sort(q, l, mid);          //先排序左半边， 再排序右半边
    merge_sort(q, mid + 1, r);

    static vector<int> w;
    w.clear();

    int i = l, j = mid + 1;

    while (i <= mid && j <= r)
        if (q[i] <= q[j])             // 这里注意 一定是 <= 才行
            w.push_back(q[i++]);
        else                            //else 很精髓
            w.push_back(q[j++]); 
    while (i <= mid) w.push_back(q[i++]);
    while (j <= r) w.push_back(q[j++]);   //把两个有序序列合并成了一个有序序列
    //注意下面的循环判断条件哪里， 用的是 j 
    for (i = l, j = 0; j < w.size(); i++, j++) q[i] = w[j];  // i从原序列的最左边开始， j从辅助数组的最左边开始。
}

快速排序

1
2
3
4
5
6
7
8
9
10
void quick_sort(vector<int>& nums, int l, int r) {   //r是数组最后一个元素的下标
	if (l >= r) return; // 这里是 ==  也行
	int i = l - 1, j = r + 1, x = nums[l + r >> 1];  // 这里pivot就选择是 mid 了
	while (i < j) {                                 // 使用 do while 循环 很精髓， 如果是用的while ,先判断再移动指针，当nums[i] == x 或 nums[j] == x 时 就会陷入死循环 ~
		do j--; while (nums[j] > x);               // do while 先执行 后判断
		do i++; while (nums[i] < x);
		if (i < j) swap(nums[i], nums[j]);
		else quick_sort(nums, l, j), quick_sort(nums, j + 1, r); //把递归写在循环外面也是可以的
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

void quick_sort(vector<int>& nums, int l, int r) {
	if (l >= r) return; // 这里是 ==  也行
	int i = l - 1, j = r + 1, x = nums[l + r >> 1];
	while (i < j) {
		do j--; while (nums[j] > x);               // do while 先执行 后判断
		do i++; while (nums[i] < x);
		if (i < j) swap(nums[i], nums[j]);  //i < j   i、j还没有相遇； 否则 i、j已经相遇， 即 比x小的已经放在了左边， 比x大的已经放在了右边
		
	}
	quick_sort(nums, l, j);
	quick_sort(nums, j + 1, r);
}

do while 语句

1
2
3
do {
    我上传题目；
} while (系统判断是否正确)；   // 注意循环操作 和  循环条件 后面都要跟上 分号

快速排序找数组中第k小的数字

每轮排序都有一个pivot就位， 判断一下这个pivot的下标是否为 k - 1， 如果是那么它就是第k小的数字， 否则向左/右递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int quick_sort(vector<int>& nums, int l, int r, int k) {
	if (l >= r) return nums[l];
	int i = l - 1, j = r + 1, x = nums[l];
	while (i < j) {
		do i++; while (nums[i] < x);
		do j--; while (nums[j] > x);
		if (i < j)
			swap(nums[i], nums[j]);
	}
	if (j == k - 1) return nums[j];
	else if (j > k - 1) 
		quick_sort(nums, l, j - 1, k);
	else
		quick_sort(nums, j + 1, r, k);

}

堆排序

完全二叉树：

大根堆 ： 根节点大于lc、 rc
小根堆 ： 根节点小于lc、 rc

堆中节点编号是按顺序排的， 如图

如果当前节点 编号为 u, 那么它的左儿子编号为 2u, 又儿子编号为2u + 1

如果我们改变了根节点的值， 执行push_down 操作
如果我们改变了叶节点的值， 执行push_up 操作
如果 改变了 中间几点的值， 执行push_down 和 push_up操作 （二者只会执行一个）

堆 的下标从 1 开始

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>

using namespace std;

void push_down(vector<int>& heap, int size, int u) {    //这里的size参数是个关键
	int t = u; // t是当前的最大值（根节点和lc , rc之间的）
	int left = u * 2, right = u * 2 + 1;
	if (left <= size && heap[left] > heap[t]) t = left; // 如果左儿子存在， 并且..
	if (right <= size && heap[right] > heap[t]) t = right;//如果右儿子存在, 并且..
	if (t != u) {//说明某个儿子的值 比 我大 了
		swap(heap[u], heap[t]);
		push_down(heap, size, t);
	}
}
void push_up(vector<int>& heap, int u) {
	while (u / 2 && heap[u / 2] < heap[u]) {        // u / 2 就是 当前节点父节点的编号
		swap(heap[u / 2], heap[u]);
		u /= 2;
	}
}
/*
void insert(vector<int>& heap, int size, int x) {
	heap[++size] = x; // 插入一个元素， 把它放到最后面即可
	push_up(heap, x);
}

void remove_top(vector<int>& heap, int& size) { // 删除堆顶元素
	heap[1] = heap[size]; //用最后一个元素覆盖堆顶元素即可 
	size--;
	push_down(heap, size, 1);
}
*/
void heap_sort(vector<int>& nums, int size) {
	int n = size;
	for (int i = 1; i <= n; i++) push_up(nums, i);  //建堆
	for (int i = 0; i < n - 1; i++) {  //注意这里 控制条件 是 n  ，与后面nums的下标不能是一个变量(//每循环一次， 就有一个数就位,因此要循环nums.size() - 1次)
		swap(nums[1], nums[size]); // 把最大值放到最后
		size--;
		push_down(nums, size, 1);
	}
}

int main() {
	int n, t;
	vector<int> nums;
	cin >> n;
	nums.resize(n + 1);  //记一下这个函数
	for (int i = 1; i <= n; i++) cin >> nums[i];  // 堆 下标从1 开始
	/*for (int i = 0; i < n; i++) {
		cin >> t;
		nums.push_back(t);
	}
	*/
	//bubble(nums);
	//selection_sort(nums);
	//insertion_sort(nums);
	//merge_sort(nums, 0, nums.size() - 1);
	//quick_sort(nums, 0, nums.size() - 1);
	heap_sort(nums, n);
/*
	for (auto x : nums)
		cout << x << ' ';
*/
	for (int i = 1; i <= n; i++)
		cout << nums[i] << ' ';
	return 0;
}

计数排序

1
2
3
4
5
6
7
8
9
10
11
// 从1开始是因为 上面堆排序的时候 改了输入格式。。。
void counting_sort(vector<int>& nums, int n) {
	vector<int> cnt(101, 0);
	for (int i = 1; i <= n; i++) cnt[nums[i]]++;

	for (int i = 1, k = 1; i <= 100; i++) 
		while (cnt[i]) {
			nums[k++] = i;
			cnt[i]--;
		}
}

桶排序

实现方法太多了。。。

1
2


基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int get(int x, int i) {    //辅助函数 ： 取当前数的第几位 （例如，i = 0 时  取x的 个位； i = 1 时 取x的 十位）
	while (i--) x /= 10;
	return x % 10;
}
// 假设所有数字 在三位数以内
// 这里nums 下标从1 开始 同样时因为上面堆排序改输入的原因
void radix_sort(vector<int>& nums, int n) {
	vector<vector<int>> cnt(10);  // 定义十个桶
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 10; j++) cnt[j].clear();

		for (int j = 1; j <= n; j++) // 按个位排序
			cnt[get(nums[j], i)].push_back(nums[j]);
		for (int j = 0, k = 1; j < 10; j++)  //循环不同数值 （0 ~ 9）
			for (int x : cnt[j])
				nums[k++] = x;
	}
}

下面是自己写了一遍排序

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

#include <iostream>
#include <vector>

using namespace std;

void bubble(vector<int>& nums) {
	int n = nums.size();
	bool flag = false;
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j + 1 <= i; j++) {
			if (nums[j] > nums[j + 1])
				swap(nums[j], nums[j + 1]);
			flag = true;
		}
		if (!flag) break;
	}


}
void selection_sort(vector<int> & nums) {
	int n = nums.size();
	for (int i = 0; i < n; i++)             //i前面的数字已经排好序了
		for (int j = i + 1; j < n; j++)
			if (nums[i] > nums[j])         //把最小元素放在第一位
				swap(nums[i], nums[j]);
}
void insertion_sort(vector<int> & nums) {
	int n = nums.size();

	for (int i = 1; i < n; i++) {
		int temp = nums[i], j;
		for (j = i - 1; j >= 0; j--) {
			if (nums[j] > temp)
				nums[j + 1] = nums[j];  // 注意是nums[j + 1] 而不是 nums[i]， 不要短视
			else
				break;                  //这个break 是精髓
		}
		nums[j + 1] = temp;
	}
}


void quick_sort(vector<int>& nums, int l, int r) {
	if (l == r) return; // >= 也可
	int i = l - 1, j = r + 1, x = nums[l + r >> 1];
	while (i < j) {      //while循环， 确保安置好一个pivot后 再 递归 左右。
		do j--; while (nums[j] > x);               // do while 先执行 后判断
		do i++; while (nums[i] < x);
		if (i < j) swap(nums[i], nums[j]);
		
	}
	quick_sort(nums, l, j);
	quick_sort(nums, j + 1, r);
}

void push_down(vector<int>& heap, int size, int u) {  //这里size是必不可少的
	int t = u; // t是当前的最大值（根节点和lc , rc之间的）
	int left = u * 2, right = u * 2 + 1;
	if (left <= size && heap[left] > heap[t]) t = left; // 如果左儿子存在， 并且..
	if (right <= size && heap[right] > heap[t]) t = right;//如果右儿子存在, 并且..
	if (t != u) {//说明某个儿子的值 比 我大 了
		swap(heap[u], heap[t]);
		push_down(heap, size, t);
	}
}
void push_up(vector<int>& heap, int u) {
	while (u / 2 && heap[u / 2] < heap[u]) {        // u / 2 就是 当前节点父节点的编号
		swap(heap[u / 2], heap[u]);
		u /= 2;
	}
}

void insert(vector<int>& heap, int size, int x) {
	heap[++size] = x; // 插入一个元素， 把它放到最后面即可
	push_up(heap, x);
}

void remove_top(vector<int>& heap, int& size) { // 删除堆顶元素
	heap[1] = heap[size]; //用最后一个元素覆盖堆顶元素即可 
	size--;
	push_down(heap, size, 1);
}

void heap_sort(vector<int>& nums, int size) {     
	int n = size;
	for (int i = 1; i <= n; i++) push_up(nums, i);  //建堆
	for (int i = 1; i <= n; i++) {  //注意这里 控制条件 是 n  ，与后面nums的下标不能是一个变量
		swap(nums[1], nums[size]); // 把最大值放到最后
		size--;                   
		push_down(nums, size, 1);     
	}
}
// 给定10^7 个数， 每个数都在 0~10^6之间
void counting_sort(vector<int>& nums, int n) {
	vector<int> cnt(101, 0);
	for (int i = 1; i <= n; i++) cnt[nums[i]]++;

	for (int i = 1, k = 1; i <= 100; i++)   //注意这里设置的 k
		while (cnt[i]) {
			nums[k++] = i;                  //注意这里的 k， i
			cnt[i]--;
		}
}

void bucket_sort(vector<int>& nums) {

}

int get(int x, int i) {
	while (i--) x /= 10;
	return x % 10;
}
// 假设所有数字 在三位数以内
// 由于上面用过堆排序...所以这里的输入是从1 开始的， 可自行更改
void radix_sort(vector<int>& nums, int n) {         //特别要注意后面索引用的是i 还是 j 还是 k...
	vector<vector<int>> cnt(10);  // 定义十个桶
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 10; j++) cnt[j].clear();

		for (int j = 1; j <= n; j++) // 按个位排序
			cnt[get(nums[j], i)].push_back(nums[j]);
		for (int j = 0, k = 1; j < 10; j++)
			for (int x : cnt[j])           // 这里用这个 range for 就很聪明了
				nums[k++] = x;
	}
}

int main() {
	int n, t;
	vector<int> nums;
	cin >> n;
	nums.resize(n + 1);  //记一下这个函数
	for (int i = 1; i <= n; i++) cin >> nums[i];  // 堆 下标从1 开始
	/*for (int i = 0; i < n; i++) {
		cin >> t;
		nums.push_back(t);
	}
	*/
	//bubble(nums);
	//selection_sort(nums);
	//insertion_sort(nums);
	//merge_sort(nums, 0, nums.size() - 1);
	//quick_sort(nums, 0, nums.size() - 1);
	//heap_sort(nums, n);
	//counting_sort(nums, n);
	radix_sort(nums, n);
/*
	for (auto x : nums)
		cout << x << ' ';
*/
	for (int i = 1; i <= n; i++)
		cout << nums[i] << ' ';
	return 0;
}

基于链表的排序

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// 基于链表的排序 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {} 
};

ListNode* merge2Lists(ListNode *l, ListNode *r) {
    ListNode *head = new ListNode(-1);
    ListNode *p = head;
    while (l && r) {
        if (l->val <= r->val) {
            p->next = l;
            l = l->next;
            p = p->next;
        } else {
            p->next = r;
            r = r->next;
            p = p->next;
        }
    }
    if (l) p->next = l;
    if (r) p->next = r;
    return head->next;
}
// 基于链表的归并 
ListNode* mergeSort(ListNode *list) {
    if (!list || !list->next) return list;

    ListNode *fast = list, *low = list;
    ListNode *pre = NULL;
    while (fast && fast->next) {
        pre = low;
        low = low->next;
        fast = fast->next->next;
    }
    pre->next = NULL;  // 断链！！ 
    ListNode *l = mergeSort(list);
    ListNode *r = mergeSort(low);
    return merge2Lists(l, r);
}

// follow up: 排序k个有序列表 
ListNode* mergeKLists(vector<ListNode*>& lists) {
    int m = lists.size();
    if (m == 0) return NULL;
    if (m == 1) return lists[0];

    int mid = m / 2;
    vector<ListNode*> left = vector<ListNode*>(lists.begin(), lists.begin() + mid);
    vector<ListNode*> right = vector<ListNode*>(lists.begin() + mid, lists.end());
    ListNode *l= mergeKLists(left);
    ListNode *r= mergeKLists(right);
    return merge2Lists(l, r);
}

// 基于链表的快排 
void swap(ListNode *p, ListNode *q) {
    int t = p->val;
    p->val = q->val;
    q->val = t;
}
void quick(ListNode *head, ListNode *end) {
    if(!head || head == end) return;

    ListNode *small = head, *p = head->next;

    while (p != end->next) {
        if (p->val < head->val) {
            small = small->next;
            swap(small, p);
        }
        p = p->next;
    }

    swap(head, small);
    quick(head, small);
    quick(small->next, end);
}
ListNode* quickSort(ListNode *head) {
    ListNode *end = head;
    while (end->next) end = end->next;

    quick(head, end);

    return head;
}
// 基于链表的插入排序
ListNode* insertionSortList(ListNode* head) {
    ListNode *dummy = new ListNode(-1);
    while (head) {
        ListNode *next = head->next;
        ListNode *p = dummy;
        while (p->next && p->next-> val <= head->val) p = p->next;

        head->next = p->next;
        p->next = head;

        head = next;
    }
    return dummy->next;
}

void print(ListNode *head) {
    ListNode *p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    } 
    cout << endl;
}
int main() {
    vector<int> nums = {3, 2, 1, 5, 3, 3, 7, 6, 7, 9, 8, 10};
    //for (int x : nums) cout << x << " "; cout << endl;

    //bubble_sort(nums);
    //selection_sort(nums);
    //insert_sort(nums);
    //heap_sort(nums);
    //quick_sort(nums);
    //merge_sort(nums);

    ListNode *list = new ListNode(nums[0]);
    ListNode *p = list;
    for (int i = 1; i < nums.size(); ++i) {
        p->next = new ListNode(nums[i]);    
        p = p->next;
    }

    print(list);
    ListNode *res = quickSort(list);
    print(list);

    //for (int x : nums) cout << x << " "; cout << endl;
}

剑指offer

不修改数组找出重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1; // 划分的区间：[l, mid], [mid + 1, r]
            int s = 0;
            for (auto x : nums) s += x >= l && x <= mid;
            if (s > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        if (head == nullptr) return res;
        
        while(head != nullptr) {
            res.push_back(head->val);
            head = head->next;
        }
        
        return vector<int>(res.rbegin(), res.rend());
    }
};

这里没有用stack， 而是使用了反向迭代器
c.rbegin() 返回一个逆序迭代器，它指向最后一个元素。
c.rend() 返回一个逆序迭代器，它指向第一个元素的前面一个位置。

重建二叉树 VLR LVR

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
/**
 * 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:
    map<int, int> hash;
    vector<int> preorder, inorder;
    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder = _preorder; 
        inorder = _inorder;
    
    for (int i = 0; i < inorder.size(); i ++) hash[inorder[i]] = i;
    return dfs (0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* dfs (int pl, int pr, int il, int ir) {
        if (pl > pr) return nullptr;
        auto root = new TreeNode(preorder[pl]);
        int k = hash[root->val];
        auto left = dfs (pl + 1, pl + k - il, il, k - 1);
        auto right = dfs (pl + k - il + 1, pr ,k + 1 ,ir);
        root->left = left;
        root->right = right;
        return root;
    }
};

二叉树的下一个节点

找个二叉树的图， 两种情况

  • 我有右子树，那么我的后继就是我的右子树最左的哪个节点；
  • 我没有右子树，如果我是我father的左儿子，那么我的后继就是我father的father
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
        if (p->right) {
            p = p->right;
            while (p->left) p = p->left;
            return p;
        }
        while (p->father && p == p->father->right) p = p->father;
        return p->father;
    }
};

矩阵中的路径

在深度优先搜索中，最重要的就是考虑好搜索顺序。
我们先枚举单词的起点，然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。

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
class Solution {
public:
    bool hasPath (vector<vector<char>>& matrix, string str) {
        for (int i = 0; i < matrix.size(); i++)
            for (int j = 0; j < matrix[0].size(); j++)
                if(dfs (matrix, str, 0, i, j)) 
                    return true;
        return false;
    }
    bool dfs (vector<vector<char>>& matrix, string& str, int u, int x, int y) {
        if (matrix[x][y] != str[u]) return false;
        if (u == str.size() - 1) return true;

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //上、右、下、左
        char t = matrix[x][y];
        matrix[x][y] = '*';
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[0].size())
                if (dfs(matrix, str, u + 1, a, b)) return true;
        }
        matrix[x][y] = t;     //这里记得要回溯
        return false;
    }
};

旋转数组的最小数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        while (n > 0 && nums[n] == nums[0]) n--;
        if (nums[n] >= nums[0]) return nums[0];
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

机器人的运动范围

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
class Solution {
public:

    int get_sum(pair<int, int> p) {
        int s = 0;
        while (p.first) {
            s += p.first % 10;
            p.first /= 10;
        }
        while (p.second) {
            s += p.second % 10;
            p.second /= 10;
        }
        return s;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if (!rows || !cols) return 0;
        queue<pair<int,int>> q;
        vector<vector<bool>> st(rows, vector<bool>(cols, false));

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int res = 0;
        q.push({0, 0});
        while (q.size()) {
            auto t = q.front();
            q.pop();
            if (st[t.first][t.second] || get_sum(t) > threshold) continue; //直接进行下一次循环
            res ++ ;  //这个点可以选择
            st[t.first][t.second] = true; //标记一下，这个点走过了
            for (int i = 0; i < 4; i ++ ) {  //向 上、右、下、左 四个方向扩展
                int x = t.first + dx[i], y = t.second + dy[i];
                if (x >= 0 && x < rows && y >= 0 && y < cols)  //因为已经判断过第一个if中的两个条件，所以此处只需要判断是否在界内即可。
					q.push({x, y});  
            }
        }

        return res;
    }
};

倒数第k个节点

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 //倒数第k个节点 即  正数第 len - k + 1个节点 。
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        
        int len = 0;
        auto p = pListHead;
        while (p != nullptr) {
            p = p->next;
            len++;
        }
        if (k > len) return nullptr;
        p = pListHead;
       for (int i = 0; i < len - k; i++) p = p->next;  //往后挪len - k 次
        return p;
    }
};

之字形打印二叉树

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
/**
 * 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<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        vector<int> level;
        queue<TreeNode* > que;
        que.push(root);
        que.push(nullptr);
        bool direction = false;
        
        while (que.size()) {
            auto t = que.front();
            que.pop();
            
            if (t) {
                level.push_back(t->val);
                if (t->left) que.push(t->left);
                if (t->right) que.push(t->right);
                
            } else {
                if (que.size())que.push(nullptr);
                if (direction) reverse(level.begin(), level.end());  // reverse这个 记一下
                res.push_back(level);
                level.clear();
                direction = !direction;
            }
            
        }
        return res;
        
    }
};
  • s.end());```之后 s 中的内容就反向了
    1
    2
    3
    -```return vector<int> (s.rbegin(), s.rend()); ``` //带return的时候 不起变量名 直接构造。
    这个新建的vector 内容就是 s的反向了。。。
    或者``` vector<int> a (s.rbegin(), s.rend());

二叉搜索树的后序遍历序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs(0, seq.size() - 1);
    }
    bool dfs (int l, int r) {
        if (l >= r) return true;
        int root = seq[r];
        int k = l;
        while (k < r && seq[k] < root) k++;
        for (int i = k; i < r; i++)
            if (seq[i] < root)
                return false;
        return dfs(l, k - 1) && dfs(k, r - 1);
    }
};

与重建二叉树那道题一个思路。 这个题相当于是根据LVR和LRV构建二叉树。

二叉树中和为某一值的路径

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
/**
 * 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<vector<int>> res;
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root, sum);
        return res;
    }
    void dfs (TreeNode* root, int sum) {
        if (!root) return;
        path.push_back(root->val);
        sum -= root->val;
        if (!root->left && !root->right && !sum) res.push_back(path);
        dfs (root->left, sum);
        dfs (root->right, sum);
        path.pop_back();            //  这里记得 回溯一下？   
        
        
    }
};

递归调用的本质是一个压栈与出栈的过程

序列化二叉树

  • to_string(…) 数值类型转string
  • stoi \ stof \ stod string转数值类型
  • val = val * 10 + data[i] - ‘0’
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
51
52
53
54
55
56
57
58
59
60
/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s (root, res);
        return res;
    }
    void dfs_s (TreeNode* root, string& res) {
        if (!root) {
            res += "null "; // 这里后面有个空格
            return;
        }
        res += to_string(root->val) + ' ';
        dfs_s(root->left, res);
        dfs_s(root->right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d (data, u);
    }
    TreeNode* dfs_d (string data, int& u) {
        if (u == data.size()) return NULL;
        int k = u;
        while (data[k] != ' ') k++;
        if (data[u] == 'n') {
            u = k + 1;
            return NULL;
        }
        //考虑了负号
        int val = 0; 
        if (data[u] == '-') {
            u = u + 1;
            
            for (int i = u; i < k; i++) val = val * 10 + data[i] - '0';
            val = -val;
        } else {
            
            for (int i = u; i < k; i++) val = val * 10 + data[i] - '0'; //注意这里的操作
        }
       
        u = k + 1;
        auto root = new TreeNode(val);
        root->left = dfs_d(data, u); //此处，因为data是VLR的顺序， 所以左边的填完，就是右边的了。
        root->right = dfs_d(data, u);
        return root;
    }
};

数字排列 （可能包含重复数字）

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    
    vector<vector<int>> permutation(vector<int>& nums) {
        path.resize(nums.size());
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0, 0);
        return res;
    }
    
    void dfs (vector<int>& nums, int u, int start, int state) {
        if (u == nums.size()) {
            res.push_back(path);
            return;
        }
        if (!u || nums[u] != nums[u - 1]) start = 0;
        for (int i = start; i < nums.size(); i++) 
            if (!(state >> i & 1)) {   //看这个数的二进制表示中，第i位是不是1, 如果不是，说明这一位没有用过
                path[i] = nums[u];
                dfs (nums, u + 1, i + 1, state + (1 << i));    //这里 state + (1 << i)  是说把state的第i位从0 变成 了 1
            }        
    }
};

二进制判断第i位是不是1


例如 把1011的第i位（最右边是第0位， >>1 相当于倒数第二位 挪到了个位上） 挪到 个位上， 然后把这个 &1

1
2
3
int a = 11; // 二进制1011 ，      
cout << (a >> 2 & 1) << endl;  //输出0
cout << (a >> 1 & 1) << endl;   // 输出1

关于DFS与backtracing

  • I would say, DFS is the special form of backtracking; backtracking is the general form of DFS.

If we extend DFS to general problems, we can call it backtracking. If we use backtracking to tree/graph related problems, we can call it DFS.

They carry the same idea in algorithmic aspect.

  • I think this answer to another related question offers more insights.

For me, the difference between backtracking and DFS is that backtracking handles an implicit tree and DFS deals with an explicit one. This seems trivial, but it means a lot. When the search space of a problem is visited by backtracking, the implicit tree gets traversed and pruned in the middle of it. Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.

So, backtracking is DFS for implicit tree, while DFS is backtracking without pruning.

最小的k个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        vector<int> res;
        for (auto x : input) {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }
        while (k--) {
            res.push_back(heap.top());
            heap.pop();
        }
       // vector<int> ans(res.rbegin(), res.rend());
       // return ans;
       reverse(res.begin(), res.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
class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if (min_heap.size() && max_heap.top() > min_heap.top()) {
            auto maxv = max_heap.top(), minv = min_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }
        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }

    double getMedian(){
        if(max_heap.size() + min_heap.size() & 1 ) return max_heap.top();
        else return (max_heap.top() + min_heap.top()) / 2.0;    //这里用2.0是因为该函数返回值为 double
    }
};

连续子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {  // s表示以前一个数为结尾的子数组中，和最大的值
        int res = INT_MIN, s = 0;         //因为可能数组全为负数，因此把res初始化为负无穷。
        for (auto x : nums) {
            if (s < 0) s = 0;
            s += x;
            res = max (res, s);
        }
        return res;
    }
};

把数组排成最小的数

sort()函数 里比较方式采用自己定义的比较函数

当sort函数在类内使用，并且定义comp函数也是类成员函数时，必须要在comp函数前加static，因为sort需要传入的参数是一个普通函数指针，而不是成员函数指针，所以需要在类成员定义前加static。https://blog.csdn.net/qq_34489443/article/details/86219772

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    static bool cmp (int a, int b) {
        auto as = to_string(a), bs = to_string(b);
        return as + bs < bs + as;                      //字符串比较 是 字典序？
    }
    string printMinNumber(vector<int>& nums) {
        sort (nums.begin(), nums.end(), cmp);          
        string res;
        for (auto x : nums) res += to_string(x);
        return res;
    }
};

礼物的最大价值

这里注意dp数组是从1开始的。这样就不用考虑边界条件了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
       int n = grid.size(), m = grid[0].size();
       if (!n || !m) return 0;
       vector<vector<int>> dp(n + 1, vector<int>(m + 1));
       for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = max (dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
    
        return dp[n][m];
    }
};

两个链表的第一个公共节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while (p != q) {
            if (p) p = p->next;
            else p = headB;
            if(q) q = q->next;
            else q = headA;
        }
        return p;
    }
};

数字在排序数组中出现的次数

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
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        if (!nums.size()) return 0;
        
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < k) l = mid + 1;   //nums[mid] < k, 也就是说mid不是解， 右半边是解在的区间， mid在左半边， 选择模板1
            else r = mid;
        }
        if (nums[l] != k) return 0; // 如果k不是nums数组中的数。
        int left = l;
        l = 0, r = nums.size() - 1;
        
        
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > k) r = mid - 1; // nums[mid] > k, 也就是说 mid 不是解， 左半边是解在的区间， mid在右半边， 选择模板2
            else l = mid ;
        }
      
        
        return l - left + 1;
    }
};

如图所示， 我们要找到的就是图中的两个红点， 用二分查找找到这两个点。
对于left这个点来说， 我们要找到该点左边具有 而 右边 不具有的性质， 即 该点左边的数 小于 k。
对于right这个点来说， 它的右边的数 大于k。

0到n-1中缺失的数字

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        int n = nums.size() + 1;   // 这里注意一下 + 1
        int res = n * (n - 1) / 2;
        for (auto x : nums) res -= x;
        return res;
    }
};

数组中数值和下标相等的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] - mid >= 0) r = mid;
            else l = mid + 1;
        }
        if (nums[r] == r) return r;
        return -1;
    }
};

同样是采用二分法， 这里 nums[i] - i 单调增， 可以使用二分法。

二叉搜索树的第k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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:
    TreeNode* res;
    TreeNode* kthNode(TreeNode* root, int k) {
        dfs (root, k);
        return res;
    }
    void dfs (TreeNode* root, int& k) { // 递归调用中， 要注意传引用...
        if (!root) return;
        dfs (root->left, k);
        k--;
        if (!k) res = root;
        else dfs (root->right, k);
    }
};

二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 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:
   
    int treeDepth(TreeNode* root) {
        if (!root) return 0;
        return max (treeDepth(root->left), treeDepth(root->right)) + 1;
    }
    
};

左子树的最大深度 与 右子树的最大深度 中的最大值 加上 1 就是 整棵树的最大深度了。

平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        int a = abs(depth(root->left) - depth(root->right));
        if (a > 1) return false;
        return isBalanced (root->left) && isBalanced (root->right);
    }
    int depth (TreeNode* root) {
        if (!root) return 0;
        return max (depth(root->left), depth(root->right)) + 1;
    }
};

这个题注意 必须 每一层的节点都平衡 才是 平衡二叉树。

数组中只出现一次的两个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int sum = 0;
        for (auto x : nums) sum ^= x; // a^b
        int k = 0;
        while (!(sum >> k & 1)) k++; //a, b第k位不相同
        int first = 0;
        for (auto x : nums) 
            if (x >> k & 1) 
                first ^= x;
        int second = sum ^ first;
       
      
        return vector<int> {first, second};  // 花括号初始化
    }
};

异或

  • 相同的数异或 为 0
  • 不同的数异或为 1
    1^1 = 0
    1^0 = 1

解法步骤 ：

  1. 把 所有数 异或， 得到 x^y;
  2. x^y的第k位是1
  3. 对于每个数a 看他的第k位 是否为 1， 把是0的归为一个集合， 是1 的归为一个集合

反转单词顺序

首先我们看看怎么反转整个字符串， 用两个指针就可以了。

1
2
3
4
5
string s = "Harry potter!";
	for (int i = 0, j = s.size() - 1; i < j; i++, j--)
		swap(s[i], s[j]);

	cout << s << endl;

用操作分解的角度来做这题。
1.反转整个句子
2.反转每个单词

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        for (int i = 0; i < s.size(); i++) {
            int j = i;
            while (j < s.size() && s[j] != ' ') j++;
            reverse(s.begin() + i, s.begin() + j);    //[first, second)
            i = j;
        }
        return s;
    }
};

这里注意：
原型： void reverse(iterator first, iterator second);
功能： 颠倒区间[first, second)的次序

左旋转字符串

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    string leftRotateString(string str, int n) {
        int k = str.size();
        reverse(str.begin(), str.end());
        reverse(str.begin(), str.begin() + k - n);
        reverse(str.begin() + k - n, str.end());
        return str;  
    }
};

反转整个序列 gfedcba
分别反转前后两个序列 cdefgab

滑动窗口的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    //要不要加1 减1  可以 代入一个特殊值来判断
    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q; //双端队列里存放的是下标
        for (int i = 0; i < nums.size(); i++) {
            while (q.size() && q.front() <= i -k) q.pop_front(); //将滑出窗口的元素弹出（判断队首元素是否需要出队）
            while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();//维护队列单调性。如果队尾元素比新插入的那个小，那么它将永无出头之日...
            q.push_back(i); //把这个元素插入deque
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

滑动窗口用一个双端队列来做。

骰子的点数

dfs

dfs记住两点

  1. 状态的含义是什么
  2. 按照什么样的顺序递归，枚举所有方案
    dfs(n, s) 表示一共投了n次， 总和是s时， 方案数是多少

按照最后一次的选择，不重不漏划分为6个集合（所谓热狗法）。 按最后一次骰子点数为1、2、3、4、5、6 六种情况划分…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    //暴力搜索（dfs） 
   
    vector<int> numberOfDice(int n) {
        vector<int> res;
        for (int i = n; i < 6 * n; i++) {
            res.push_back(dfs(n, i));
        }
        return res;
    }
    int dfs (int n, int sum) {
        //首先设置两个边界条件
        if(sum < 0) return 0;
        if (n == 0) return !sum;
        
        int ans = 0;
        for (int i = 1; i <= 6; i++)   //最后一次骰子的点数
            ans += dfs(n - 1, sum - i);
        return ans;
    }
};

dp

  1. 状态表示 f[i][j] 前i次 总和是 j 的情况下 的 方案数
  2. 计算 这里可以用热狗划分，按照最后一次的情况划分为6个不相交的集合
  3. 边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    
        vector<int> numberOfDice(int n) {
        vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1)); //从1枚举到n所以 是n + 1
        f[0][0] = 1; //一次都不投的时候，只有总点数为0 时 有一种方案， 其他都不合法
        for (int i = 0; i <= n; i++) //先循环投的次数
            for (int j = 1; j<= i * 6; j++)//再循环 总点数
                for (int k = 1; k <= min(j, 6); k++) //最后循环最后一次的点数
                    f[i][j] += f[i - 1][j - k]; //最后f[i][j]的方案数就是 每种情况（最后一次骰子的点数k）的方案数之和
                    
        vector<int> res;
        for (int i = n; i <= n * 6; i++) res.push_back(f[n][i]);
        return res;

    }

};

实际上这是一个分组背包问题 （但是这个题每组物品都要选一个，不存在不选的情况）
n组 每组有物品 1、2、3、4、5、6 （每组物品只能选一个）

我们要凑出总和是 n-6n 所有的方案数

for 循环物品组
for 循环体积
for 循环决策
加和

扑克牌的顺子

这里使用的 vector back() 最后一个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    // 1. 去除所有0
    // 2. 重复元素
    // 3. 首尾元素之差 <= 4 
    bool isContinuous( vector<int> numbers ) {
        if (!numbers.size()) return false;
        sort(numbers.begin(), numbers.end());
        int k = 0;
        while (!numbers[k]) k++;  // 过滤掉所有的 0
        for (int i = k + 1; i < numbers.size(); i++) // 查看是否有重复的元素
            if (numbers[i] == numbers[i - 1])
                return false;
        return numbers.back() - numbers[k] <= 4;
    }
};

圆圈中剩下的数字

用list 模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
       
        list<int> nums;
        for (int i = 0; i < n; i++) nums.push_back(i);
        auto it = nums.begin();
        int k = m - 1;
        while (nums.size() > 1) {
            while (k--) {
                it++;
                if (it == nums.end()) it = nums.begin(); //把迭代器移到开头模拟环形列表
            }
            it = nums.erase(it);  //删除第m个元素
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();
    }
};

## 

1
2
3
4
5
6
7
8
class Solution {
public:
    int getSum(int n) {
        int res = n;
        n > 0 && (res += getSum(n - 1));  //短路操作， 当 n>0 时， 才会执行后面的操作。
        return res;
    }
};

把字符串转换成整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int strToInt(string str) {
        int k = 0;
        while (k < str.size() && str[k] == ' ') k++;
        long long number = 0;
        bool is_minus = false;
        if (str[k] == '+') k++;
        else if (str[k] == '-') k++, is_minus = true;
        while (k < str.size() && str[k] >= '0' && str[k] <= '9') {
            number = number * 10 + str[k] - '0';
            k++;
        }
        if (is_minus) number *= -1;
        if (number > INT_MAX) number = INT_MAX;
        if (number < INT_MIN) number = INT_MIN;
        
        return number;
    }
};

树中两个结点的最低公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (root == p || root == q) return root;
        auto left = lowestCommonAncestor(root->left, p, q);
        auto right = lowestCommonAncestor(root->right, p, q);
        if (left && right) return root;
        if (left) return left;
        return right;
    }
};

笔试

Leetcode 768. 京东笔试

单调栈从底至顶是单调递增的，其保存的是到目前为止的遇到的最大值。当一个新元素到达的时候，如果比栈顶大，直接进栈；如果比栈顶小，那么保存一下栈顶curMax，再对栈进行出栈操作直至栈顶元素小于当前元素，最后再把curMax入栈。这样遍历一遍所有的数字之后，得到的栈中的元素个数就是我们要求的块的个数。

思路就是，导致块数变少的原因是来自后面出现了一个较小的元素。这个较小元素的存在，导致了我们必须把它划分到前面去，所以就一路打通到前面一个比它小的元素，这些被打通的元素属于同一个块。最后把curMax进栈，curMax的含义是我们前面一个块的最大值，也就是每个块排序后的最后一个元素。所以最后栈里多少个元素就是我们有多少个块，栈里的每个元素是每个块的结尾元素（最大值）。栗子如下：

比如数组为 [1 0 3 3 2]，我们先把第一个数字1压入栈，此时栈为：

stack：1

然后遍历到第二个数字0，发现小于栈顶元素，将栈顶元素1取出存入curMax，此时栈为空了，不做任何操作，将curMax压回栈，此时栈为：

stack：1

然后遍历到第三个数字3，大于栈顶元素，压入栈，此时栈为：

stack：1，3

然后遍历到第四个数字3，等于栈顶元素，压入栈，此时栈为：

stack：1，3，3

然后遍历到第五个数字2，小于栈顶元素，将栈顶元素3取出存入curMax，此时新的栈顶元素3，大于当前数字2，移除此栈顶元素3，然后新的栈顶元素1，小于当前数字2，循环结束，将curMax压回栈，此时栈为：

stack：1，3

所以最终能拆为两个块儿，即stack中数字的个数。

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
#include <iostream>
#include <vector>
#include <stack>
using namespace std;


int main() {
	int n;
	vector<int> nums;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		nums.push_back(t);
	}
	
	stack<int> temp;
	temp.push(nums[0]);
	
	for (int i = 1; i < n; i++) {
		int cur_max = temp.top();
		if (nums[i] >= temp.top())
			temp.push(nums[i]);
		else {
			cur_max = temp.top();
			while (temp.size() && temp.top() > nums[i]) {
				temp.pop();
			}
			temp.push(cur_max);
		}
				
	}
	
	cout << temp.size() << endl;
	return 0;
}

网易互娱1

给定一个数x, 判断x在二进制下（去掉前导0）是否是回文数。

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
int main()
{
	int n;
	cin >> n; //表示有n个数据
	vector<string> ans;
	for (int i = 0; i < n; i++) { 
		int num;
		cin >> num;
		int  j = 0;
		int temp = num;
		vector<int> t;

		while (temp) {                   //转换成二进制
			t.push_back(temp % 2);
			temp /= 2;
		}
		int sum = 0;
		for (int j = 0; j < t.size(); j++) { 
			sum += t[j] * pow(2, t.size() - j - 1);
		}

		if (sum - num == 0)
			ans.push_back("Yes");
		else
			ans.push_back("No");
	}

	for (auto x : ans)
		cout << x << endl;

	return 0;
}

网易互娱2

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
作者：老司机李云龙
链接：https://www.nowcoder.com/discuss/249359?type=0&order=0&pos=83&page=0
来源：牛客网

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int val;
    int left;
    int right;
};
 
int main() {
    int n;
    cin >> n;
    while(n--) {
        int k;
        cin >> k;
        vector<node> tree(k);
        //用来找根节点
        vector<int> num(k, 0);
        for(int i = 0;i < k;i++) {
            cin >> tree[i].val >> tree[i].left >> tree[i].right;
            if(tree[i].left != -1)
                num[tree[i].left] = 1;
            if(tree[i].right != -1)
                num[tree[i].right] = 1;
        }
        int root = -1;
        for(int i = 0;i < k;i++) {
            if(num[i] == 0){
                root = i;
                break;
            }
        }
        vector<int> treeSum;
        queue<node> q;
        q.push(tree[root]);
        //层次遍历
        while(!q.empty()) {
            int size = q.size();
            int cnt = 0;
            for(int i = 0;i < size;i++) {
                node head = q.front();
                q.pop();
                cnt += head.val;
                if(head.left != -1){
                    q.push(tree[head.left]);
                }
                if(head.right != -1){
                    q.push(tree[head.right]);
                }
            }
            treeSum.push_back(cnt);
        }
        bool ans = true;
        for(int i = 0;i < treeSum.size() - 1;i++) {
            if(treeSum[i+1] < treeSum[i]){
                ans = false;
                break;
            }
        }
        if(ans)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
             
    }
    return 0;
}
0%