关键词：[算法] [二分查找] [DFS/BFS] [动态规划] [滑动窗口] [位运算]
Leetcode刷题目的：无疑是提高自己的编程和算法能力，算法是面试逃不过的环节；
之前都是刷每日一题，然后也有大半年没刷了，感觉并未真正学到啥东西，也没记住啥，之后开始按题型刷；
使用条件：有序数组+查找目标元素；
复杂度：O(log n)；
优化：
实际使用求中间mid索引建议用这种方法：
int mid = left + (right-left)/2 可以防止left+right溢出（超出整数范围）；
可以将查找目标元素扩展为 查找符合要求的元素，括号内为满足的条件，比如这一题：
注意前后端点的判断，不要越界，还有就是return条件的选择（这一题：搜索插入位置）;
双指针可以进行归并也可以进行翻转，对于不同类型的题目应合理运用；
对于这种题型，很明显归并是使用双指针的目的；
我自己的思路：不考虑排序的办法；
本题分三种情况，全正、全负和有正有负，所以分类讨论：
但显然，这一题仍可以用更巧妙的方法，使用两个指针分别指向位置 0和 n-1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况；
！还有一个常见的归并题，就是给你个非递减数组和一个目标值，让你找其中的两个数字使之和为目标值，明显的双指针归并；167. 两数之和 II - 输入有序数组 - 力扣（LeetCode） (leetcode-cn.com)
有些题需要不只需要翻转一次，使用比较巧妙，比如这一题：
先要整体翻转一次，然后两段各翻转一次；
本质就是通过双指针来维护一个窗口，随着右指针移动+状态的改变来判断是否移动左指针，从而改变滑动窗口；
惯用模板：
int ProblemName(string s)
{
// step1：特殊情况判断以及一些需要维护的变量（长度len、哈希表）
int len = s.size();
if (len <= 1)
return len;
map<char, int> m;
// step2：定义窗口的首尾端 (start, end)， 然后滑动窗口
int left = 0, right = 1;
int res = 1;
while (right < len)
{
// step3：更新滑动窗口内的状态
// step4：情况一 可变窗口
/*
如果题目的窗口长度固定：用一个if语句判断一下当前窗口长度是否超过限定长度
如果超过了，窗口左指针前移一个单位保证窗口长度固定, 在那之前, 先更新Step 1定义的(部分或所有)维护变量
if 窗口长度大于限定值:
更新 (部分或所有) 维护变量
窗口左指针前移一个单位保证窗口长度固定
*/
// step4：情况二 固定窗口
/*
如果题目的窗口长度可变: 这个时候一般涉及到窗口是否合法的问题
如果当前窗口不合法时, 用一个while去不断移动窗口左指针, 从而剔除非法元素直到窗口再次合法
在左指针移动之前更新Step 1定义的(部分或所有)维护变量
while 不合法:
更新 (部分或所有) 维护变量
不断移动窗口左指针直到窗口再次合法
*/
// step5：更新结果
right++;
}
return res;
}
比如这道题：无重复字符的最长子串，就是看可变窗口的选择
开始没想到固定窗口，还是按照可变窗口做的，虽然也过了，但是耗时太久，因为每进行一步都要对窗口状态进行判断从而决定left移到哪；而因为这里s2的字串要为s1，必然这个窗口的长度是等于s1的大小的，所以可以按照固定窗口的思路，代码就参照模板的step4：情况二 固定窗口；
bool checkInclusion(string s1, string s2)
{
int n = s1.length(), m = s2.length();
if (n > m)
{
return false;
}
vector<int> cnt1(26), cnt2(26);
for (int i = 0; i < n; ++i)
{
++cnt1[s1[i] - 'a'];
++cnt2[s2[i] - 'a'];
}
int left = 0;
int right = n;
while (right < m)
{
// 更新窗口状态
++cnt2[s2[right] - 'a'];
--cnt2[s2[left] - 'a'];
// 判断是否达到要求
if (cnt1 == cnt2)
{
return true;
}
left++;
right++;
}
return false;
}
用于图的遍历/最小路径问题，一般找到所有解用DFS，找到最优解用BFS，但其实二者是通用的，一般能用DFS的也能用BFS求解；
BFS是一种从中心向四周扩散的方式，而DFS是一条路走到尽头再回头；
DFS算法框架
int solution(int[][] matrix)
{
// 如果需要遍历数组找到多个入口
int res = 0;
for(遍历i、j)
{
if (符合入口条件)
{
// 进行dfs探索，并判断是否需要更新目标值
res = max(res, dfs(i, j, matrix));
}
}
return res;
}
// dfs的功能就是从(i,j)进去后能找到的最大覆盖范围
int dfs(int i, int j, int[][] matrix)
{
// step1：边界条件判断
if (条件1不满足 || 条件2不满足 || ......)
{
return 0;
}
// step2：条件满足，更正当前点的状态
matrix[i][j] = 0;
// step3：解决其它子问题->继续向相邻节点探索
int num = 1;
num += dfs(i + 1, j, matrix);
num += dfs(i - 1, j, matrix);
num += dfs(i, j + 1, matrix);
num += dfs(i, j - 1, matrix);
return num;
}
BFS算法框架
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
queue<Node> q; // 核⼼数据结构
set<Node> visited; // 避免⾛回头路
q.push(start); // 将起点加⼊队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这⾥判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加⼊队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点：更新步数在这⾥ */
step++;
}
}
图像渲染：
// bfs
vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int newColor)
{
// 广度优先搜索
queue<vector<int>> q;
int len_row = image.size(), len_col = image[0].size();
int oldColor = image[sr][sc];
vector<int> start = {sr, sc};
q.push(start);
vector<vector<bool>> vis(len_row, vector<bool>(len_col, false));
vector<vector<int>> pos = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vis[sr][sc] = true;
while (!q.empty())
{
int len = q.size();
while (len--)
{
vector<int> cur = q.front();
q.pop();
image[cur[0]][cur[1]] = newColor;
// 对上下左右进行遍历
for (auto v : pos)
{
int xx = cur[0] + v[0], yy = cur[1] + v[1];
if (xx >= 0 && xx < len_row && yy >= 0 && yy < len_col && !vis[xx][yy])
{
if (image[xx][yy] == oldColor)
{
q.push(vector<int>{xx, yy});
}
vis[xx][yy] = true;
}
}
}
}
return image;
}
// dfs递归版本
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
return dfs(image, sr, sc, newColor, image[sr][sc]);
}
public int[][] dfs(int[][] image, int i, int j, int newColor, int num){
if(i<0 || i>=image.length || j<0 || j>=image[0].length || image[i][j]==newColor || image[i][j]!=num){
}else{
int temp=image[i][j];
image[i][j]=newColor;
dfs(image, i+1, j, newColor, temp);
dfs(image, i-1, j, newColor, temp);
dfs(image, i, j+1, newColor, temp);
dfs(image, i, j-1, newColor, temp);
}
return image;
}
}
典型题就是这道题：岛屿的最大面积
// bfs
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>> &grid)
{
// bfs更妥
// 不用vis数据，把访问过的都置0就行
int len_row = grid.size();
if (len_row == 0)
return 0;
int len_col = grid[0].size();
// 表示四个方位
int pos[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
queue<vector<int>> q;
int res = 0;
for (int i = 0; i < len_row; i++)
{
for (int j = 0; j < len_col; j++)
{
// 找到了入口就开始bfs
if (grid[i][j] == 1)
{
// 从这个入口进入能找到岛屿的最大值
int cur = 0;
q.push(vector<int>{i, j});
grid[i][j] = 0;
while (!q.empty())
{
int len = q.size();
while (len--)
{
int x = q.front()[0], y = q.front()[1];
q.pop();
cur++;
// 在四个方向上找符合条件的点
for (auto v : pos)
{
int xx = x + v[0], yy = y + v[1];
if (xx >= 0 && xx < len_row && yy >= 0 && yy < len_col && grid[xx][yy] == 1)
{
grid[xx][yy] = 0;
q.push(vector<int>{xx, yy});
}
}
}
}
res = max(res, cur);
}
}
}
return res;
}
};
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
res = Math.max(res, dfs(i, j, grid));
}
}
}
return res;
}
private int dfs(int i, int j, int[][] grid) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0;
int num = 1;
num += dfs(i + 1, j, grid);
num += dfs(i - 1, j, grid);
num += dfs(i, j + 1, grid);
num += dfs(i, j - 1, grid);
return num;
}
}
合并二叉树
老是找不到DFS递归的入口点，现在只习惯写BFS；
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2)
{
queue<TreeNode *> q1, q2;
if (root1==nullptr || root2 == nullptr)
return root1 == nullptr ? root2 : root1;
q1.push(root1);
q2.push(root2);
while (!q1.empty() && !q2.empty())
{
TreeNode *cur1 = q1.front(), *cur2 = q2.front();
q1.pop();
q2.pop();
cur1->val += cur2->val;
if (cur1->left != nullptr && cur2->left != nullptr)
{
q1.push(cur1->left);
q2.pu sh(cur2->left);
}
else if (cur1->left == nullptr && cur2->left != nullptr)
{
cur1->left = cur2->left;
}
if (cur1->right != nullptr && cur2->right != nullptr)
{
q1.push(cur1->right);
q2.push(cur2->right);
}
else if (cur1->right == nullptr && cur2->right != nullptr)
{
cur1->right = cur2->right;
}
}
return root1;
}
};
DFS每次都让我大吃一惊，简洁易懂；
class Solution {
public:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr) {
return t2;
}
if (t2 == nullptr) {
return t1;
}
auto merged = new TreeNode(t1->val + t2->val);
merged->left = mergeTrees(t1->left, t2->left);
merged->right = mergeTrees(t1->right, t2->right);
return merged;
}
};
填充每个节点的下一个右侧节点指针
这道题是真的厉害，bfs层次遍历肯定没问题，但是复杂度会达到O(N)，所以必须得用dfs；
同一个父节点的孩子用 next 连接倒还容易，root->left->next=root->right；但是不同父节点的孩子用next连接始终想不通，看了题解弄懂，按照层次遍历，比如我需要5 -> next 指向6，我可以利用5的父节点2 -> next =3 来实现，那么就是root->right->next=root->next->left；简直精辟；
class Solution {
public:
void dfs(Node *root)
{
if (root == NULL || root->left == NULL)
return;
// 处理同一个父节点的连接情况
root->left->next = root->right;
if (root->next)
// 处理不同父节点的连接情况
root->right->next = root->next->left;
dfs(root->left);
dfs(root->right);
}
};
BFS跟DFS都能用于搜索，但不同的是，BFS能够快速地找到最短路径，因为他是从中心点一步步扩散的，最先到的那一层即为最短路径；
想问题一定要从简单的情况入手，尤其是涉及到DFS、BFS和动态规划的题！
01 矩阵
先不要想复杂，从简单的情况入手，如果我们这个矩阵只有一个0，剩下的全是1，怎么办？可以从 0 的位置开始进行 广度优先搜索。广度优先搜索可以找到从起点到其余所有点的 最短距离，因此如果我们从 0 开始搜索，每次搜索到一个 1，就可以得到 0 到这个 1 的最短距离，也就离这个 1 最近的 0 的距离了（因为矩阵中只有一个 0）。
现在回归题目的情况，从1个0变成了多个0的情况，那么可以把这些0看做一个整体，从这个整体开始一层一层外外面散开；
class Solution {
private:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dist(m, vector<int>(n));
// seen数组记录某点是否访问过
vector<vector<int>> seen(m, vector<int>(n));
queue<pair<int, int>> q;
// 将所有的 0 添加进初始队列中
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
q.emplace(i, j);
seen[i][j] = 1;
}
}
}
// 广度优先搜索
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
// 往外扩散一层，得到的必是最短距离
for (int d = 0; d < 4; ++d) {
int ni = i + dirs[d][0];
int nj = j + dirs[d][1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]) {
dist[ni][nj] = dist[i][j] + 1;
q.emplace(ni, nj);
seen[ni][nj] = 1;
}
}
}
return dist;
}
};
动态规划的方法懒得弄懂了，看起来比较麻烦，先掌握DFS和BFS；
这道题弄懂后，又做了类似的一道题：腐烂的橘子；相比于01矩阵，这道题多了一些边界的判断，但本质是一样的！
递归的思想是比较难想到的，一但用递归的形式做出来了，必然又是简洁易懂的；总得来说就是把大问题拆分成小问题，而且是重复的子问题，我做这一步，下一步由你来做的思想；
这道题我是用归并解的，但看到了递归这么简介的形式，也是惊呆了；练一种方法就要专门用这种方法解题，要不然就没意义了；
链表递归最有意思的就是能够递归地将众多节点连接起来成一个链表；
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
// 我来判断当前节点l1和l2哪个小，其余的交给你来判断
// 链表递归最有意思的就是能够递归地连接起来成一个链表
if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}else{
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
}
};
然后做了下反转链表，也是再一次感受到了自己的无知以及C++的深奥，题是做出来了，也巩固了C++的一些知识点：
如果函数的形参不加引用类型，那么无论参数是变量还是地址，都是以值的形式传递；在做下面这道题的时候，加深了这一块的知识：
利用递归解题：
class Solution
{
public:
ListNode *rev(ListNode *head, ListNode *&new_head)
{
if (head->next == nullptr)
{
new_head = head;
return head;
}
ListNode *cur = rev(head->next, new_head);
cur->next = head;
return head;
}
ListNode *reverseList(ListNode *head)
{
if(head==nullptr)
return nullptr;
ListNode *new_head = nullptr;
rev(head, new_head)->next = nullptr;
return new_head;
}
};
对于函数 rev ，如果形参new_head前面不加引用类型，那么传递的是地址的值，也就是说，随着递归一次次开辟栈，栈局部变量 new_head 仅仅会在进行到最后一个结点时，将自己的地址值修改为 head ，此时 return，那么栈清空，变量释放，回到上一个栈是 new_head仍为 nullptr；
如果加了 & 引用类型，如果 rev 调用多少次，都是用的new_head本身，并不会在栈中创建和它相等的局部变量；
当然，这并不否认可以通过函数传指针来交换两个变量这一结果：
void fun(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=*a;
}
组合
这道求组合的题目倒还不用考虑顺序的问题，回溯的基本框架就是：
for(::)
{
// 加入当前元素
cur.push_back(i);
// 去探索基于当前元素的后面的子问题
dfs(n, k, i + 1, cur, res);
// 回溯，移除当前元素，接着探索
cur.pop_back();
}
class Solution
{
public:
void dfs(int &n, int &k, int now, vector<int> &cur, set<vector<int>> &res)
{
// 剪枝：如果cur长度加上剩余没选的元素[now,n]之和小于k，说明后面就算全选也达不到要求
if (cur.size() + n - now + 1 < k)
return;
if (cur.size() == k)
{
res.insert(cur);
return;
}
for (int i = now; i <= n; i++)
{
cur.push_back(i);
dfs(n, k, i + 1, cur, res);
cur.pop_back();
}
}
vector<vector<int>> combine(int n, int k)
{
set<vector<int>> res;
vector<int> cur;
dfs(n, k, 1, cur, res);
vector<vector<int>> ret(res.size());
int index = 0;
for (auto v : res)
{
ret[index++] = v;
}
return ret;
}
};
当然，全排列的话，只用在组合的基础上加个顺序就行了，需要额外用到一个数组用于继续某个元素是否被访问过；
class Solution
{
public:
vector<vector<int>> res;
void dfs(vector<int> &nums, vector<int> &cur, vector<bool> &vis)
{
if (cur.size() == nums.size())
{
res.push_back(cur);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (!vis[i])
{
cur.push_back(nums[i]);
vis[i] = true;
dfs(nums, cur, vis);
vis[i] = false;
cur.pop_back();
}
}
}
vector<vector<int>> permute(vector<int> &nums)
{
vector<bool> vis(nums.size(), false);
vector<int> cur;
dfs(nums, cur, vis);
return res;
}
};
字母大小写全排列这道题也是个组合问题，不过是特定条件下的组合，解题其实差不多；
动态规划问题的⼀般形式就是求最值，既然是要求最值，核⼼问题是什么呢？求解动态规划的核⼼问题是穷举，因为要求最值，肯定要把所有可⾏的答案穷举出来，然后在其中找最值。
⾸先，动态规划的穷举有点特别，因为这类问题存在「重叠⼦问题」，如果 暴⼒穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优 化穷举过程，避免不必要的计算。
⽽且，动态规划问题⼀定会具备「最优⼦结构」，才能通过⼦问题的最值得到原问题的最值。
虽然动态规划的核⼼思想就是穷举求最值，但是问题可以千变万化， 穷举所有可⾏解其实并不是⼀件容易的事，只有列出正确的「状态转移⽅程」才能正确地穷举。
以上提到的重叠⼦问题、最优⼦结构、状态转移⽅程就是动态规划三要素。 具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移⽅程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的⼀个思维框架，辅助你思考状态转移⽅程：
明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」，即递推公式 -> 明确 base case
动态规划5步曲：
（一）暴力递归：
这是递归树：
PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复 杂度，寻找算法低效的原因都有巨⼤帮助；
观察递归树，很明显发现了算法低效的原因：存在⼤量重复计算，⽐如 f(18) 被计算了两次，⽽且你可以看到，以 f(18) 为根的这个递归树体量 巨⼤，多算⼀遍，会耗费巨⼤的时间。更何况，还不⽌ f(18) 这⼀个节点 被重复计算，所以这个算法及其低效。
这就是动态规划问题的第⼀个性质：重叠⼦问题；
（二）带备忘录的递归解法
造⼀个「备忘录」，每次算出某个⼦问题的答案后别急着返 回，先记到「备忘录」⾥再返回；每次遇到⼀个⼦问题先去「备忘录」⾥查 ⼀查，如果发现之前已经解决过这个问题了，直接把答案拿出来⽤，不要再 耗时去计算了。⼀般使⽤⼀个数组充当这个「备忘录」，当然你也可以使⽤哈希表（字 典），思想都是⼀样的。
实际上，带「备忘录」的递归算法，把⼀棵存在巨量冗余的递归树通过「剪 枝」，改造成了⼀幅不存在冗余的递归图，极⼤减少了⼦问题（即递归图中 节点）的个数。
⾄此，带备忘录的递归解法的效率已经和迭代的动态规划解法⼀样了。实际 上，这种解法和迭代的动态规划已经差不多了，只不过这种⽅法叫做「⾃顶 向下」，动态规划叫做「⾃底向上」。
从上向下延 伸，都是从⼀个规模较⼤的原问题⽐如说 f(20) ，向下逐渐分解规模，直 到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「⾃顶向下」。
反过来，我们直接从最底下，最简单，问题规模最⼩的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20) ，这就是动 态规划的思路，这也是为什么动态规划⼀般都脱离了递归，⽽是由循环迭代完成计算。
（三）动态规划
把这个「备忘录」独⽴出来成为⼀ 张表，就叫做 DP table 吧，在这张表上完成「⾃底向上」；
这个 DP table 特别像之前那个「剪枝」后 的结果，只是反过来算⽽已。实际上，带备忘录的递归解法中的「备忘 录」，最终完成后就是这个 DP table，所以说这两种解法其实是差不多的， ⼤部分情况下，效率也基本相同。
引出「状态转移⽅程」这个名词，实际上就是描述问题结构的数学形 式：
为啥叫「状态转移⽅程」？为了听起来⾼端。你把 f(n) 想做⼀个状态 n，这 个状态 n 是由状态 n - 1 和状态 n - 2 相加转移⽽来，这就叫状态转移，仅此 ⽽已；
「状态转移⽅程」的重要性，它是 解决问题的核⼼。很容易发现，其实状态转移⽅程直接代表着暴⼒解法。千万不要看不起暴⼒解，动态规划问题最困难的就是写出状态转移⽅程，即这个暴⼒解。优化⽅法⽆⾮是⽤备忘录或者 DP table。
这个例⼦的最后，讲⼀个细节优化。细⼼的读者会发现，根据斐波那契数列 的状态转移⽅程，当前状态只和之前的两个状态有关，其实并不需要那么⻓ 的⼀个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就⾏ 了。所以，可以进⼀步优化，把空间复杂度降为 O(1)：
动态规划的另⼀个重要特性「最优⼦结构」，怎么没有涉及？下 ⾯会涉及。斐波那契数列的例⼦严格来说不算动态规划，因为没有涉及求最 值，以上旨在演⽰算法设计螺旋上升的过程。
题⽬：给你 k 种⾯值的硬币，⾯值分别为 c1, c2 … ck ，每种硬 币的数量⽆限，再给⼀个总⾦额 amount ，问你最少需要⼏枚硬币凑出这个 ⾦额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
// coins 中是可选硬币⾯值，amount 是⽬标⾦额
int coinChange(int[] coins, int amount);
⽐如说 k = 3 ，⾯值分别为 1，2，5，总⾦额 amount = 11 。那么最少需 要 3 枚硬币凑出，即 11 = 5 + 5 + 1。 你认为计算机应该如何解决这个问题？显然，就是把所有肯能的凑硬币⽅法 都穷举出来，然后找找看最少需要多少枚硬币。
（一）暴力递归
⾸先，这个问题是动态规划问题，因为它具有「最优⼦结构」的。要符合 「最优⼦结构」，⼦问题间必须互相独⽴。
什么叫子问题相互独立？
⽐如说，你的原问题是考出最⾼的总成绩，那么你的⼦问题就是要把语⽂考 到最⾼，数学考到最⾼…… 为了每门课考到最⾼，你要把每门课相应的选 择题分数拿到最⾼，填空题分数拿到最⾼…… 当然，最终就是你每门课都 是满分，这就是最⾼的总成绩。 得到了正确的结果：最⾼的总成绩就是总分。因为这个过程符合最优⼦结 构，“每门科⽬考到最⾼”这些⼦问题是互相独⽴，互不⼲扰的。
但是，如果加⼀个条件：你的语⽂成绩和数学成绩会互相制约，此消彼⻓。 这样的话，显然你能考到的最⾼总成绩就达不到总分了，按刚才那个思路就 会得到错误的结果。因为⼦问题并不独⽴，语⽂数学成绩⽆法同时最优，所 以最优⼦结构被破坏。
回到凑零钱问题，为什么说它符合最优⼦结构呢？⽐如你想求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10 的最少硬币 数（⼦问题），你只需要把⼦问题的答案加⼀（再选⼀枚⾯值为 1 的硬币） 就是原问题的答案，因为硬币的数量是没有限制的，⼦问题之间没有相互 制，是互相独⽴的。
如何列出正确的状态转移⽅程？
step1：确定状态
也就是原问题和⼦问题中变化的变量。由于硬币数量⽆ 限，所以唯⼀的状态就是⽬标⾦额 amount 。
step2：然后确定 dp 函数的定义
当前的⽬标⾦额是 n ，⾄少需要 dp(n) 个硬 币凑出该⾦额。
step3：然后确定「选择」并择优
也就是对于每个状态，可以做出什么选择改变当 前状态。具体到这个问题，⽆论当的⽬标⾦额是多少，选择就是从⾯额列表 coins 中选择⼀个硬币，然后⽬标⾦额就会减少：
step4：最后明确 base case
显然⽬标⾦额为 0 时，所需硬币数量为 0；当⽬标⾦额 ⼩于 0 时，⽆解，返回 -1：
⾄此，状态转移⽅程其实已经完成了，以上算法已经是暴⼒解法了，以上代 码的数学形式就是状态转移⽅程：
⾄此，这个问题其实就解决了，只不过需要消除⼀下重叠⼦问题，⽐如 amount = 11, coins = {1,2,5} 时画出递归树看看：
时间复杂度分析：⼦问题总数 x 每个⼦问题的时间。 ⼦问题总数为递归树节点个数，这个⽐较难看出来，是 O(nk)，总之是指 数级别的。每个⼦问题中含有⼀个 for 循环，复杂度为 O(k)。所以总时间复 杂度为 O(k * nk)，指数级别。
（二）带备忘录的递归
不画图了，很显然「备忘录」⼤⼤减⼩了⼦问题数⽬，完全消除了⼦问题的 冗余，所以⼦问题总数不会超过⾦额数 n，即⼦问题数⽬为 O(n)。处理⼀个 ⼦问题的时间不变，仍是 O(k)，所以总的时间复杂度是 O(kn)。
（三）dp数组的迭代解法
当然，我们也可以⾃底向上使⽤ dp table 来消除重叠⼦问题， dp 数组的定 义和刚才 dp 函数类似，定义也是⼀样的：
dp[i] = x 表⽰，当⽬标⾦额为 i 时，⾄少需要 x 枚硬币。
PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount ⾦额的硬 币数最多只可能等于 amount （全⽤ 1 元⾯值的硬币），所以初始化为 amount + 1 就相当于初始化为正⽆穷，便于后续取最⼩值。
第⼀个斐波那契数列的问题，解释了如何通过「备忘录」或者「dp table」 的⽅法来优化递归树，并且明确了这两种⽅法本质上是⼀样的，只是⾃顶向 下和⾃底向上的不同⽽已。
第⼆个凑零钱的问题，展⽰了如何流程化确定「状态转移⽅程」，只要通过 状态转移⽅程写出暴⼒递归解，剩下的也就是优化递归树，消除重叠⼦问题 ⽽已。
先拿着道题来练手，爬楼梯，也算是典型了
带备忘录的递归：
class Solution
{
public:
int dfs(int n, vector<int> &rec)
{
if (n == 1)
return 1;
if (n == 2)
return 2;
int res = 0;
if (rec[n - 1] != -1)
res += rec[n - 1];
else
res += dfs(n - 1, rec);
if (rec[n - 2] != -1)
res += rec[n - 2];
else
res += dfs(n - 2, rec);
rec[n] = res;
return res;
}
int climbStairs(int n)
{
if (n == 1)
return 1;
vector<int> rec(n + 1, -1);
rec[1] = 1;
rec[2] = 2;
return dfs(n, rec);
}
};
动态规划：
class Solution
{
public:
int climbStairs(int n)
{
if (n == 1)
return 1;
vector<int> rec(n + 1, -1);
rec[1] = 1;
rec[2] = 2;
for (int i = 3; i <= n; i++)
{
rec[i] = rec[i - 1] + rec[i - 2];
}
return rec[n];
}
};
优化为空间复杂度为 O(1)：
class Solution
{
public:
int climbStairs(int n)
{
if (n == 1)
return 1;
if (n == 2)
return 2;
vector<int> rec(n + 1, -1);
int pre1 = 1;
int pre2 = 2;
int res;
for (int i = 3; i <= n; i++)
{
res = pre1 + pre2;
pre1 = pre2;
pre2 = res;
}
return res;
}
};
又来一典型题：打家劫舍
按照之间的思路，明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case，一下感觉动态规划很明了了：
//备忘录+递归
class Solution
{
public:
// 打劫n家最多得到dfs(n)的钱
int dfs(int n, vector<int> &nums, vector<int> &rec)
{
if (n < 0)
return 0;
if (n == 1)
return rec[1];
int res;
// 打劫下一家或者打劫这一家再跳到下下家；
if (rec[n - 1] != -1 && rec[n - 2] != -1)
{
res = max(rec[n - 1], nums[n] + rec[n - 2]);
}
else if (rec[n - 1] != -1)
{
res = max(rec[n - 1], nums[n] + dfs(n - 2, nums, rec));
}
else if (rec[n - 2] != -1)
{
res = max(dfs(n - 1, nums, rec), nums[n] + rec[n - 2]);
}
else
{
res = max(dfs(n - 1, nums, rec), nums[n] + dfs(n - 2, nums, rec));
}
rec[n] = res;
return res;
}
int rob(vector<int> &nums)
{
int len = nums.size();
if (len == 0)
return 0;
if (len == 1)
return nums[0];
if (len == 2)
return max(nums[0], nums[1]);
vector<int> rec(len, -1);
rec[0] = nums[0];
rec[1] = max(nums[0], nums[1]);
return dfs(len - 1, nums, rec);
}
};
// dp数组
class Solution
{
public:
int rob(vector<int> &nums)
{
int len = nums.size();
if (len == 0)
return 0;
if (len == 1)
return nums[0];
if (len == 2)
return max(nums[0], nums[1]);
vector<int> rec(len, -1);
rec[0] = nums[0];
rec[1] = max(nums[0], nums[1]);
for (int i = 2; i < len; i++)
{
rec[i] = max(rec[i - 1], nums[i] + rec[i - 2]);
}
return rec[len - 1];
}
};
虽然说备忘录和dp数组的效率差不多，但实际上leetcode跑出来还是有一定的区别的：
优化成常数空间：
class Solution
{
public:
int rob(vector<int> &nums)
{
int len = nums.size();
if (len == 0)
return 0;
if (len == 1)
return nums[0];
if (len == 2)
return max(nums[0], nums[1]);
int a = nums[0];
int b = max(nums[0], nums[1]);
int res;
for (int i = 2; i < len; i++)
{
res = max(b, nums[i] + a);
a = b;
b = res;
}
return res;
}
};
典型例题：三角形最小路径和
// 带备忘录的递归
class Solution
{
public:
// 走到n层的路径和dfs(n)
int dfs(int n, vector<vector<int>> &triangle, int m, vector<vector<int>> &rec)
{
if (n == triangle.size())
{
return 0;
}
// 走左孩子和走右孩子8
int res;
if (rec[n + 1][m] != INT32_MAX && rec[n + 1][m + 1] != INT32_MAX)
{
res = min(rec[n + 1][m], rec[n + 1][m + 1]) + triangle[n][m];
}
else if (rec[n + 1][m] != INT32_MAX)
{
res = min(rec[n + 1][m], dfs(n + 1, triangle, m + 1, rec)) + triangle[n][m];
}
else if (rec[n + 1][m + 1] != INT32_MAX)
{
res = min(dfs(n + 1, triangle, m, rec), rec[n + 1][m + 1]) + triangle[n][m];
}
else
{
res = min(dfs(n + 1, triangle, m, rec), dfs(n + 1, triangle, m + 1, rec)) + triangle[n][m];
}
rec[n][m] = res;
return res;
}
int minimumTotal(vector<vector<int>> &triangle)
{
int n = triangle.size();
if (n == 1)
return triangle[0][0];
vector<vector<int>> rec(n, vector<int>(n, INT32_MAX));
for (int i = 0; i < n; i++)
{
rec[n - 1][i] = triangle[n - 1][i];
}
return dfs(0, triangle, 0, rec);
}
};
// dp数组
class Solution
{
public:
int minimumTotal(vector<vector<int>> &triangle)
{
int n = triangle.size();
if (n == 1)
return triangle[0][0];
vector<vector<int>> rec(n, vector<int>(n, INT32_MAX));
for (int i = 0; i < n; i++)
{
rec[n - 1][i] = triangle[n - 1][i];
}
for (int i = n - 2; i >= 0; i--)
{
for (int j = 0; j <= i; j++)
{
rec[i][j] = min(rec[i + 1][j], rec[i + 1][j + 1]) + triangle[i][j];
}
}
return rec[0][0];
}
};
对空间复杂度进行优化，即可以把rec这个二维数组优化成一个一维数组，因为在上个解法中，其实从下往上每用完一层那一层后面就没用了，所以可以用一个一维数组进行覆盖，一层一层覆盖；
class Solution
{
public:
int minimumTotal(vector<vector<int>> &triangle)
{
int n = triangle.size();
if (n == 1)
return triangle[0][0];
vector<int> rec(n, INT32_MAX);
for (int i = 0; i < n; i++)
{
rec[i] = triangle[n - 1][i];
}
for (int i = n - 2; i >= 0; i--)
{
for (int j = 0; j <= i; j++)
{
rec[j] = min(rec[j], rec[j + 1]) + triangle[i][j];
}
}
return rec[0];
}
};
典型例题：Leetcode链接最长递增子序列
dp[i]表示以元素num[i]结尾的最长递增子序列长度；if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);，很容易理解，如果内循环中对nums[i]与前面的各个元素比较大小，若nums[i]较大，说明他可以作为以nums[j]结尾的递增子序列的下一个元素，长度+1，然后筛选出长度最大的；dp[i]的值；
class Solution
{
public:
int lengthOfLIS(vector<int> &nums)
{
int len = nums.size();
int res = 1;
vector<int> dp(len, 1); //dp[i]dp[i]表示到以元素i结尾的最大递增子序列长度
for (int i = 1; i < len; i++)
{
int cur = dp[i];
for (int j = 0; j < i; j++)
{
if (nums[j] < nums[i])
{
cur = max(cur, dp[j] + 1);
}
}
dp[i] = cur;
res = max(dp[i], res);
}
return res;
}
};
Leetcode链接：最长重复子数组
动态规划五部曲，关键第一步：
dp[i][j]的含义我选择的是以nums1[i]和nums2[j]结尾的公共最长子数组长度if (nums1[i] == nums2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;就是如果nums1[i]==nums2[j]，那么dp[i][j]最少为1，同时还要看他们前面的元素是否为公共子数组的结尾，如果是，那么就续上这个公共子数组；dp[i][j]的含义是以nums1[i]和nums2[j]结尾的公共最长子数组长度，那么要对第一行和第一列进行初始化，比如dp[0-len][0]，要把nums1[i]==num2[0]对应的dp[i][0]初始化为1；这里建议把dp[i][j]的含义换位以nums1[i-1]和nums2[j-1]结尾的公共最长子数组长度，这样就能省略初始化的部分，把他们划到循环里面
class Solution
{
public:
int findLength(vector<int> &nums1, vector<int> &nums2)
{
int len1 = nums1.size(), len2 = nums2.size();
vector<vector<int>> dp(len1, vector<int>(len2, 0)); //dp[i][j]表示以nums1[i]结尾，以nums2[j]结尾的公共最长子数组长度
// 处理边界条件
for (int i = 0; i < len1; i++)
{
if (nums1[i] == nums2[0])
dp[i][0] = 1;
}
for (int j = 0; j < len2; j++)
{
if (nums1[0] == nums2[j])
dp[0][j] = 1;
}
// 状态转移，注意双循环
for (int i = 1; i < len1; i++)
{
for (int j = 1; j < len2; j++)
{
if (nums1[i] == nums2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
// 输出结果，找最大值
int res = 0;
for (auto v : dp)
{
for (auto e : v)
{
res = max(res, e);
}
}
return res;
}
};
Leetcode链接：最长公共子序列
这是一个比较有意思的题，虽然只是把重复子数组变成了子序列，多了不连续的问题，但难度上升了挺多；
依然还是五部曲：
dp[i][j]是以text1[0~i-1]和text2[0~j-1]的最长公共子序列长度；dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])同时，如果text1[i - 1] == text2[j - 1]，那么dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j])，为什么不直接dp[i][j]+=1，是因为后期出现了冗余元素重复计算的问题，后面会解释；class Solution
{
public:
int longestCommonSubsequence(string text1, string text2)
{
int len1 = text1.size(), len2 = text2.size();
// dp[i][j]的含义是以text1[0~i-1]和text2[0~j-1]最长公共子序列长度
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for (int i = 1; i <= len1; i++)
{
for (int j = 1; j <= len2; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (text1[i - 1] == text2[j - 1])
{
// 注意这里有个小问题，如text1之前有个数text1[k]与text2[j]匹配过且dp[k][j]+1了，那么text1[k之后]与text2[j]再匹配就会出错
dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
}
}
}
return dp[len1][len2];
}
};
之前我是在if判断里面直接dp[i][j]+=1，后来遇到错误了：
这一组的答案明显为1，仅有两个 b 为公共子序列，但错误的语句dp[i][j]+=1会让最后结果为2：
所以我们这采用了dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j])，仅当A[i]和B[i]初次匹配时才+1，否则继续沿用左和上的最大值；
算法中，位运算可以巧妙运用在一下几个方面：
1、判断奇偶数 => x&1
2、判断数x中第k ( 从右至左 ) 位是1还是0
法1：( x >> ( k - 1 ) ) & 1
法2：x & ( 1 << ( k - 1 ) )
3、交换两个整数变量 a , b 的值
a = a ^ b;
b = b ^ a;
a = a ^ b;
这里为什么能这样做，在后面的异或运算中会说明；
4、不用判断语句，求整数绝对值
return (value ^ (value >> 31))-(value >>31)
同样在异或运算中说明；
二进制中1的个数
描述：实现一个函数，输入一个正整数，输出该数二进制表示中1的个数。
例：9的二进制表示为1001，有2位是1；
思路：循环运用判断x的第k位是否为1的方法；
int count=0;
while(value)
{
count += value & 1;
value = value >> 1;
}
return count;
方法二：
& 运算有这样一个性质：a = ( a - 1 ) & a ； 这样a就能消除最低位的一个1；
思路：利用这一性质，我们可以每次将value-1，然后与自己&，能做多少次这样的操作就说明有多少个1；
int count=0;
while(value)
{
value = (value - 1) & value;
count++;
}
return count;
2的幂
这里我刚开始的做法是按位移，然后&n，但仅仅只是简单的运用了位运算，没学到精髓；看了评论区大佬的：如果 n 是2的 x 次幂，那么 n-1 一定是第 1 到 x-1 位都为 1，那么此时n&n-1必定为0；
class Solution
{
public:
bool isPowerOfTwo(int n)
{
if (n <= 0)
return false;
if ((n & n - 1) == 0)
return true;
return false;
}
};
异或又称不进位加法，两个数相异或，对应位相同则为0，不同则为1；
具有以下性质：
1、a ^ a = 0；
2、0 ^ a = a；
3、异或具有交换律和结合律
b ^ c = c ^ b；
a ^ b ^ c = a ^ ( b ^ c) = ( a ^ b ) ^ c；
4、( -1 ) ^ a =！a;
交换两个变量的值
交换变量a,b的值
a = a ^ b;
b = b ^ a;
a = a ^ b;
利用异或运算的交换律和结合律，可以得到如下：
1、a = a ^ b;
2、b = b ^ a;
把1式代入2式中，此时 b = b ^ ( a ^ b ) ，则 b = b ^ b ^ a = a;
3、a = a ^ b;
将1式和 b = a 代入3式，则 a = a ^ b ^ a = b;
不用判断语句，求整数绝对值
return (value ^ (value >> 31))-(value >>31)
1、若value为正数，则value二进制表示中最高位一定为0，那么 value >> 31 =0;
value ^ (value >> 31) = value ^ 0 = value;
value - (value >> 31) = value - 0 = value;
即正数的绝对值仍是自身；
2、若value为负数，则value二进制表示中最高位一定为1，那么 value >> 31 = 111…1 ,一共32个1，即-1；
value ^ (value >> 31) = ! value;
而负数以补码形式存放，补码等于绝对值的原码取反+1；
那么这里 ! value - (value >> 31) => ! value +1 即得到的是value的绝对值；
如果理解有困难，可以看这个例子：
如何找唯一成对的数？
问题描述：1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，在不用辅助存储空间的前提下，设计一个算法，将它找出来；
思路：根据异或性质1： a ^ a = 0；可以用来去重；
令T = 1 ^ 2 ^ 3 ^… ^ 1000 ；
那么遍历数组的同时将当前数字与 T 异或，在数组中只出现一次的数字会与 T 中的该数字相抵消，从而去重；最终会剩下重复的那个元素，因为它在数组和T中一共出现3次；
举一个只有11个数的例子： 重复的元素在任意位置出现都是可以找出来的；
int T=0;
for(int i=1;i<=1000;i++)
{
T=T^i;
}
for(int i=0;i<=1000;i++)
{
T=T^A[i];
}
return T;
只出现一次的数字
利用异或的第一个性质：0^a=a;a^a=0 那么数组里面成对的数一旦异或，必定归为0，即相互抵消，最后剩下的就是落单的数；
异或 + 与 + 移位= 加法
2的二进制形式0010
3的二进制形式0011
5的二进制形式0101
2^3 ：0001 ；2&3 ：0010，那么2+3=（2&3）<<1 + 2^3，由于还是不能用加号，所以把它又进行一次，此时a=0100，b=0001，那么 a+b = (a&b)<<1 + a^b，此时(a&b)<<1为0，所以直接输出a^b的值即可，即0101=5；
class Solution {
public:
int getSum(int a, int b) {
while(b != 0)
{
unsigned int carry = (unsigned int)(a & b) << 1; // 相加只算进位的结果
a ^= b; // 无进位相加结果
b = carry;
}
return a;
}
};
一般而言，求解某数是否为2 or 3 or 10的幂，这种的问题用循环和递归马上就能写出，但往往题目会加条件，比如你能不使用循环或者递归来完成本题吗？
如果不用循环和递归，怎么写，就要用到数论的技巧，以3的幂为例：
在题目给定的 32 位有符号整数的范围内，最大的 33 的幂为 319 = 11622614673 ；所以，我们只需要判断 nn 是否是 319的约数即可；此外，这里需要特殊判断 n 是负数或 0 的情况：
class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
};
主要是无限循环小数如何处理，