前缀和
一维
二维
例题
304. 二维区域和检索 – 矩阵不可变 – 力扣（LeetCode）
思路解析
练习：
1277. 统计全为 1 的正方形子矩阵 – 力扣（LeetCode）
DP
二维矩阵DP
1277. 统计全为 1 的正方形子矩阵 – 力扣（LeetCode）
网格图DP
3459. 最长 V 形对角线段的长度 – 力扣（LeetCode）
解决思路：模拟人走路（记忆化搜索），对于当前位置，需要有以下参数：
- 当前的位置信息：i，j
- 当前沿着哪条对角线进行移动：k
- 当前位置是否还有转向的机会：can_turn
- 当前位置的值是否符合要求： target
Q1：递归的值如何返回呢？
解决办法（灵神的思路）：设置一个矩阵 m * n，每格为 array<array<int, 2>, 4> – 四个对角线，每个对角线中还未转向/已转向的路径长度最值
例： [[2, 5], [1, 1], [0, 3], [0, 0]] – [1,1]中的第二个1表示当前位置右上角对角线已经转向的符合题目要求的最大路径长度
这样对于可以转向的节点的最值有两个情况需要对比：直走的最长路径和转向后的最长路径的最值
代码如下：
class Solution {
public:
/*
该类型题属于网格图DP，可以模拟人记忆化搜索（递归写法）
对于当前的位置,需要哪些参数来确定下一步走到哪呢？
(i, j) - 当前位置
k - 沿对角线方向
CanTurn - 是否可以转弯
target - 下一步的位置的数必须是什么
Q：返回值是？
模拟每一步，返回值为递归数 + 1
灵神在此处有个神中神的操作：
对于m*n的矩阵，用memo[i][j][k][canturn]来记录接下来可以走的最长路长，接下来递归碰到了，就不需要再执行了,直接返回即可
*/
// 静态成员函数，记录四个转向（沿顺时针转90°）的变化量， 这样 (k + 1) % 4 -生成环
static constexpr int rotate90[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
int lenOfVDiagonal(vector<vector<int>>& grid) {
int row = grid.size(), column = grid[0].size();
// memo 矩阵（十分牛逼的操作）
vector memo(row, vector<array<array<int, 2>, 4>>(column));
int ans = 0;
// lambda 递归
auto dfs = [&](this auto&& dfs, int i, int j, int k, bool CanTurn, int target){
// 此处的 i, j 视为上一步的位置
i += rotate90[k][0];
j += rotate90[k][1];
// 判断退出递归条件
if(i < 0 || j < 0 || i >= row || j >= column || grid[i][j] != target){
return 0;
}
// 引地址取 memo
int& ref = memo[i][j][k][CanTurn];
// 若ref有值，则直接返回ref (之前递归已经记录下来的)
if(ref){
return ref;
}
// 若ref无值，则需要递归求值
ref = dfs(i, j, k, CanTurn, 2 - target) + 1;
// 递归 (是否能转向)
if(CanTurn){
// 在转向的十字路口的ref值会计算两次，一次是未转向的，一次是转向的，需要返回的是最值
ref = max(ref, dfs(i, j, (k + 1)%4, false, 2 - target) + 1);
}
return ref;
};
// 遍历找1,然后四个方向递归找最值
for(int i = 0; i < row; ++i){
for(int j = 0; j < column; ++j){
if(grid[i][j] == 1){
for(int k = 0; k < 4; ++k){
ans = max(ans, dfs(i, j, k, true, 2) + 1);
}
}
}
}
return ans;
}
};在理解上述代码情况下，可对算法进一步优化：最优化减枝，优化方向：
- 四个方向走都有其理论最值，如果当前的ans大于现要走的方向的理论最值，就不需要再去递归该路径了
- 同样的道理，在转向的节点上，若当前的ref大于在转向节点要走的方向的理论最值，就不需要去递归转向后的路径了
- 未转向的直线上只会出现一个1，因此若 memo[i][j][k][can_turn = ture] 有值，就不需要再修改其值
class Solution {
public:
// 静态成员函数，记录四个转向（沿顺时针转90°）的变化量， 这样 (k + 1) % 4 -生成环
static constexpr int rotate90[4][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1}};
int lenOfVDiagonal(vector<vector<int>>& grid) {
int row = grid.size(), column = grid[0].size();
// memo 矩阵（十分牛逼的操作）
vector memo(row, vector<array<array<int, 2>, 4>>(column));
// 优化3需要对memo矩阵进行修改，只记录不能转向下的ref值 (空间优化)
int ans = 0;
// lambda 递归
auto dfs = [&](this auto&& dfs, int i, int j, int k, bool CanTurn, int target){
// 此处的 i, j 视为上一步的位置
i += rotate90[k][0];
j += rotate90[k][1];
// 判断退出递归条件
if(i < 0 || j < 0 || i >= row || j >= column || grid[i][j] != target){
return 0;
}
// 引地址取 memo
int& ref = memo[i][j][k][CanTurn];
// 若ref有值，则直接返回ref (之前递归已经记录下来的)
if(ref){
return ref;
}
// 若ref无值，则需要递归求值
ref = dfs(i, j, k, CanTurn, 2 - target) + 1;
// 递归 (是否能转向)
if(CanTurn){
// 优化2：若当前的ref大于当前节点转向后的理论最值，那么就不需要递归转向了
// 左上方， 理论最值为 min(i + 1 , j + 1);
// 右上方, 理论最值为 min(i + 1, column - j);
// 右下方, 理论最值为 min(row - i, column - j);
// 左下方, 理论最值为 min(row - i, j + 1);
int Suppose_Max[4] = {min(i + 1, j + 1), min(i + 1, column -j), min(row - i, column - j), min(row - i, j + 1)};
if(ref > Suppose_Max[(k+1)%4]) return ref;
// 在转向的十字路口的ref值会计算两次，一次是未转向的，一次是转向的，需要返回的是最值
ref = max(ref, dfs(i, j, (k + 1)%4, false, 2 - target) + 1);
}
return ref;
};
// 遍历找1,然后四个方向递归找最值
for(int i = 0; i < row; ++i){
for(int j = 0; j < column; ++j){
if(grid[i][j] == 1){
// 优化1：若当前的ans大于理论最值，则无需再进行遍历了
for(int k = 0; k < 4; ++k){
// 走左上角的理论最值， 向上的最值 - (i + 1)
// 走右上角的理论最值， 向右的最值 - (column - j)
// 走右下方的理论最值， 向下的最值 - (row - i)
// 走左下方的理论最值， 向左的最值 - (j + 1)
int Suppose_Max[4] = {i + 1, column - j, row - i, j + 1};
if(ans > Suppose_Max[k]) continue;
ans = max(ans, dfs(i, j, k, true, 2) + 1);
}
}
}
}
return ans;
}
};单调栈
问题类型
- 存储 i 位置的左右两侧 第一个大于/小于 v[i] 的位置信息
- 在一维数组中找第一个满足某种条件的数
- 处理两个大值间的相关问题，例如：蓄水问题
例题
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
// 从前往后, 单调递减栈, 角度：栈中保存需要计算的答案
// vector<int> answer(n, 0);
// stack<int> st;
// for(int i = 0; i < n; ++i){
// while(!st.empty() && temperatures[st.top()] < temperatures[i]){
// answer[st.top()] = i - st.top();
// st.pop();
// }
// st.push(i);
// }
// 从后往前, 单调递减栈，角度：用栈中的数据更新答案
vector<int> answer(n, 0);
stack<int> st;
for(int i = n -1; i > -1; --i){
while(!st.empty() && temperatures[st.top()] <= temperatures[i]) st.pop();
if(!st.empty()) answer[i] = st.top() - i;
st.push(i);
}
return answer;
}
};练习
503. 下一个更大元素 II – 力扣（LeetCode）
1019. 链表中的下一个更大节点 – 力扣（LeetCode）
1504. 统计全 1 子矩形 – 力扣（LeetCode）
1793. 好子数组的最大分数 – 力扣（LeetCode）
1944. 队列中可以看到的人数 – 力扣（LeetCode）
举一反三
84 -> 85 题看似不相干的题型，但是经过以下处理转换为了一个题型：
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
转换为heights矩阵，矩阵的列存储的信息：连续的数字1的个数
| 1 | 0 | 1 | 0 | 0 |
| 2 | 0 | 2 | 1 | 1 |
| 3 | 1 | 3 | 2 | 2 |
| 4 | 0 | 0 | 3 | 0 |
每行都可以作为84题的case，取第三行为例
84题使用单调栈解决该问题，每行都有一个最值，取最大值即可
单调队列
枚举
部分算法题考察题目的本质，需要会将题型转化为对应的简单题，再通过枚举所有情况进行求解
情况枚举
例题
3197. 包含所有 1 的最小矩形面积 II – 力扣（LeetCode）
该题对应的简单题为
3195. 包含所有 1 的最小矩形面积 I – 力扣（LeetCode）
Q：如何转换为包含所有1的最小矩阵面积问题呢？
此时就需要考虑到所有可能的切法，共有以下切法（其中上方可以通过顺时针旋转90°（即：将矩阵转置就能得到）得到下方的情况， 因此只需解决上方情况，而下方的情况将矩阵转置带回到上发解决代码中）：
备注： 可以先写出暴力枚举的方法，之后通过DP或递归优化用时
二进制枚举
集合论与位运算的知识点
参考文章：集合与位运算 + bitset库
例题
2397. 被列覆盖的最多行数 – 力扣（LeetCode）
class Solution {
public:
/*
思考角度1：
考虑列向量（每一列都进行编码，用数组存取），并将column编码为二进制数， 考虑其全集的numselect个数的子集
若column的第i位为1，则表示清空为0，计算所有列向量编码的并集，返回 row - 并集的集合大小 即为覆盖的行数
*/
int maximumRows1(vector<vector<int>>& matrix, int numSelect) {
int ans = 0;
int row = matrix.size(), column = matrix[0].size();
vector<int> Col(column, 0);
for(int j = 0; j < column; ++j)
for(int i = 0; i < row; ++i)
Col[j] |= matrix[i][j] << (row - i - 1);
int x = (1 << numSelect) - 1;
// Gosper's Hack 快速查找全集中 个数为k 的子集
while(x < (1 << column)){
// 处理逻辑
int join = 0;
for(int i = 0; i < column; ++i){
if( !((x >> i) & 1) ){
join |= Col[i];
}
}
int lb = x & -x;
int left = lb + x;
int right = ((lb + x)^x)/lb >> 2;
x = left | right;
ans = max(ans,row - __builtin_popcount(join));
}
return ans;
}
/*
思考角度2：
将行向量编码，x编码中的元素为删除的列，若 row & x == row，说明row中存在的1都被x的1所在的列删除了
假设 - 某行row编码为 1001， 删除编码为 1010， 则 row & x = 1000， 没删除干净
1001， 则 row & x = 1001， 说明删除干净了（行被覆盖）
*/
int maximumRows(vector<vector<int>>& matrix, int numSelect){
int ans = 0;
int row = matrix.size(), column = matrix[0].size();
// 行向量编码
vector<int> RowCode(row);
for(int i = 0; i < row; ++i){
for(int j = 0; j < column; ++j){
RowCode[i] |= matrix[i][j] << j;
}
}
// 删除编码
int subset = (1 << numSelect) - 1;
// Gosper's Hack方法
while(subset < (1 << column)){
int CoverRow = 0;
for(const int& row: RowCode){
// 注意优先级
if((row & subset) == row) ++CoverRow;
}
ans = max(ans, CoverRow);
// 跳转到下一个符合条件的子集
int lb = subset & -subset;
int left = lb + subset;
int right = ((lb + subset) ^ subset) / lb >> 2;
subset = left | right;
}
return ans;
}
};递归
对于子问题和主问题求解过程一致的情况，可以通过递归的写法实现（例如： 切蛋糕问题）
备注：但递归算法问题存在诸多问题，例如：调用函数栈需要额外时间和空间；子问题可能有重合部分；调用过多的层数时导致栈溢出
滑动窗口
参考灵神：分享丨【算法题单】滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环
排序
- 利用排序简化枚举，比如某点是否在其余两点构成的长方形内
例题
解题思路如下：
points[i] – 坐标：
横坐标按从小到大排序（后续枚举无需考虑坐标间横坐标的情况）
纵坐标按从大到小排序（原因： 若按从小到大， 则处理包含在正方形内的元素极其困难）
固定左边界，枚举右边，保证右侧点的纵坐标严格单调递增且不大于左边界的纵坐标（y_max < yright <= y0）
代码如下：
class Solution { public: int numberOfPairs(vector<vector<int>>& points){ int n = points.size(); // sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b){ // if(a[0] == b[0]) // return a[1] > b[1]; // return a[0] < b[0]; // }); // ranges可快速实现上述内容 ranges::sort(points, {}, [](auto &p)->pair<int, int>{ return {p[0], -p[1]}; }); int ans = 0; // 现在只需要规定从左到右为递增且小于当前left的纵坐标即可 for(int left = 0; left < n - 1; ++left){ int y0 = points[left][1]; int ymax = INT_MIN; for(int right = left + 1; right < n; ++right){ if(points[right][1] > ymax && points[right][1] <= y0){ ++ans; ymax = points[right][1]; } } } return ans; } };
练习
2785. 将字符串中的元音字母排序 – 力扣（LeetCode）
获取元音字母（大写转小写，判断ch = ‘a’ | ‘e’ | ‘i’ | ‘o’ | ‘u’），从小到大排序放置于原先的元音字母位置上 （两次遍历）
判断优化： 注意到’a’~’z’ 和 ‘A’ ~ ‘Z’ 的 ASCII后五位的范围：00001 ~ 11010，因此只需要将ch & 31即可转为同一问题，{a, e, i, o, u} -> {1, 5, 9, 15, 21}, VOWEL_MASK = 2^1 + 2^5 + 2^9 + 2^15 + 2^21 = 2130466, 十六进制数 0x208222(容易记住)
Q：如何判断是否为元音呢？
VOWEL_MASK >> (ch & 31) & 1 == 1
上述仍然需要两次遍历
最终优化（灵神思路） – 一次遍历：计数排序， 用cnt记录元音的个数
代码如下：
const int VOWEL_MASK = 0x208222;
string sortVowels(string s) {
// 'u' - 'A' = 52
int cnt[53]{};
for(const char& ch:s){
// 元音，计数 + 1
if((VOWEL_MASK >> (ch & 31)) & 1){
++cnt[ch - 'A'];
}
}
char j = 'A';
for(char& ch: s){
// 若为辅音，则直接跳过一次循环
if(((VOWEL_MASK >> (ch & 31)) & 1) == 0)
continue;
while(cnt[j - 'A'] == 0){
j = j == 'Z'?'a': j + 1;
}
ch = j;
--cnt[j - 'A'];
}
return s;
}数学分析
此种类型题难在将问题转化为纯数学问题，难度系数十分大
例题
3495. 使数组元素都变为零的最少操作次数 – 力扣（LeetCode）
此题难度极大，需要将问题转换为纯数学问题（包括公式推导 & 充要条件 & 求和公式）
Q1：如何将本题转换为纯数学问题呢？关键点在哪？
此题本质：对于数组[1, n ] – 数据右移2位变为0的总操作数，如：q = [1, 2, 3, 4, 5] 就是 a = [1, 1, 1, 2, 2]
如何得来的呢？以5为例，二进制数为 101，第一次操作后：101 >> 2 = 1，第二次操作后：1 >> 2 = 0
因此5需要进行两次右移操作，数字对应二进制长度为 m，右移2位变为0的操作数为 ⌈m / 2⌉
如：5 – 101， m = 3，右移操作为 ⌈3 / 2⌉ = 2
那么对于 [1, n] 的数组，每次进行两次操作的最少操作次数为？ ⌈sum(a) / 2⌉
证明如下图：
Q2：转换后如何求解 sum(a)呢？
方法：
[1, n] n的二进制数的位数m
累加计算长度为i (1 <= i < m)的总操作数，其最小值为 2^(i – 1)， 最大值为 2^i – 1，总共有 2^(i-1)个长度为i的二进制数，其每个操作次数：⌈i/ 2⌉，长度为i的总操作次数为 ⌈i / 2⌉ * (2 ^(i – 1))
计算长度为m的总操作数，其最小值为 2^(m – 1)，最大值为n，总共有(n – 2^(m-1))个长度为m的二进制数，其每个操作次数为：⌈m/2⌉，长度为m的总操作次数为 ⌈m / 2⌉ * (n – 2^(m-1))
代码如下：
long long sum_operate_nums(int n){
// 统计总次数
long long sum = 0;
int m = bit_width((uint32_t) n);
for(int i = 1; i < m; ++i){
sum += 1LL * ((i + 1) >> 1) * (1 << (i - 1));
}
// 1 << m >> 1 而非 1 << (m - 1) 原因：防止 m = 0
sum += 1LL * (n - (1 << m >> 1) + 1) * ((m + 1) >> 1);
return sum;
}优化：
求和公式推导如下图：
代码如下：
long long sum_operate_nums_approve(int n){
int m = bit_width((uint32_t) n);
// k为小于m的最大偶数
int k = (m - 1) / 2 * 2;
// 求和公式
long long sum = 1LL * k * (1 << k >> 1) - ((1 << k) - 1) / 3 + 1LL * ((m + 1) >> 1) * (n + 1 - (1 << k));
return sum;
}对于[l,r]：⌈f(r) – f(l-1)⌉ >> 1
long long minOperations(vector<vector<int>>& queries) {
long long ans = 0;
int n = queries.size();
for(int i = 0; i < n; ++i)
// ans += (sum_operate_nums(queries[i][1]) - sum_operate_nums(queries[i][0] - 1) + 1) >> 1;
ans += (sum_operate_nums_approve(queries[i][1]) - sum_operate_nums_approve(queries[i][0] - 1) + 1) >> 1;
return ans;
}
感悟
若对算法题无头绪，可以先暴力求解试试，然后看看该方法中有无元素重复计算，若有则必可以优化
接着再去思考如何进行优化（如：DP） —— 难点