437贪心

lc3459

memo与方向枚举，在二维网格中查找以1开头、1和2交替出现的最长对角线（含转向）路径长度

1. 确定参数与返回值：DFS参数包含当前位置 (i,j) 、移动方向 k 、转向权限 can_turn 、目标值 target ，返回以当前状态出发的最长交替路径长度。

2. 设置终止条件：计算移动后新位置，若越界或网格值不等于 target ，则路径终止，返回0。

3. 处理当前层逻辑：判断是否可读取记忆化缓存，若 can_turn 为 false 且缓存存在，直接返回缓存值避免重复计算。

4. 递归遍历下一层：先沿原方向递归计算路径长度并加1，若有转向权限，切换方向后再次递归，取两次递归结果的最大值。

5. 记忆化优化：当 can_turn 为 false 时，将当前递归计算的路径长度存入 memo[i][j][k] ，供后续相同状态直接调用

class Solution {
static constexpr int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};

public:
int lenOfVDiagonal(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector memo(m, vector<array<int, 4>>(n));

auto dfs = [&](this auto&& dfs, int i, int j, int k, bool can_turn, int target) -> int {
i += DIRS[k][0];
j += DIRS[k][1];
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target) {
return 0;
}
// 只在 can_turn=false 时读取和写入 memo
if (!can_turn && memo[i][j][k]) {
return memo[i][j][k];
}
int res = dfs(i, j, k, can_turn, 2 - target) + 1;
if (!can_turn) {
return memo[i][j][k] = res;
}
int maxs[4] = {m - i, j + 1, i + 1, n - j}; // 理论最大值（走到底）
k = (k + 1) % 4;
// 优化二：如果理论最大值没有超过 res，那么不递归
if (min(maxs[k], maxs[(k + 3) % 4]) > res) {
res = max(res, dfs(i, j, k, false, 2 - target) + 1);
}
return res;
};

int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) {
continue;
}
int maxs[4] = {m - i, j + 1, i + 1, n - j}; // 理论最大值（走到底）
for (int k = 0; k < 4; k++) { // 枚举起始方向
// 优化一：如果理论最大值没有超过 ans，那么不递归
if (maxs[k] > ans) {
ans = max(ans, dfs(i, j, k, true, 2) + 1);
}
}
}
}
return ans;
}
};

lc3457

贪心

要被舍弃的数尽可能的小

class Solution {

public:

long long maxWeight(vector<int>& pizzas) {

ranges::sort(pizzas, greater<int>());

int days = pizzas.size() / 4;

int odd = (days + 1) / 2;

long long ans = 0;

for (int i = 0; i < odd; i++)

ans += pizzas[i];

for (int i = 0; i < days / 2; i++) {

ans += pizzas[odd + i * 2 + 1];

}

return ans;

}

};

lc3456

class Solution {
public:
bool hasSpecialSubstring(string s, int k) {
int n = s.size();
int cnt = 0;
for (int i = 0; i < n; i++) {
cnt++;
if (i == n - 1 ||s[i] != s[i + 1]){
if (cnt == k)
return true;
cnt = 0;// try update后置0
}
}
return false;
}
};