928. 尽量减少恶意软件的传播 II(Hard)
给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。
请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：
输入：graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
输出：1
示例 3：
输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：1
提示：
n == graph.length
n == graph[i].length
2 <= n <= 300
graph[i][j] 是 0 或 1.
graph[i][j] == graph[j][i]
graph[i][i] == 1
1 <= initial.length < n
0 <= initial[i] <= n - 1
initial 中每个整数都不同
菜鸡抄的灵神题解：
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
unordered_set<int> st(initial.begin(), initial.end());
vector<int> vis(graph.size());
int node_id, size;
function<void(int)> dfs = [&](int x) {
vis[x] = true;
size++;
for (int y = 0; y < graph[x].size(); y++) {
if (graph[x][y] == 0) {
continue;
}
if (st.contains(y)) {
// 按照 924 题的状态机更新 node_id
// 注意避免重复统计，例如上图中的 0 有两条不同路径可以遇到 1
if (node_id != -2 && node_id != y) {
node_id = node_id == -1 ? y : -2;
}
} else if (!vis[y]) {
dfs(y);
}
}
};
unordered_map<int, int> cnt;
for (int i = 0; i < graph.size(); i++) {
if (vis[i] || st.contains(i)) {
continue;
}
node_id = -1;
size = 0;
dfs(i);
if (node_id >= 0) { // 只找到一个在 initial 中的节点
// 删除节点 node_id 可以让 size 个点不被感染
cnt[node_id] += size;
}
}
int max_cnt = 0;
int min_node_id = 0;
for (auto [node_id, c] : cnt) {
if (c > max_cnt || c == max_cnt && node_id < min_node_id) {
max_cnt = c;
min_node_id = node_id;
}
}
return cnt.empty() ? ranges::min(initial) : min_node_id;
}
};
题解：逆向思维（Python/Java/C++/C/Go/JS/Rust）
2007. 从双倍数组中还原原数组
一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。
给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。
示例 1：
输入：changed = [1,3,4,2,6,8]
输出：[1,3,4]
解释：一个可能的 original 数组为 [1,3,4] :
- 将 1 乘以 2 ，得到 1 * 2 = 2 。
- 将 3 乘以 2 ，得到 3 * 2 = 6 。
- 将 4 乘以 2 ，得到 4 * 2 = 8 。
其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。
示例 2：
输入：changed = [6,3,0,1]
输出：[]
解释：changed 不是一个双倍数组。
示例 3：
输入：changed = [1]
输出：[]
解释：changed 不是一个双倍数组。
提示：
1 <= changed.length <= 1e5
0 <= changed[i] <= 1e5
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
ranges::sort(changed);
vector<int> ans;
unordered_multiset<int> mark;
for (int x : changed) {
auto it = mark.find(x);
if (it == mark.end()) { // x 不是双倍后的元素
mark.insert(x * 2); // 标记一个双倍元素
ans.push_back(x);
} else { // x 是双倍后的元素
mark.erase(it); // 清除一个标记
}
}
// 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
return mark.empty() ? ans : vector<int>();
}
};
还是灵神题解orz
三种方法：从 O(nlogn) 到 O(n)
1883. 准时抵达会议现场的最小跳过休息次数(Hard)
给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。
当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。
例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。
然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。
例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。
返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。
示例 1：
输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。
示例 2：
输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。
示例 3：
输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。
提示：
n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 1e5
1 <= speed <= 1e6
1 <= hoursBefore <= 1e7
hard不会，看了题解：
class Solution {
public:
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
if (accumulate(dist.begin(), dist.end(), 0) >
(long long)speed * hoursBefore) {
return -1;
}
int n = dist.size();
vector<vector<int>> memo(n, vector<int>(n, -1)); // -1 表示没有计算过
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (j < 0) { // 递归边界
return 0;
}
auto& res = memo[i][j]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
res = (dfs(i, j - 1) + dist[j] + speed - 1) / speed * speed;
if (i)
res = min(res, dfs(i - 1, j - 1) + dist[j]);
return res;
};
for (int i = 0;; i++) {
if (dfs(i, n - 2) + dist[n - 1] <= (long long)speed * hoursBefore) {
return i;
}
}
}
};
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
回溯法：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> combination;
sort(candidates.begin(), candidates.end());
combinationSum(candidates, target, res, combination, 0);
return res;
}
private:
void combinationSum(vector<int>& candidates, int target,
vector<vector<int>>& res, vector<int>& combination,
int begin) {
if (!target) {
res.push_back(combination);
return;
}
for (int i = begin; i != candidates.size() && target >= candidates[i];
++i) {
combination.push_back(candidates[i]);
combinationSum(candidates, target - candidates[i], res, combination,
i);
combination.pop_back();
}
}
};
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
同上的方法，回溯法：
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
vector<int> combination;
combinationSum(k, n, res, combination, 1);
return res;
}
private:
void combinationSum(int k, int n, vector<vector<int>>& res,
vector<int>& combination, int begin) {
if (!n && !k) {
res.push_back(combination);
return;
}
for (int i = begin; i < 10 && n >= i && k > 0; ++i) {
combination.push_back(i);
combinationSum(k - 1, n - i, res, combination, i + 1);
combination.pop_back();
}
}
};
377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
背包基础，dp：
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target + 1);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
};
1052. 爱生气的书店老板
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
示例 1：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例 2：
输入：customers = [1], grumpy = [0], minutes = 1
输出：1
提示：
n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 104
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1
经典滑动窗口：
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int total = 0;
int n = customers.size();
for (int i = 0; i < n; i++) {
if (grumpy[i] == 0) {
total += customers[i];
}
}
int increase = 0;
for (int i = 0; i < minutes; i++) {
increase += customers[i] * grumpy[i];
}
int maxIncrease = increase;
for (int i = minutes; i < n; i++) {
increase = increase - customers[i - minutes] * grumpy[i - minutes] +
customers[i] * grumpy[i];
maxIncrease = max(maxIncrease, increase);
}
return total + maxIncrease;
}
};