【5】417. 太平洋大西洋水流问题
思路
DFS/BFS，反向搜索，判断每个新位置是否能流到现在的位置。用矩阵记录是否能到达，使用位运算进行优化（1代表太平洋，2代表大西洋）。
代码
DFS
static vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
class Solution {
public:
void dfs(int x, int y, int v, vector<vector<int>> &heights, vector<vector<int>> &waves){
if(waves[x][y] & v) return;
waves[x][y] |= v;
int m = waves.size();
int n = waves[0].size();
for(const auto &d : dirs){
int nx = x + d[0];
int ny = y + d[1];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && heights[nx][ny] >= heights[x][y])
dfs(nx, ny, v, heights, waves);
}
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
const int M = heights.size();
const int N = heights[0].size();
// 流动记录矩阵
vector<vector<int>> waves(M, vector<int>(N));
for(int i = 0; i < M; i++){
dfs(i, 0, 1, heights, waves);// 左边一列 太平洋
dfs(i, N - 1, 2, heights, waves);// 右边一列 大西洋
}
for(int j = 0; j < N; j++){
dfs(0, j, 1, heights, waves);// 上面一列 太平洋
dfs(M - 1, j, 2, heights, waves);// 下面一列 大西洋
}
vector<vector<int>> ans;
for(int i = 0; i < M; i++)
for(int j = 0; j < N ; j++)
if(waves[i][j] == 3)
ans.push_back({i, j});
return ans;
}
};// 简洁写法
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
const int m = heights.size();
const int n = heights[0].size();
vector<vector<int>> s(m, vector<int>(n));
vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
auto dfs = [&](this auto&& dfs, int x, int y, int v) {
if (s[x][y] & v) return;
s[x][y] |= v;
for (const auto& d : dirs) {
int nx = x + d[0];
int ny = y + d[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && heights[x][y] <= heights[nx][ny]) {
dfs(nx, ny, v);
}
}
};
for (int i = 0; i < m; ++i) {
dfs(i, 0, 1);
dfs(i, n - 1, 2);
}
for (int j = 0; j < n; ++j) {
dfs(0, j, 1);
dfs(m - 1, j, 2);
}
vector<vector<int>> ans;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i][j] == 3) ans.push_back({i, j});
}
}
return ans;
}
};BFS
懒得写了
【6】778. 水位上升的泳池中游泳
思路
注意：题目上游泳不需要时间，即可以瞬间移动（神人）。所以，在只要有一条能从0, 0通到N – 1, N – 1的路径存在的情况下，使等待时间t变得最小。
1.二分查找 + 遍历
二分查找相关题目：单调性分析 -> 区间搜索范围 -> 区间搜索方法
单调性分析：题目中提供等待的时间t，而t又跟可游泳的网格分布有关。t越大，可游泳的网格分布越大，满足条件的可能性越大；t越小，可游泳的网格分布越小，满足条件的可能性越小。
区间搜索范围：[0, N * N – 1]
区间搜索方法：当小于等于该数值时，如果路径存在，那么值一定小于等于该数值；如果路径不存在，那么值一定大于该数值。
2.并查集
模拟下雨，
3.Dijkstra
应用前提：1.正权 2.单源最短路径
代码
1.二分查找 + 遍历
static vector<vector<int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
class Solution {
public:
bool dfs(vector<vector<int>> &grid, int x, int y, vector<vector<bool>>& visited, int th){
if(x == grid.size() - 1 && y == grid.size() - 1) return true;
for(const auto &d : dirs){
int nx = x + d[0];
int ny = y + d[1];
if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && visited[nx][ny] == false && grid[nx][ny] <= th){
visited[nx][ny] = true;
if(dfs(grid, nx, ny, visited, th)) return true;
}
}
return false;
}
int swimInWater(vector<vector<int>>& grid) {
const int N = grid.size();
int left = 0, right = N * N - 1;
while(left < right){
int mid = (left + right) >> 1;
vector<vector<bool>>visited(N,vector<bool>(N,false));
if(grid[0][0] <= mid&&dfs(grid, 0, 0, visited, mid)) right = mid;
else{
left = mid + 1;
}
}
return left;
}
};【7】1488. 避免洪水泛滥
思路
下雨不可抽，不下雨可抽。导致洪水泛滥的原因是：前面湖泊已满，后面还要下雨。那么，我们是否可以看未来哪个湖泊最可能先引发洪水泛滥，进而考虑我们抽水的湖泊呢？
换句话说就是：延迟抽水，等到后面要发生洪水的时候，再决定之前抽水的湖泊
1.贪心 + 二分查找
使用有序集合st来存晴天的下标。在哈希表mp中，first存有水的湖泊，second存下标。有序集合 st 的排序方式是按照晴天日子的顺序排列的，这就确保了我们总是在最早的晴天日子中进行抽干操作，以最大程度地避免洪水的发生。
对于最后剩余的晴天，我们可以将它们用于抽干任意一个湖泊，为了方便，我们令其为 1。初始化时，我们将所有晴天的默认操作设为抽干湖泊1，这是一种“安全”的占位符。因为即使湖泊1是空的，抽干一个空的湖泊也不会产生负面影响（题目描述中抽干空湖泊是无事发生的）。
- 若 rains[i]=0，则将 i 加入有序集合 st。
- 若 rains[i]>0，表示第 rains[i] 湖泊将下雨，令 ans[i]=−1 表示这一天的湖泊不可抽干：
- 若第 rains[i] 是第一次下雨，则此时不会发生洪水。
- 否则我们需要在有序集合 st 中找到大于等于该湖泊上一次下雨天数的最小索引 idx（可以用二分查找实现），如果 idx 不存在（即没有晴天可以用于抽干），此时不能避免洪水的发生，按照题目要求返回一个空数组。否则我们令 ans[idx]=rains[i]，并在 st 中删除 idx，表示我们会在第 idx 天抽干 rains[i] 湖泊的水来避免第 i 天洪水的发生。
代码
1.贪心 + 二分查找
class Solution {
public:
vector<int> avoidFlood(vector<int>& rains) {
vector<int> ans(rains.size(), 1);
set<int> st;
unordered_map<int, int> mp;
for (int i = 0; i < rains.size(); ++i) {
if (rains[i] == 0) {
st.insert(i);
} else {
ans[i] = -1;
if (mp.count(rains[i])) {
auto it = st.lower_bound(mp[rains[i]]);
if (it == st.end()) {
return {};
}
ans[*it] = rains[i];
st.erase(it);
}
mp[rains[i]] = i;
}
}
return ans;
}
};【8】2300. 咒语和药水的成功对数
思路
1.二分查找
公式：spells[i] * potions[j] >= success
spells[i]越大或potions[j]越大，成功概率越高。因为我们要咒语组合成功的药水数目，所以我们使用spells[i]来遍历数组。
逆推出：potions[j] >= success / spells[i]
可见，具有单调性，可以使用二分查找解决。
代码
1.二分查找
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
vector<int> res;
for(auto & i : spells){
// 向上取整 ceil(a/b) = (a + b - 1) / b
// 不小于 success / spells[i] 的最小整数，所以需要-1
long long t = (success + i - 1)/ i - 1;
// 取位置，算剩下potions的数量
res.push_back(potions.size() - (upper_bound(potions.begin(), potions.end(), t) - potions.begin()));
}
return res;
}
};【9】3494. 酿造药水需要的最少总时间
思路
题目要求：每个药水都必须经过每个巫师处理，每个巫师同时间只能够处理一瓶药水，并且每个药水开始酿造后就无法停下。
注意：题目中每个药水要 必须 依次通过 所有 巫师处理
1.动态规划
从时刻0开始酿造药水，可以计算出后面的巫师结束酿造的时间。后面的巫师开始酿造的时间取决于前面的巫师结束酿造的时间，具有连续性，不能确定下来。所以，我们假设允许第 j 瓶药水的酿造过程不连续，前 j – 1 瓶仍连续。
公式推导：
设第 i 位巫师处理完第 j 瓶药水的时间是times[i][j]，那么有：
times[i][j]=max(times[i−1][j],times[i][j−1])+skill[i]×mana[j]
由于times[i−1][j]与旧纪录有关，times[i][j−1]与现记录有关，所以我们可以把times压缩成一维，记录旧值与新值。（一位数组滚动优化）
在经过每瓶药水递推后，由于之前假设允许第 j 瓶药水的酿造过程不连续产生了间隔，所以要反向遍历更新。
代码
1.动态规划
class Solution {
public:
using LL = long long;
long long minTime(vector<int>& skill, vector<int>& mana) {
int n = skill.size(), m = mana.size();
vector<LL> times(n);//降维
for(int j = 0; j < m; j++){
LL cur = 0;
for(int i = 0; i < n; i++)
cur = max(cur, times[i]) + skill[i] * mana[j];
times[n - 1] = cur;
for(int i = n - 2; i >= 0; i--)
times[i] = times[i + 1] - skill[i + 1] * mana[j];
}
return times[n - 1];
}
};【10】3147. 从魔法师身上吸取的最大能量
思路
1.逆序遍历
从前往后看，数组是这样的：
[i]
[i, i + k]
[i, i + k, i + 2k]
[i, i + k, i + 2k, i + 3k]
[i, i + k, i + 2k, i + 3k, i + 4k]
从后往前看，
[i]
[i, i – k]
[i, i – k, i – 2k]
[i, i – k, i – 2k, i – 3k]
[i, i – k, i – 2k, i – 3k, i – 4k]
在这些个路径中，发现都是差为|k|的等差数列，即周期为k。于是，就i从0开始遍历到k-1。从题目中可以知道，最后要到达末尾，而起点是未知的，所以从末尾到起点逆着推比较好（就i从n-k开始遍历到n），这样也避免了一个问题（当energy数组中出现负数时，避免写多余代码修正数字）。
代码
1.逆序遍历
class Solution {
public:
int maximumEnergy(vector<int>& energy, int k) {
int n = energy.size(), ans = INT_MIN;
//采用逆序是为了避免修正数字
for(int i = n - k; i < n; i++){
int sum = 0;
for(int j = i;j >= 0; j -= k){
sum += energy[j];
ans = max(ans, sum);
}
}
return ans;
}
};【11】3186. 施咒的最大总伤害
思路
1.动态规划
使用一个咒语power[i]后，就不能使用伤害绝对值相差1-2的咒语。所以，咒语的选择与power的顺序无关，与咒语伤害值有关。于是，可以先把一样伤害的咒语存到一起去。
设伤害为poweri 的咒语数量为counti 。令f(i)表示从 0 到第 i 种咒语中选择，并且最后选择第 i 种咒语的最大总伤害。公式如下：
f(i) = f(j)max(powerj < poweri – 2) + poweri * counti
按伤害递增顺序遍历咒语，用单调指针维护f(j)max ，即用于转移的最大值，最后答案为f中的最大值。
代码
1.动态规划
class Solution {
public:
long long maximumTotalDamage(vector<int>& power) {
map<int, int> mp;
for(int i: power){
mp[i]++;
}
vector<pair<int, int>> p = {{-1e9, 0}};
for(auto &i: mp){
p.push_back(i);
}
int n = p.size();
vector<long long> dp(n, 0);
long long mx = 0;
for(int i = 1, j = 1; i < n; i++){
while(j < i && p[i].first - 2 > p[j].first){
mx = max(mx, dp[j]);
j++;
}
dp[i] = mx + 1LL * p[i].first * p[i].second;
}
long long ans = 0;
for(int i = 0; i < n; i++)
ans = max(ans, dp[i]);
return ans;
}
};