解题记录
12 月总结
本月有价值的题目：
2023-12-01
2661 找出叠涂元素
很简单的题目，就是题目描述的不清楚
2023-12-02
1094 拼车
简单的模拟题
2023-12-03
1423 可获得的最大点数
比较简单，维护两个前缀和即可
需要注意边界处理
2023-12-04
1038 从二叉搜索树到更大和树
二叉树后序遍历，没啥难度，不做记录
2023-12-05
2477 到达首都的最少油耗
DFS+模拟，不做记录
2023-12-06
2646 最小化旅行的价格总和
一棵树，每个节点有一个价格
一些旅行路径，路径的价格是路径上所有节点的价格之和
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半
返回执行所有旅行的最小价格总和
节点数 1 <= n <= 50
对于「多条路径」的处理比较简单，记录一个新的 Price，每个节点的 Price = 经过的路径数 * 该节点原本的价格
关键问题是如何选择价格减半的节点，以下简称为「染色」，被染色的节点价格减半
最开始的想法是暴搜，但是枚举每种可能的染色方式比较困难。
考虑动态规划
维护两个数组：
subtrees0[i]：以 i 为根节点的子树，的最小价格，i 不染色subtrees0[i]：以 i 为根节点的子树，的最小价格，i 染色
那么状态转移方程为：
核心动态规划代码：
1
2
3
4
5
6
7
8
9
10
void DP(int pre, int node){
for(auto& next: MatrixEdges[node]){
if(next == pre) continue;
DP(node, next);
subtrees0[node] += min(subtrees0[next], subtrees1[next]);
subtrees1[node] += subtrees0[next];
}
subtrees0[node] += NewPrice[node];
subtrees1[node] += NewPrice[node] / 2;
}
2023-12-07
1466 重新规划路线
DFS，不做记录
2023-12-08
一条单向直路线，一共 n 个地点，编号 1~n
驾驶出租车，乘客信息用一个下标从 0 开始的二维数组
rides表示，其中rides[i] = [starti, endi, tipi]表示第i位乘客需要从地点starti前往endi，愿意支付tipi元的小费每一位 你选择接单的乘客
i，你可以 盈利endi - starti + tipi元。你同时 最多 只能接一个订单求最大盈利
动态规划，DP[i] 表示到达 i，最大盈利是多少
状态转移方程为：
DP[i] = max(DP[i-1], DP[start_k] + end_k - start_k + tip_k), for all k that end_k == i
这里的 DP[i-1] 是一处细节
核心代码：
1
2
3
4
5
6
7
8
9
10
11
vector<long long> dp(n + 1, 0);
vector<vector<pair<int, int>>> v(n + 1);
for(auto& ride : rides){
v[ride[1]].push_back({ride[0], ride[1] - ride[0] + ride[2]});
}
for(int i = 1; i <= n; i++){
dp[i] = dp[i - 1];
for(auto& p : v[i]){
dp[i] = max(dp[i], dp[p.first] + p.second);
}
}
另外一开始想着按照 rides 递归，对其从小到大排序，后来发现行不通，但是排序的代码值得记录一下：
1
2
3
sort(rides.begin(), rides.end(), [](const vector<int>& a, const vector<int>& b){
return a[1] < b[1];
});
2023-12-09
2048 下一个更大的数值平衡数
比较简单，不做记录
2023-12-10
70 爬楼梯
经典的递推入门题，不做记录
2023-12-11
1631 最小体力消耗路径
二维地图，给出每个点的高度
路径的体力值，等于路径上相邻点的高度差绝对值的最大值
求从左上角走到右下角的最小体力值
1 <= rows, columns <= 100
暴搜应该会超时（没尝试）
使用二分，二分体力值。
看了下题解，除了二分，还可以抽象为最小生成树问题，感觉还挺巧妙的
代码就比较简单了，不做记录
2023-12-12
2454 下一个更大元素 IV
给一个一维整数数组
找到每个数字后面的，第二个比他大的数字
1 <= nums.length <= 10^5
使用两个单调栈
首先考虑找每个数字后面的第一个比他大的数字，那么维护一个单调栈即可，单调不增，对于新遍历到的一个数字，如果它比当前栈顶数字大，那么它就是栈顶数字的后面第一个比它大的数字，不大于栈顶数字的话，入栈。
现在问题变成找第二个比它大的数字。
那么原本的单调栈仍然维护，当找到第一个比栈顶大的数字时，栈顶弹栈，入第二个单调栈。第二个单调栈如果遇到比它大的数字，那么该数字就是第二个比它大的数字。
为了维护第二个单调栈，需要做两个额外处理：
- 新遍历到的数字，应该先与第二个单调栈比较
- 从第一个单调栈弹出的元素，可能不止一个，所以再用一个栈中转，维护单减顺序。
时间复杂度 O(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
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1);
stack<int> stack1; // 初始单调栈
stack<int> stack2; // 第二个单调栈
stack<int> stack3; // 用于中转数据
for(int i = 0; i < n; i++){
while(!stack2.empty() && nums[stack2.top()] < nums[i]){
ans[stack2.top()] = nums[i];
stack2.pop();
}
while(!stack1.empty() && nums[stack1.top()] < nums[i]){
stack3.push(stack1.top());
stack1.pop();
}
while(!stack3.empty()){
stack2.push(stack3.top());
stack3.pop();
}
stack1.push(i);
}
return ans;
}
};
2023-12-13
2697 字典序最小回文串
比较简单，不做记录
2023-12-14
2132 用邮票贴满网格图
给一个二维矩阵，每个格子为 1 或 0，为 1 表示被占据
给一个邮票尺寸，用该邮票覆盖矩阵
邮票不可旋转，邮票可无限次使用，邮票可重叠，邮票必须完全在矩阵内，不可覆盖为 1 的格子
问是否可以覆盖所有的 0 格子
1 <= m, n <= 10^51 <= m * n <= 2 * 10^5
二位前缀和+二维差分
因为邮票可重叠，且不考虑「使用最少的邮票」进行覆盖，那么对于每个 0 格子，考虑以它作为左上角覆盖一张邮票。需要考虑两个问题：
- 如何判断可以覆盖？朴素想法是，遍历以它为左上角的邮票大小，但是这使得常数有邮票面积那么大，会超时。使用二位前缀和。只要此时邮票范围的和为 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
28
29
30
31
32
33
34
class Solution {
public:
bool possibleToStamp(vector<vector<int>>& grid, int stampHeight, int stampWidth) {
vector<vector<int>> prefixSum(grid.size() + 2, vector<int>(grid[0].size() + 2, 0));
vector<vector<int>> prefixDiff(grid.size() + 2, vector<int>(grid[0].size() + 2, 0));
for(int i = 1; i <= grid.size(); i++) {
for(int j = 1; j <= grid[0].size(); j++) {
prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + grid[i - 1][j - 1];
}
}
for(int i = 1; i + stampHeight - 1 <= grid.size(); i++) {
for(int j = 1; j + stampWidth - 1 <= grid[0].size(); j++) {
int x = i + stampHeight - 1;
int y = j + stampWidth - 1;
int sum = prefixSum[x][y] - prefixSum[i - 1][y] - prefixSum[x][j - 1] + prefixSum[i - 1][j - 1];
if(sum == 0){ // 中间的任意格子都为 0
prefixDiff[i][j]++;
prefixDiff[i][y + 1]--;
prefixDiff[x + 1][j]--;
prefixDiff[x + 1][y + 1]++;
}
}
}
for(int i = 1; i <= grid.size(); i++) {
for(int j = 1; j <= grid[0].size(); j++) {
prefixDiff[i][j] += prefixDiff[i - 1][j] + prefixDiff[i][j - 1] - prefixDiff[i - 1][j - 1];
if(prefixDiff[i][j] == 0 && grid[i - 1][j - 1] == 0) {
return false;
}
}
}
return true;
}
};
2023-12-15
2415 反转二叉树的奇数层
BFS，比较简单，不做记录
2023-12-16
2276 统计区间中的整数数目
初始为空区间，两种操作：
void add(int left, int right)添加区间[left, right]到区间集合之中。
int count()返回出现在区间集合中的整数个数1 <= left <= right <= 10^9- 最多调用
add和count方法 总计10^5次
这个题目和 11 月做过的 Range 模块 十分类似。
使用平衡二叉搜索树，STL 中的 set，以 left 为 key，right 为 value，整棵树按照 left 排序。
对于 conut 操作，如果每调用一次就遍历一遍二叉树，实测会超时。根据题目特点，可以维护一个值 ans，表示整数个数，随着 add 操作，更新 ans.
虽然 11 月敲过一遍，但现在仍然不熟悉，所以再附一遍完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class CountIntervals {
public:
CountIntervals() {}
void add(int left, int right) {
auto it = ranges.lower_bound({left, right});
if(it != ranges.begin() && (--it)->second < left) it++;
while(it != ranges.end() && it->first <= right){
left = min(left, it->first);
right = max(right, it->second);
ans -= it->second - it->first + 1;
it = ranges.erase(it);
}
ranges.insert({left, right});
ans += right - left + 1;
}
int count() {
return ans;
}
private:
set<pair<int, int>> ranges;
int ans = 0;
};
2023-12-17
746 使用最小花费爬楼梯
比较简单的动态规划，不做记录
2023-12-18
162 寻找峰值
就是在一维数组里找峰值，任意一个都可以。
朴素的遍历就可以解决，时间复杂度是 O(n)，不过想尝试一下二分，时间复杂度为 O(logn)
比想象的复杂一些，主要是边界处理，可能会访问数组越界。
2023-12-19
1901 寻找峰值 II
比较简单，不做记录