leetcode题解合集 | Kelin's blog

DFS/回溯

以整数拆分为例：

剪枝条件

当和为n时，保存结果
当和大于n时，进行剪枝

在DFS中，同一排的结点是在同一个函数调用中进行处理，如上图中的第一排，1、2、3、4、这4个结点是在第一次函数调用中进行处理。

因此使用一个for循环来处理同一排的结点。
因为元素可以重复取用，本来for循环的起始位置应该都为1，但是为了避免重复，我们可以假设for循环的起始位置为其父节点的值，这里用变量index表示

vector<int> res;
//n表示要拆分的数 index表示当前函数从哪个数开始拆 sum表示当前的和
void split(int n,int index,int sum) {
    if (sum == n) {//保存结果
        myPrint(res);
        return;
    }
    if (sum > n) return;//剪枝
    for (int i = index; i < n; ++i) {
        res.push_back(i);
        //元素可以重复使用，下一次还是从i开始拆分，拆到n为止
        split(n, i, sum + i);
        res.pop_back();
    }
}

77 组合
 216. 组合总和 III
39. 组合总和
 17. 电话号码的字母组合
 40. 组合总和 II
90. 子集 II
47. 全排列 II
679. 24点游戏
 687. 最长同值路径

动态规划

一个超级实用的视频
状态表示：
f 函数代表什么状态？
写出状态表示之后我们会有一个f函数的集合，代表递推到f(i)时，有多少种可能的状态。

动态转移方程
把集合中的每一种可能表示出来，对应要求的结果（求最大、最小、求和等）写出动态转移方程。

状态表示
状态集，从状态集求出当前状态

思考当前状态对比前一个状态会有什么变化：

从前一步加1？
等于前一步？

如下图所示

2400. 恰好移动 k 步到达某一位置的方法数目

贪心

每次选取局部最优解，得到最终的最优解。
2406. 将区间分为最少组数
 406. 根据身高重建队列
 452. 用最少数量的箭引爆气球

数据结构

优先队列

//升序队列 小顶堆
priority_queue <int,vector<int>,greater<int>> q;
//降序队列  大顶堆 默认情况
priority_queue <int,vector<int>,less<int>> q;

数组/链表/哈希

数组： 查找效率高，插入和删除效率低
链表： 插入删除效率高，查找效率低

哈希：

思想：通过哈希函数得到的键值，使其能够高效查找
当键值重复时，处理哈希冲突
在C++中unordered_set 和unordered_map的底层实现时哈希表

454. 四数相加 II
2405. 子字符串的最优划分
 6221. 最流行的视频创作者

栈/队列

907. 子数组的最小值之和
 1106. 解析布尔表达式

单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
739. 每日温度
 503. 下一个更大元素 II

前缀树

并查集

并查集由两个部分构成：

find()函数，发现x的根
Union()函数，合并

// 初始化，最初每个元素的根都是自己
void init(vector<int> &parent, int n){
    for(int i = 0;i < n; ++i){
        parent.push_back(i);
    }
}
//发现x的根
int myfind(vector<int> &parent, int x) {
    if(parent[x] != x) {
        parent[x] = myfind(parent,parent[x]);
    }
    return parent[x];
}
//将y的根给x的根，将x和y合并为一堆
void myunion(vector<int> &parent,int x,int y) {
    parent[myfind(parent,x)] = myfind(parent,y);
}

并查集

886. 可能的二分法

934. 最短的桥 BFS+DFS

684. 冗余连接并查集+拓扑排序

线段树

双指针/滑动窗口

主要是考虑左指针往右走的条件。
209. 长度最小的子数组

树

对于二叉树来书，考虑遍历方式：

前序遍历：先处理父节点，再处理孩子节点
中序遍历：先处理左孩子，再处理父节点，最后处理右孩子
后序遍历：先处理孩子结点，再处理父节点

大部分题目都是使用的后序遍历来求解：因为处理父节点时往往需要用到子节点的结果

6242. 二叉搜索树最近节点查询
序列化二叉搜索树

位运算

操作	结果	特性
~	取反，0变为1，1变为0
a&b	且，ab同时为1时才取1	a & b <= min(a,b)，交换律、结合律，越取越小
a 或 b	a和b其中有一个为1，最终结果就是1	越取越大
a ^ b	a和b相同时为1，不同为0
<< 和 >>	左移一位，相当于*2，右移一位，相当于/2

2419. 按位与最大的最长子数组

模拟

根据题意模拟，主要是代码细节要注意。

数学

主要多考虑组合数学

从起点到终点的所有路径：给定一个$n$和一个$k，n$代表要走的步数，$k$代表终点，从0出发，每次可以选择往左走或者往右走，走到$k$，有多少种路径？

假设$a$等于往右走的步数，往左走的步数为$k-a$,走到$n$时的步数为$a-(k-a)=a$，$a=(k+n)/2$
当且仅当$(k+n)$为偶数时有解
等价于从$k$步里面选$a$步往右走，所以结果是$C^{(k+n)/2}_k$

2400. 恰好移动 k 步到达某一位置的方法数目

C++如何计算组合数？

从n个里面选m个，当前这个选，就变为从n-1个里面选m-1个，当前不选，就变成从n-1个里面选m个。

根据公式:：$C_n^m=C^m_{n-1}+C_{n-1}^{m-1}$

#include<iostream>
using namespace std;

long long res[67][67]={0};
long long C(long long n,long long m){
    if(m==0 || m==n) return 1;
    if(res[n][m] != 0)return res[n][m];//保存状态
    return res[n][m] = C(n-1,m)+ C(n-1,m-1);//赋值给res[n][m]并返回
}
int main()
{
    printf("%ld",C(6,3));
    return 0;
}

排序不等式：
$a_1 \leq a_2 \leq … \leq a_n$
$b_1 \leq b_2 \leq … \leq b_n$

最大值= $a_1b_1+a_2b_2+…+a_nb_n$
最小值= $a_1b_n+a_2b_{n-1}+…+a_nb_1$

求解最大公约数和最小公倍数

最大公约数：数组中所有数都能整除的最大数
最小公倍数：数组中所有数的最小倍数

$a和b的最小公倍数=a*b/(a和b的最大公约数)$
求解最大公约数使用gcd(a,b)函数

902. 最大为 N 的数字组合

6234. 最小公倍数为 K 的子数组数目

2447. 最大公因数等于 K 的子数组数目