lc3593
自底向上dfs
max dfs
cnt not need change子树
class Solution {
public:
int minIncrease(int n, vector<vector<int>>& edges, vector<int>& cost)
{
vector<vector<int>> g(n);
for (auto& e : edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x);
}
g[0].push_back(-1);
int ans = 0;
auto dfs = [&](this auto&& dfs, int x, int fa) -> long long {
long long max_s = 0;
int cnt = 0;
for (int y : g[x]) {
if (y == fa)
continue;
long long mx = dfs(y, x);
if (mx > max_s) {
max_s = mx;
cnt = 1;
}else if (mx == max_s)
cnt++;
}
ans += g[x].size() - 1 - cnt;//子树-fa-not need change
return max_s + cost[x];
};
dfs(0, -1);
return ans;
}
};
lc1519
vector<int> dfs
class Solution {
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
vector<int> res(n, 0);
vector<vector<int>> g(n);
for(auto& e : edges) {
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
auto dfs = [&](this auto&& dfs,int u, int p)-> vector<int>
{
vector<int> cnt(26, 0);//cur
cnt[labels[u] - 'a']++;
for(int v : g[u]) {
if(v == p) continue;
vector<int> c = dfs(v, u);
for(int i = 0; i < 26; i++)
cnt[i] += c[i];
//拿到的每个v 都加给cur
}
res[u] = cnt[labels[u] - 'a'];
//统计完v后 存入ret
return cnt;
};
dfs(0, -1);// cur,fa
return res;
}
};
lc3254
统计连续上升的元素长度，用一次遍历判断每个长度为k的子数组是否连续上升 借助cnt变量
满足则记录末尾元素为能量值，否则保持-1
class Solution {
public:
vector<int> resultsArray(vector<int>& nums, int k) {
vector<int> ans(nums.size() - k + 1, -1);
int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
cnt = i == 0 || nums[i] == nums[i - 1] + 1 ? cnt + 1 : 1;
if (cnt >= k)
ans[i - k + 1] = nums[i];
}
return ans;
}
};
lc957
模拟+周期+hash
模拟每天牢房状态变化+检测循环周期
高效计算出 n 天后的牢房状态，避免了大数 n 的重复模拟
class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int n) {
unordered_map<int, vector<int>> map; //key：第i天 value：cells状态
map.insert({0, cells});
for (int i = 1; i <= n; i++) {
if (i == 1) {
cells[0] = 0;
cells[7] = 0;
}
for (int j = 1; j < 7; j++) {
if (map[i - 1][j - 1] == 0 && map[i - 1][j + 1] == 0) cells[j] = 1;
else if (map[i - 1][j - 1] == 1 && map[i - 1][j + 1] == 1) cells[j] = 1;
else cells[j] = 0;
}
map.insert({i, cells});
bool flag = true;// 判循环
for (int j = 0; j < 8; j++)
if (cells[j] != map[1][j]) flag = false;
if (i > 1 && flag) {
if (n % (i - 1) == 0) return map[i - 1]; //能整除则返回上一天的状态（余数为0）
else return map[n % (i - 1)];
//不能整除时返回第 n % (i - 1) 的状态
}
}
return cells;
//没出现循环直接返回模拟的结果
}
};
