算法学习笔记
学习来源：Leetcode，CSDN等
1 排序算法
内部排序算法（直接在内存中排序）有8种常用算法：
性能比较
|
平均情况 |
最好情况 |
最坏情况 |
空间复杂度 |
稳定性 |
一趟排序能确定元素的位置与否 |
| 直接插入排序 |
$O(N^2)$ |
$O(N)$ |
$O(N^2)$ |
$O(1)$ |
稳定 |
不能 |
| 希尔排序 |
$O(N^{1.3})$ |
$O(N)$ |
$O(N^2)$ |
$O(1)$ |
不稳定 |
不能 |
| 简单选择排序 |
$O(N^2)$ |
$O(N^2)$ |
$O(N^2)$ |
$O(1)$ |
不稳定 |
能 |
| 堆排序 |
$O(N\log{N})$ |
$O(N\log{N})$ |
$O(N\log{N})$ |
$O(1)$ |
不稳定 |
能 |
| 冒泡排序 |
$O(N^2)$ |
$O(N)$ |
$O(N^2)$ |
$O(1)$ |
稳定 |
能 |
| 快速排序 |
$O(N\log{N})$ |
$O(N\log{N})$ |
$O(N^2)$ |
$O(\log{N})$ |
不稳定 |
能 |
| 归并排序 |
$O(N\log{N})$ |
$O(N\log{N})$ |
$O(N\log{N})$ |
$O(N)$ |
稳定 |
稳定性
稳定排序：排序前后两个相等的数相对位置不变，则算法稳定
非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定
复杂度比较
- 常数阶$O(1)$
- 对数阶$O(\log{N})$
- 线性阶$O(N)$
- 线性对数阶$O(N\log{N})$
- 平方阶$O(N^2)$
- 立方阶$O(N^3)$
- K方阶$O(N^k)$
- 指数阶$O(2^N)$
从上到下效率越来越低。
1.1 交换类排序
1.1.1 冒泡排序
① 分析
算法步骤：
- 将序列当中的左右元素，依次比较，保证右边的元素始终大于左边的元素；（ 第一轮结束后，序列最后一个元素一定是当前序列的最大值；）
- 对序列当中剩下的n-1个元素再次执行步骤1。
- 对于长度为n的序列，一共需要执行n-1轮比较（如果在一轮中没有发生比较，可以直接结束循环）
最好的情况： 如果待排序数据序列为正序，则一趟冒泡就可完成排序（没有发生排序），排序码的比较次数为n-1次，且没有移动，时间复杂度为O(n)。
最坏的情况： 如果待排序数据序列为逆序，则冒泡排序需要n-1次趟起泡，每趟进行n-i次排序码的比较和移动，即比较和移动次数均达到最大值：
排序情况分析：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 3, 44, 38, 5, 15
总共5个数，最坏情况下需要进行4轮排序
第一轮：对n(5)个数进行排序
3, 38, 44, 5, 15
3, 38, 5, 44, 15
3, 38, 5, 15, 44
第二轮：对n-1(4)个数进行排序
3, 5, 38, 15, 44
3, 5, 15, 38, 44 （排序完成，3,4轮可以不用进行，通过flag控制）
第三轮：对n-2(3)个数进行排序
3, 5, 15, 38, 44
第四轮：对n-4(2)个数进行排序
3, 5, 15, 38, 44
结束
|
② 实现
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
| public class BubbleSortTest {
public static void main(String[] args) {
int[] arr = {12,3,33,11,32,9,8,5};
System.out.println("排序前：" + Arrays.toString(arr));
for (int i = 0; i < arr.length - 1; i++) {
boolean isSwap = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
isSwap = true;
}
}
System.out.println("第" + i + "轮：" + Arrays.toString(arr));
if (!isSwap) {
break;
}
}
}
}
|
1.1.2 快速排序
① 分析
思想：分治法
算法步骤：
- 从待排序的n个记录中任意选取一个记录（通常选取第一个记录）为分区标准;
- 把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为第一趟排序；
- 然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。
最好的情况： 是每趟排序结束后，每次划分使两个子文件的长度大致相等。
最坏的情况： 是待排序记录已经排好序。
排序情况分析：
1
| 66,13,51,76,81,26,57,69,23 pivot=66
|
将两个指针i，j分别指向序列的起始和最后的位置。
反复操作以下两步：
j逐渐减小，并逐次比较j指向的元素和目标元素（pivot）的大小，若arr(j)<pivot则交换位置。i逐渐增大，并逐次比较i指向的元素和目标元素的大小，若arr(i)>pivot则交换位置。- 直到
i，j指向同一个值，这一轮就结束。
第一轮结束后为：
1
| 23 13 51 66 81 26 57 69 76
|
然后以66为界，对两个子序列进行排序:
1
2
| 81 26 57 69 76 pivot=81
23 13 51 pivot=23
|
② 实现
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
|
void quickSort(int arr[],int low, int high) {
if(low >= high) {
return;
}
int left = low;
int right = high;
int pivot = arr[left];
while(left != right) {
while(left < right && arr[right] >= pivot)
--right;
arr[left] = arr[right];
while(left < right && arr[left] <= pivot)
++left;
arr[right] = arr[left];
}
arr[left] = pivot;
quickSort(arr, low, left - 1);
quickSort(arr, left + 1, high);
}
|
1.2 插入类排序
1.2.1 直接插入排序
① 分析
算法步骤：
从待排序的n个记录中的第二个记录（第一个记录看成有序）开始，依次与前面的记录比较并寻找插入的位置，每次外循环结束后，将当前的数插入到合适的位置。
- 第一层循环：遍历待比较的所有数组元素
- 第二层循环：将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。如果：
selected > ordered，那么将二者交换
最好情况：当待排序记录已经有序。
最坏情况：如果待排序记录为逆序。
② 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Main {
public static void main(String args[]) {
int[] arr = new int[]{17,62,39,52,8,24};
for(int i = 1; i < arr.length; i++) {
int temp = arr[i];
for(int j = i - 1; j >= 0; j--) {
if(arr[j] > temp) {
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
}
|
1.2.2 希尔排序
① 分析
希尔排序是将数据分组，将每一组进行插入排序。每一组排成有序后，最后整体就变有序了。
算法步骤：
- 将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；
- 每次将gap折半减小，循环上述操作；
- 当gap=1时，利用直接插入，完成排序。
gap的选取：
一般选取待排序数组长度的三分之一或二分之一
图示
此时分为了1组，再排序一次（此时就是直接插入排序）后变成下面情况：
② 实现
三层循环：最外层控制gap，里面两层和直接插入排序差别不大。
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
| public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
gap /= 2;
shell(array, gap);
}
}
public static void shell(int[] array, int gap) {
for (int i = gap; i < array.length ; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0; j -= gap) {
if (array[j] > tmp) {
array[j + gap] = array[j];
}else {
break;
}
}
array[j + gap] = tmp;
}
}
|
1.3 选择类排序
1.3.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
| public class SelectionSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
}
|
1.3.2 堆排序
① 分析
堆是具有以下性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
例如：
映射到数组为：
节点编号的关系：（节点编号从0开始算）
- 节点
i 的「左子节点」为2i+1，「右子节点」为2i+2，其父节点是(i-1)/2 (0节点除外)
- 对于一棵有
n个节点的完全二叉树，最后一个非叶子节点的编号为(n-2)/2或者n/2 - 1
此时大根堆和小根堆，对于每个节点i满足以下关系：
- 大根堆：
nums[i] >= nums[2i+1] && nums[i] >= nums[2i+2]
- 小根堆：
nums[i] <= nums[2i+1] && nums[i] <= nums[2i+2]
算法步骤：
- 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点，位于数组的第一个位置。
- 将最大元素与末尾元素进行交换，此时末尾就为最大值。
- 然后将剩余n-1个元素重新构造成一个大顶堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
细节：
- 从最后一个「非叶子节点」为根节点的子树出发，从右往左、从下往上进行调整操作。
- 对于以某个非叶子节点的子树而言，其基本的调整操作包括:
- 如果该节点大于等于其左右两个子节点，则无需再对该节点进行调整，因为它的子树已经是堆有序的；
- 如果该节点小于其左右两个子节点中的较大者，则将该节点与子节点中的较大者进行交换，并从刚刚较大者的位置出发继续进行调整操作，直至堆有序。
图示
给定待排序数组：nums=[5,2,1,9,6,8]，最后一个非叶子节点编号为6/2-1=2。
第一步：
第二步：
第三步：
第四步：
至此，建立了一个大根堆。
注意到，在每一次建好大根堆后，堆顶元素即为当前范围内的最大值，因此要得到数组中的第 K 个最大元素需要：建堆（大根堆） K 次，此时堆顶元素即为第 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
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
| public class HeapSort {
@Test
public void test() {
int[] arr = {5, 2, 1, 9, 6, 8};
heapSort(arr);
}
public void heapSort(int[] arr) {
int startIndex = (arr.length - 2) / 2;
for (int i = startIndex; i >= 0; i--) {
toMaxHeap(arr, arr.length, i);
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, i, 0);
toMaxHeap(arr, i, 0);
}
System.out.println(Arrays.toString(arr));
}
public void toMaxHeap(int[] arr, int size, int index) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int maxIndex = index;
if (leftChildIndex < size && arr[leftChildIndex] > arr[maxIndex]) {
maxIndex = leftChildIndex;
}
if (rightChildIndex < size && arr[rightChildIndex] > arr[maxIndex]) {
maxIndex = rightChildIndex;
}
if (maxIndex != index) {
swap(arr, index, maxIndex);
toMaxHeap(arr, size, maxIndex);
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|
1.4 归并排序
1.4.1 分析
归并排序属于比较类非线性时间排序，号称比较类排序中性能最佳者，在数据中应用中较广。归并排序是java语言底层的Arrays.sort()的实现。
归并排序是分治法（Divide and Conquer）的一个典型的应用。
若将两个有序集合并成一个有序表，称为2-路归并，与之对应的还有多路归并。
算法步骤：先分解，再合并
1.4.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
| public class MergeSort {
public static void mergeSort(int[] a, int lo, int hi) {
int[] temp = new int[a.length];
mergeSort(a, temp, lo, hi);
}
public static void mergeSort(int[] a) {
mergeSort(a, 0, a.length - 1);
}
private static void mergeSort(int[] a, int[] temp, int lo, int hi) {
int mid = (lo + hi) / 2;
if (hi - lo > 1) {
mergeSort(a, temp, lo, mid);
mergeSort(a, temp, mid + 1, hi);
}
merge(a, temp, lo, mid, hi);
}
private static void merge(int[] a, int[] temp, int lo, int mid, int hi) {
int arr1Begin = lo;
int arr1End = mid;
int arr2Begin = mid + 1;
int arr2End = hi;
int k = lo;
while (arr1Begin <= arr1End || arr2Begin <= arr2End) {
if (arr1Begin > arr1End) {
temp[k++] = a[arr2Begin++];
} else if (arr2Begin > arr2End) {
temp[k++] = a[arr1Begin++];
} else {
if (a[arr1Begin] < a[arr2Begin]) {
temp[k++] = a[arr1Begin++];
} else {
temp[k++] = a[arr2Begin++];
}
}
}
for (int i = lo; i <= hi; i++) {
a[i] = temp[i];
}
}
public static void main(String[] args) {
int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
mergeSort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
|
1.5 基数排序
基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。
具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
例如：
1.6 例题
题1：将5个不同的数据进行排序，至多需要比较（）次比较。
计算方法：$C_{n}^{2}$，n为待排序个数
组合数公式：
解答：考虑采用最暴力的做法，每两个数之间都比较一次，一共需要比较$C_{5}^{2}$次（10次）。
题2：现有N条词以及对应的拼音串，对其排序，排序规则：首先按拼音串的字母序排序，如果拼音串相同，则按当前词所在的顺序排序，下列哪些排序算法符合条件？（ ）
A.插入排序
B.快速排序
C.堆排序
D.冒泡排序
解答：AD，本质分为两次排序，后一次排序不能破坏前一次排序的结果，因此只能采用稳定排序。
题3：如果开发一款打扑克的游戏，现在要对选手拿到的牌进行排序，请问一下哪种排序方式最合适？
A.冒泡排序
B.希尔排序
C.选择排序
D.插入排序
解答：D，牌是一张一张发的，每发一张就要插入到手牌中，因此选用插入排序最合适。
题4：有序列（8,5,2,12,7,1,6,10,9,3,4,11），新序列（4,5,2,3,1,6,7,10,9,12,8,11）是下列（ ）排序算法一趟扫描结果。
A.堆排序
B.快速排序
C.希尔排序
D.冒泡排序
解答：B，注意pivot不一定是第一个元素，这里的pivot选择了7，左小右大。
题5：将一个从大到小的数组，用以下排序方法排序成从小到大的，（）最快。
A.插入排序
B.冒泡排序
C.快速排序
D.堆排序
解答：D，逆序排列（最坏情况），ABC均为平方阶，堆排序最坏情况为线性对数阶。
题6：
2 回溯法
思想
回溯法，又叫试探法，是一种寻找最优解的暴力搜寻法。主要思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
基本思想：
- 针对具体问题，定义问题的解空间；
- 确定易于搜索的解空间结构（数据结构的选择）。
- 一般以DFS（深度优先搜索）的方式搜索解空间。
- 在搜索过程中，可以使用剪枝函数等来优化算法。
站在回溯的某个节点上，我们需要思考三个问题：
- 路径:就是我们当前做出的选择
- 选择列表:就是我们当前可以做出的选择
- 结束条件:也就是到达决策树底部，无法再做出选择
通用代码框架：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| result=[];
def backtrack(路径,选择列表)
if 满足结束条件:
result.add(路径);
return;
for 选择 in 选择列表
做选择
backtrack(路径，选择列表)
撤销选择
|
Leetcode例题
1 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
1
2
| 输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
示例 2：
1
2
| 输入：nums = [0,1]
输出：[[0,1],[1,0]]
|
示例 3：
多叉树的生成过程：以[1, 2, 3]为例
对于这道题而言，当树的深度等于数组大小时，就结束搜索。
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
|
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> res;
if(len == 0) {
return res;
}
int depth = 0;
vector<bool> used(false, 0);
vector<int> path;
dfs(nums, len, depth, used, path, res);
return res;
}
void dfs(vector<int>& nums, int len, int depth,
vector<int>& used, vector<int>& path, vector<vector<int>>& res) {
if(depth == len) {
res.push_back(path);
return;
}
for(int i = 0; i < len; i++) {
if(!used[i]) {
used[i] = true;
path.push_back(nums[i]);
dfs(nums, len, depth + 1, used, path, res);
used[i] = false;
path.pop_back();
}
}
}
};
|
总结：
做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。
在画图的过程中思考清楚：
- 分支如何产生；
- 题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
- 哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？
2 全排列②
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
1
2
3
4
5
| 输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
|
示例 2：
1
2
| 输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
这道题和上道题不同的地方在于，需要对遍历生成的树进行剪枝，即去掉不符合题意的叶子结点。
如果要比较两个列表是否一样，一个容易想到的办法是对列表分别排序，然后逐个比对。既然要排序，我们就可以在搜索之前就对候选数组排序，一旦发现某个分支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复列表。
重点想象深度优先遍历在这棵树上执行的过程，哪些地方遍历下去一定会产生重复，这些地方的状态的特点是什么？
对比图中标注 ① 和 ② 的地方。相同点是：这一次搜索的起点和上一次搜索的起点一样。不同点是：
- 标注 ① 的地方上一次搜索的相同的数刚刚被撤销；
- 标注 ② 的地方上一次搜索的相同的数刚刚被使用。
如何判断当前分支是否是重复的分支： 因为之前已经排好序了，所以当前选择的元素nums[i]如果和前一个选择的元素相同 ，即nums[i] == nums[i-1]就说明该分支有可能是重复的。 但是这个相等条件有两种可能，一种是，1 1‘ 2，也就是选择完1之后再选择第二个1，两个元素虽然重复，但是第二个元素是前一个元素的下一层，这时是没有问题的。 另一种是之前的同层分支已经有 1 1‘ 2了，这次的选择是 1‘ 1 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
|
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
int len = nums.size();
vector<vector<int>> res;
if(len == 0) {
return res;
}
vector<bool> used(len, false);
vector<int> path;
dfs(nums, len, 0, used, path, res);
return res;
}
void dfs(vector<int>& nums, int len, int depth,
vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
if(depth == len) {
res.push_back(path);
return;
}
for(int i = 0; i < len; i++) {
if(used[i]) {
continue;
}
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
used[i] = true;
path.push_back(nums[i]);
dfs(nums, len, depth + 1, used, path, res);
used[i] = false;
path.pop_back();
}
}
};
|
3 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
1
2
3
4
5
6
| 输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
|
示例 2：
1
2
| 输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
|
示例 3：
1
2
| 输入: candidates = [2], target = 1
输出: []
|
首先画出一棵树来分析，以candidates = [2, 3, 6, 7]，target = 7 为例：
可以看出递归返回的条件为target=0，剪枝条件是target<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 <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
int len = candidates.size();
vector<vector<int>> res;
vector<int> path;
dfs(candidates, path, 0, res, len, target);
return res;
}
void dfs(vector<int>& candidates, vector<int>& path, int index, vector<vector<int>>& res, int len, int target) {
int sum = 0;
for(int& x : path) {
sum+=x;
}
if(sum == target) {
res.push_back(path);
return;
}
if(sum > target) {
return;
}
for(int i = index; i < len; i++) {
path.push_back(candidates[i]);
dfs(candidates, path, i, res, len, target);
path.pop_back();
}
}
};
|
4 组合总数②
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
1
2
3
4
5
6
7
8
| 输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
|
示例 2:
1
2
3
4
5
6
| 输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
|
这道题和1.2.2类似，都是数组中的元素有重复的，因此需要排序，利用1.2.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
|
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int len = candidates.size();
vector<vector<int>> res;
vector<int> path;
sort(candidates.begin(), candidates.end());
dfs(candidates, path, 0, res, len, target);
return res;
}
void dfs(vector<int>& candidates, vector<int>& path, int index, vector<vector<int>>& res, int len, int target) {
int sum = 0;
for(int& x : path) {
sum+=x;
}
if(sum == target) {
res.push_back(path);
return;
}
if(sum > target) {
return;
}
for(int i = index; i < len; i++) {
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
path.push_back(candidates[i]);
dfs(candidates, path, i+1, res, len, target);
path.pop_back();
}
}
};
|
5 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
1
2
3
4
5
6
7
8
9
10
| 输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
|
示例 2：
1
2
| 输入：n = 1, k = 1
输出：[[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
|
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> path;
vector<int> nums(n, 0);
int count = 1;
for(vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter++) {
*iter += count;
count++;
}
dfs(nums, nums.size(), 0, k, path, res);
return res;
}
void dfs(vector<int>& nums, int len, int begin, int k, vector<int>& path, vector<vector<int>>& res) {
if(path.size() == k) {
res.push_back(path);
return;
}
for(int i = begin; i < len; i++) {
path.push_back(nums[i]);
dfs(nums, nums.size(), i+1, k, path, res);
path.pop_back();
}
}
};
|
6 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1
2
| 输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
|
示例 2：
1
2
| 输入：nums = [0]
输出：[[],[0]]
|
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums 中的所有元素 互不相同
这道题的特殊之处在于，每个结点都是符合条件的解。
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 <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int len = nums.size();
vector<vector<int>> res;
vector<int> temp;
dfs(nums, 0, len, temp, res);
res.push_back({});
return res;
}
void dfs(vector<int>& nums, int begin, int len,
vector<int>& temp, vector<vector<int>>& res) {
if(begin == len) {
return;
}
for(int i = begin; i < len; i++) {
temp.push_back(nums[i]);
res.push_back(temp);
dfs(nums, i+1, len, temp, res);
temp.pop_back();
}
}
};
|
7 子集②
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
1
2
| 输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
|
示例 2：
1
2
| 输入：nums = [0]
输出：[[],[0]]
|
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
和上一题的不同在于，包含重复元素，思想同1.2.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
|
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
int len = nums.size();
vector<vector<int>> res;
vector<int> temp;
vector<bool> used(len, false);
dfs(nums, 0, len, temp, res, used);
res.push_back({});
return res;
}
void dfs(vector<int>& nums, int begin, int len,
vector<int>& temp, vector<vector<int>>& res, vector<bool>& used) {
if(begin == len) {
return;
}
for(int i = begin; i < len; i++) {
if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
temp.push_back(nums[i]);
used[i] = true;
res.push_back(temp);
dfs(nums, i+1, len, temp, res, used);
temp.pop_back();
used[i] = false;
}
}
};
|
8 排列序列
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"
给定 n 和 k，返回第 k 个排列。
示例 1：
1
2
| 输入：n = 3, k = 3
输出："213"
|
示例 2：
1
2
| 输入：n = 4, k = 9
输出："2314"
|
示例 3：
1
2
| 输入：n = 3, k = 1
输出："123"
|
提示：
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
|
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> nums(n, 0);
int count = 1;
for(int& num : nums) {
num = count;
count++;
}
vector<int> path;
vector<vector<int>> res;
count = 0;
vector<bool> used(n, false);
dfs(nums, path, n, 0, k, count, res, used);
vector<int> tmp = res[0];
string resStr;
for(int& s : tmp) {
resStr += to_string(s);
}
return resStr;
}
void dfs(vector<int>& nums, vector<int>& path,
int len, int depth, int k, int& count, vector<vector<int>>& res, vector<bool>& used) {
if(depth == len) {
count+=1;
if(count == k) {
res.push_back(path);
}
return;
}
for(int i = 0; i < len; i++) {
if(count == k) {
break;
}
if(!used[i]) {
path.push_back(nums[i]);
used[i] = true;
dfs(nums, path, len, depth+1, k, count, res, used);
used[i] = false;
path.pop_back();
}
}
}
};
|
上面的代码通过回溯法，从第1个叶子结点开始寻找，直到找到第k个叶子结点，该方法可以优化。
所求排列 一定在叶子结点处得到，进入每一个分支，可以根据已经选定的数的个数，进而计算还未选定的数的个数，然后计算阶乘，就知道这一个分支的 叶子结点 的个数：
- 如果 k 大于这一个分支将要产生的叶子结点数，直接跳过这个分支，这个操作叫「剪枝」；
- 如果 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
string getPermutation(int n, int k) {
vector<bool> isUsed(n + 1, false);
string res = "";
dfs(isUsed, res, n, k);
return res;
}
void dfs(vector<bool> &isUsed, string &res, int n, int k){
int res_len = res.size();
if(res_len == n){
return;
}
int remain_fac = factorial(n - res_len - 1);
for(int i = 1; i <= n; ++i){
if(isUsed[i]){
continue;
}
if(remain_fac > 0 && remain_fac < k){
k -= remain_fac;
continue;
}
res = res + static_cast<char>('0' + i);
isUsed[i] = true;
dfs(isUsed, res, n, k);
}
}
int factorial(int n){
int res = 1;
while(n > 0){
res *= n;
n--;
}
return res;
}
};
|
9 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
1
2
| 输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
|
示例 2：
提示：
例如n=3时，可生成的左括号数和右括号数分别为3；
- 当前左右括号都有大于 0 个可以使用的时候，才产生分支；
- 产生左分支的时候，只看当前是否还有左括号（
left>0）可以使用；
- 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量（
left<right）的时候，才可以产生分支；
- 在左边和右边剩余的括号数都等于 0 （
left=right=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
|
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<string> generateParenthesis(int n) {
int left = n;
int right = n;
vector<string> res;
string str("");
dfs(str, left, right, res);
return res;
}
void dfs(string str, int left, int right, vector<string>& res) {
if(left == 0 && right == 0) {
res.push_back(str);
return;
}
if(left > right) {
return;
}
if(left > 0) {
dfs(str + "(", left-1, right, res);
}
if(left < right) {
dfs(str + ")", left, right-1, res);
}
}
};
|
10 复原IP地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
1
2
| 输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
|
示例 2：
1
2
| 输入：s = "0000"
输出：["0.0.0.0"]
|
示例 3：
1
2
| 输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
|
提示：
1 <= s.length <= 20s 仅由数字组成
11 图像渲染
有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。
你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。
为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。
最后返回 经过上色渲染后的图像 。
示例 1:
1
2
3
4
| 输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。
|
示例 2:
1
2
| 输入: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, newColor = 2
输出: [[2,2,2],[2,2,2]]
|
提示:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], newColor < 2160 <= sr < m0 <= sc < 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
34
35
36
37
38
39
40
41
42
43
44
|
#include <vector>
using namespace std;
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int m = image.size();
int n = image[0].size();
vector<vector<int>> res(image);
vector<vector<int>> visited;
for(int i = 0; i < m; i++) {
vector<int> temp(n, 0);
visited.push_back(temp);
}
dfs(image, res, sr, sc, color, visited);
res[sr][sc] = color;
return res;
}
void dfs(vector<vector<int>>& image, vector<vector<int>>& res, int sr, int sc, int color, vector<vector<int>>& visited) {
int cur = image[sr][sc];
visited[sr][sc] = 1;
for(int i = 0; i < 4; i++) {
int x = sr + dx[i];
int y = sc + dy[i];
if(x >= 0 && x < image.size() && y >= 0 && y < image[0].size() && image[x][y] == cur) {
if(visited[x][y] == 1) {
continue;
}
res[x][y] = color;
dfs(image, res, x, y, color, visited);
}
}
}
};
|
12 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
1
2
3
4
5
6
7
| 输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
|
示例 2：
1
2
3
4
5
6
7
| 输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
|
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] 的值为 '0' 或 '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
|
#include <vector>
using namespace std;
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int res = 0;
vector<vector<int>> visited;
for(int i = 0; i < m; i++) {
vector<int> temp(n, 0);
visited.push_back(temp);
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(visited[i][j] == 0 && grid[i][j] == '1') {
dfs(grid, visited, i, j);
res+=1;
}
}
}
return res;
}
void dfs(vector<vector<char>>& grid, vector<vector<int>>& visited, int x, int y) {
visited[x][y] = 1;
for(int i = 0; i < 4; i++) {
int _x = x + dx[i];
int _y = y + dy[i];
if(_x >= 0 && _x < grid.size() && _y >= 0 && _y < grid[0].size() && grid[_x][_y] == '1' && visited[_x][_y] == 0) {
dfs(grid, visited, _x, _y);
}
}
}
};
|
13 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例 1：
1
2
3
| 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
|
示例 2：
1
2
| 输入：board = [["X"]]
输出：[["X"]]
|
提示：
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j] 为 'X' 或 'O'
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
|
#include <vector>
using namespace std;
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
bool flag = false;
void solve(vector<vector<char>>& board) {
int m = board.size();
int n = board[0].size();
vector<vector<int>> visited;
vector<vector<int>> path;
for(int i = 0; i < m; i++) {
vector<int> temp(n, 0);
visited.push_back(temp);
}
vector<vector<int>> ovisited(visited);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(board[i][j] == 'O') {
flag = false;
if(i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1) {
flag = true;
}
path.push_back({i, j});
dfs(board, path, visited, i, j);
if(!flag) {
for(vector<int> v : path) {
board[v[0]][v[1]] = 'X';
}
}
path.clear();
visited = ovisited;
}
}
}
}
void dfs(vector<vector<char>>& board, vector<vector<int>>& path, vector<vector<int>>& visited, int x, int y) {
visited[x][y] = 1;
for(int i = 0; i < 4; i++) {
int _x = x + dx[i];
int _y = y + dy[i];
if(_x >= 0 && _x < board.size() && _y >= 0 && _y < board[0].size() && visited[_x][_y] == 0) {
if(board[_x][_y] == 'O') {
if(_x == 0 || _x == board.size() - 1 || _y == 0 || _y == board[0].size() - 1) {
flag = true;
}
path.push_back({_x, _y});
dfs(board, path, visited, _x, _y);
}
}
}
}
};
|
14 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
1
2
| 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
|
示例 2：
1
2
| 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
|
示例 3：
1
2
| 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
|
提示：
m == board.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board 和 word 仅由大小写英文字母组成
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
|
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
bool flag = false;
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
vector<vector<int>> visited;
for(int i = 0; i < m; i++) {
vector<int> temp(n, 0);
visited.push_back(temp);
}
vector<vector<int>> ovisited(visited);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(board[i][j] == word[0]) {
dfs(board, visited, i, j, word, 1);
}
visited = ovisited;
}
}
return flag;
}
void dfs(vector<vector<char>>& board, vector<vector<int>>& visited, int x, int y, string& word, int seq) {
visited[x][y] = true;
if(seq == word.size()) {
flag = true;
return;
}
for(int i = 0; i < 4; i++) {
if(flag) {
break;
}
int _x = x + dx[i];
int _y = y + dy[i];
if(_x >= 0 && _x < board.size() && _y >= 0 && _y < board[0].size() && visited[_x][_y] == 0) {
if(board[_x][_y] == word[seq]) {
dfs(board, visited, _x, _y, word, seq+1);
visited[_x][_y] = false;
}
}
}
}
};
|
15 路径总和②
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
1
2
| 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
|
示例 2：
1
2
| 输入：root = [1,2,3], targetSum = 5
输出：[]
|
示例 3：
1
2
| 输入：root = [1,2], targetSum = 0
输出：[]
|
提示：
- 树中节点总数在范围
[0, 5000] 内
-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
题解
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
|
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res;
vector<int> path;
if(root == nullptr) {
return res;
}
dfs(root, path, res, targetSum);
return res;
}
void dfs(TreeNode* node, vector<int>& path, vector<vector<int>>& res, int remain) {
path.push_back(node->val);
if(node->right == nullptr && node->left == nullptr) {
if(remain - node->val == 0) {
res.push_back(path);
return;
}
}
if(node->left) {
dfs(node->left, path, res, remain - node->val);
path.pop_back();
}
if(node->right) {
dfs(node->right, path, res, remain - node->val);
path.pop_back();
}
}
};
|
16 叶子相似的树
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
1
2
| 输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true
|
提示：
- 给定的两棵树结点数在
[1, 200] 范围内
- 给定的两棵树上的值在
[0, 200] 范围内
题解
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
| #include <vector>
using namespace std;
class Solution {
public:
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector<int> leafNodes1;
vector<int> leafNodes2;
dfs(root1, leafNodes1);
dfs(root2, leafNodes2);
if(leafNodes1.size() != leafNodes2.size()) {
return false;
}
for(int i = 0; i < leafNodes1.size(); i++) {
if(leafNodes1[i] != leafNodes2[i])
return false;
}
return true;
}
void dfs(TreeNode* node, vector<int>& path) {
if(node->left == nullptr && node->right == nullptr) {
path.push_back(node->val);
return;
}
if(node->left)
dfs(node->left, path);
if(node->right)
dfs(node->right, path);
}
};
|
3 贪心算法
思想
贪心算法（greedy algorithm ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。
利用贪心法求解的问题应具备如下2个特征：
- 贪心选择性质：一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
- 最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中，至于什么问题具有什么样的贪心选择性质是不确定的，需要具体问题具体分析。
Leetcode例题
分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
1
2
3
4
5
6
| 输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
|
示例 2:
1
2
3
4
5
6
| 输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
|
提示：
1 <= g.length <= 3 * 1040 <= s.length <= 3 * 1041 <= g[i], s[j] <= 231 - 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
|
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int cur;
int begin = 0;
int res = 0;
for(int i = 0; i < s.size(); i++) {
cur = s[i];
for(int j = begin; j < g.size(); j++) {
if(cur >= g[j]) {
res++;
begin = j + 1;
break;
} else {
break;
}
}
}
return res;
}
};
|
摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
- 例如，
[1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
- 相反，
[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
1
2
3
| 输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
|
示例 2：
1
2
3
4
| 输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
|
示例 3：
1
2
| 输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
|
提示：
1 <= nums.length <= 10000 <= nums[i] <= 1000
进阶：你能否用 O(n) 时间复杂度完成此题?
题解
柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
1
2
3
4
5
6
7
| 输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
|
示例 2：
1
2
3
4
5
6
7
| 输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
|
提示：
1 <= bills.length <= 105bills[i] 不是 5 就是 10 或是 20
题解
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
|
#include <vector>
#include <queue>
using namespace std;
class Solution {
queue<int> q1;
queue<int> q2;
bool flag;
public:
bool lemonadeChange(vector<int>& bills) {
if(bills[0] != 5) {
return false;
}
for(int i = 0; i < bills.size(); i++) {
flag = false;
int cash = bills[i];
switch(cash) {
case 5:
q1.push(cash);
flag = true;
break;
case 10:
flag = change(5);
break;
case 20:
flag = change(15);
break;
}
if(!flag) {
return false;
}
}
return true;
}
bool change(int bill) {
if(bill == 5) {
if(q1.size() == 0) {
return false;
} else {
q1.pop();
q2.push(10);
return true;
}
} else {
if(q1.size() >= 1 && q2.size() >= 1) {
q1.pop();
q2.pop();
return true;
} else {
if(q1.size() >= 3) {
for(int i = 0;i < 3; i++) {
q1.pop();
}
return true;
} else {
return false;
}
}
}
return false;
}
};
|
4 动态规划
思想
暂略
背包问题理论基础
对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。
01背包
有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
暴力解法：每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是$o(2^n)$，这里的n表示物品数量。
所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！
例子：
背包最大重量为4。
物品为：
|
重量 |
价值 |
| 物品0 |
1 |
15 |
| 物品1 |
3 |
20 |
| 物品2 |
4 |
30 |
问背包能背的物品最大价值是多少？
题解
对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)
放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
首先从dp[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。如图：
状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。
dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
代码初始化如下：
1
2
3
4
5
6
7
| for (int j = 0 ; j < weight[0]; j++) {
dp[0][j] = 0;
}
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
|
此时dp数组初始化情况如图所示：
1
2
3
4
5
|
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
|
可以看出dp[i][j] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。
可以看出，有两个遍历的维度：物品与背包重量
那么问题来了，先遍历 物品还是先遍历背包重量呢？
其实都可以！！ 但是先遍历物品更好理解。
那么我先给出先遍历物品，然后遍历背包重量的代码。
1
2
3
4
5
6
7
|
for(int i = 1; i < weight.size(); i++) {
for(int j = 0; j <= bagweight; j++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[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
28
| void test_2_wei_bag_problem1() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagweight = 4;
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
for(int i = 1; i < weight.size(); i++) {
for(int j = 0; j <= bagweight; j++) {
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
cout << dp[weight.size() - 1][bagweight] << endl;
}
int main() {
test_2_wei_bag_problem1();
}
|
Leetcode例题
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
1
2
3
4
5
| 输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
|
示例 2：
1
2
3
4
5
6
| 输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
提示：
爬第n阶楼梯的方法数量，等于 2 部分之和：
- 爬上 n−1 阶楼梯的方法数量，因为再爬1阶就能到第n阶
- 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第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
|
#include <vector>
using namespace std;
class Solution {
public:
int climbStairs(int n) {
if(n <= 2) {
return n;
}
vector<int> dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i < n + 1; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};
|
优化：滚动数组。我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现，但是这里的$f(x)$之和$f(x-1)$与$f(x-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
|
#include <vector>
using namespace std;
class Solution {
public:
int climbStairs(int n) {
if(n <= 2) {
return n;
}
int f_n_1 = 1, f_n_2 = 0, f_n = 2;
for(int i = 3; i <= n; i++) {
f_n_2 = f_n_1;
f_n_1 = f_n;
f_n = f_n_1 + f_n_2;
}
return f_n;
}
};
|
使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1：
1
2
3
4
5
| 输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
|
示例 2：
1
2
3
4
5
6
7
8
9
10
| 输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
|
提示：
2 <= cost.length <= 10000 <= cost[i] <= 999
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
|
#include <vector>
using namespace std;
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int len = cost.size();
vector<int> dp1(len + 1, 0);
vector<int> dp2(len, 0);
dp1[0] = 0;
dp1[1] = cost[0];
dp2[0] = 0;
dp2[1] = cost[1];
for(int i = 2; i <= len; i++) {
dp1[i] = min(dp1[i - 1] + cost[i - 1], dp1[i - 2] + cost[i - 2]);
}
for(int i = 2; i < len; i++) {
dp2[i] = min(dp2[i - 1] + cost[i], dp2[i - 2] + cost[i - 1]);
}
return dp1[len] < dp2[len - 1] ? dp1[len] : dp2[len - 1];
}
};
|
或者将两种情况考虑在一起，此时$dp[0]=dp[1]=0$：
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
};
|
斐波那契数列
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
1
2
| F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
|
给定 n ，请计算 F(n) 。
示例 1：
1
2
3
| 输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
|
示例 2：
1
2
3
| 输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
|
示例 3：
1
2
3
| 输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
|
提示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int fib(int n) {
if(n <= 1) {
return n;
}
int *dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
|
滚动数组：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int fib(int n) {
if(n <= 1) {
return n;
}
int q = 0, p = 1, r = 1;
for(int i = 2; i < n; i++) {
q = p;
p = r;
r = p + q;
}
return r;
}
};
|
不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
示例 2：
1
2
3
4
5
6
7
| 输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
|
示例 3：
示例 4：
提示：
1 <= m, n <= 100- 题目数据保证答案小于等于
2 * 109
可以使用回溯法，但是时间超时：
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 <vector>
using namespace std;
class Solution {
public:
const int dx[2] = {1, 0};
const int dy[2] = {0, 1};
int uniquePaths(int m, int n) {
int res = 0;
vector<vector<int>> board;
for(int i = 0; i < m; i++) {
vector<int> temp(n, 0);
board.push_back(temp);
}
board[m - 1][n - 1] = 1;
dfs(board, 0, 0, res);
return res;
}
void dfs(vector<vector<int>>& board, int x, int y, int& res) {
if(board[x][y] == 1) {
res++;
return;
}
for(int i = 0; i < 2; i++) {
int _x = x + dx[i];
int _y = y + dy[i];
if(_x < board.size() && _y < board[0].size()) {
dfs(board, _x, _y, res);
}
}
}
};
|
使用动态规划：
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
|
#include <vector>
using namespace std;
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
int i, j;
for(i = 0; i < m; i++) {
dp[i][0] = 1;
}
for(i = 0; i < n; i++) {
dp[0][i] = 1;
}
for(i = 1; i < m; i++) {
for(j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
|
不同路径②
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
1
2
3
4
5
6
| 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
|
示例 2：
1
2
| 输入：obstacleGrid = [[0,1],[0,0]]
输出：1
|
提示：
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] 为 0 或 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
|
#include <vector>
using namespace std;
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int i, j;
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
vector<vector<int>> dp(m, vector<int>(n, 0));
for(i = 0; i < m; i++) {
if(obstacleGrid[i][0] == 1) {
break;
} else {
dp[i][0] = 1;
}
}
for(i = 0; i < n; i++) {
if(obstacleGrid[0][i] == 1) {
break;
} else {
dp[0][i] = 1;
}
}
for(i = 1; i < m; i++) {
for(j = 1; j < n; j++) {
dp[i][j] = 0;
if(obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
if(dp[i-1][j] != 0) {
dp[i][j] += dp[i-1][j];
}
if(dp[i][j-1] != 0) {
dp[i][j] += dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
};
|
整数拆分
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
1
2
3
| 输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
|
示例 2:
1
2
3
| 输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
|
提示:
题解
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 <vector>
using namespace std;
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
int curMax = 0;
for(int j = 1; j < i; j++) {
curMax = max(curMax, max(j * (i - j), j * dp[i - j]));
}
dp[i] = curMax;
}
return dp[n];
}
};
|
不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
示例 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
|
#include <vector>
using namespace std;
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++) {
dp[i] = 0;
for(int j = 0; j < i; j++) {
dp[i] = dp[i] + dp[j] * dp[i-j-1];
}
}
return dp[n];
}
};
|
分割等和子集*
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
1
2
3
| 输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
|
示例 2：
1
2
3
| 输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
|
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
题解
打家劫舍③*
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 *在不触动警报的情况下 ，小偷能够盗取的最高金额* 。
示例 1:
1
2
3
| 输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
|
示例 2:
1
2
3
| 输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9
|
提示：
- 树的节点数在
[1, 104] 范围内
0 <= Node.val <= 104
题解
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
|
#include <unordered_map>
using namespace std;
class Solution {
unordered_map<TreeNode*, int> f;
unordered_map<TreeNode*, int> g;
public:
int rob(TreeNode* root) {
postorder(root);
return max(f[root], g[root]);
}
void postorder(TreeNode* node) {
if(node == nullptr) {
return ;
}
postorder(node->left);
postorder(node->right);
f[node] = node->val + g[node->left] + g[node->right];
g[node] = max(f[node->left], g[node->left]) + max(f[node->right], g[node->right]);
}
};
|
买卖股票的最佳时机②
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
1
2
3
4
5
| 输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
|
示例 2：
1
2
3
4
| 输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
|
示例 3：
1
2
3
| 输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
|
提示：
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
题解
