Leetcode 第 409 场周赛题解

Leetcode 第 409 场周赛题解

题目1：3242. 设计相邻元素求和服务

思路

模拟，在原数组的周围补一圈 0。

代码

/** @lc app=leetcode.cn id=3242 lang=cpp** [3242] 设计相邻元素求和服务*/// @lc code=start
class NeighborSum
{
private:int g[12][12];int n;public:NeighborSum(vector<vector<int>> &grid) : n(grid.size()){for (int i = 0; i <= n + 1; i++)for (int j = 0; j <= n + 1; j++)g[i][j] = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)g[i][j] = grid[i - 1][j - 1];}int adjacentSum(int value){int ans = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (g[i][j] == value)ans = g[i][j - 1] + g[i + 1][j] + g[i - 1][j] + g[i][j + 1];return ans;}int diagonalSum(int value){int ans = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (g[i][j] == value)ans = g[i - 1][j - 1] + g[i - 1][j + 1] + g[i + 1][j - 1] + g[i + 1][j + 1];return ans;}
};/*** Your NeighborSum object will be instantiated and called as such:* NeighborSum* obj = new NeighborSum(grid);* int param_1 = obj->adjacentSum(value);* int param_2 = obj->diagonalSum(value);*/
// @lc code=end

复杂度分析

时间复杂度：O(n²)，其中 n 是数组 grid 的行（列）数。

空间复杂度：O(n²)，其中 n 是数组 grid 的行（列）数。

题目2：3243. 新增道路查询后的最短距离 I

思路

动态规划。

定义 dp[i] 为从 0 到 i 的最短路。

用 from[i] 记录额外添加的边的终点是 i，起点列表是 from[i]。

我们可以从 i−1 到 i，也可以从 from[i][j] 到 i，这些位置作为转移来源，用其 dp 值 +1 更新 dp[i] 的最小值。

初始值：dp[i]=i。

答案：dp[n−1]。

注意：设添加的边为 l→r，只有当 dp[l]+1<dp[r] 时才更新 DP。

代码

/** @lc app=leetcode.cn id=3243 lang=cpp** [3243] 新增道路查询后的最短距离 I*/// @lc code=start// 动态规划class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){vector<int> dp(n);vector<vector<int>> from(n);// 初始化：dp[i] = iiota(dp.begin(), dp.end(), 0);vector<int> ans;// 状态转移for (vector<int> &q : queries){int l = q[0], r = q[1];from[r].push_back(l);if (dp[l] + 1 < dp[r]){dp[r] = dp[l] + 1;// 更新后面的最短路for (int i = r + 1; i < n; i++){dp[i] = min(dp[i], dp[i - 1] + 1);for (int j : from[i]){// 存在一条 j->i 的路径dp[i] = min(dp[i], dp[j] + 1);}}}ans.push_back(dp[n-1]);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(q(n+q))，其中 q 是数组 queries 的长度。

空间复杂度：O(n+q)，其中 q 是数组 queries 的长度。

题目3：3244. 新增道路查询后的最短距离 II

思路

贪心。

由于题目保证添加的边（捷径）不会交叉，从贪心的角度看，遇到捷径就走捷径是最优的。所有被跳过的城市都不可能再出现在最短路了，直接删除掉。

代码

/** @lc app=leetcode.cn id=3244 lang=cpp** [3244] 新增道路查询后的最短距离 II*/// @lc code=start
class Solution
{
public:vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries){set<int> s; // 存储所有城市的编号// 将每个城市加入到 set 中for (int i = 0; i < n; i++)s.insert(i);vector<int> ans;for (vector<int> &q : queries){// [l, r) 之间的所有城市不可能在最短路里auto l = s.upper_bound(q[0]), r = s.lower_bound(q[1]);s.erase(l, r);// 剩余节点数减 1 即为当前的最短路径长度ans.push_back(s.size() - 1);}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O((n+q)logn)，其中 q 是数组 queries 的长度。

空间复杂度：O(n)。

题目4：3245. 交替组 III

思路

树状数组。

题解：https://leetcode.cn/problems/alternating-groups-iii/solutions/2869147/cong-yi-dao-nan-yi-bu-bu-tui-dao-pythonj-jho9/

代码

/** @lc app=leetcode.cn id=3245 lang=cpp** [3245] 交替组 III*/// @lc code=start
class FenwickTree
{vector<array<int, 2>> tree;public:FenwickTree(int n) : tree(n + 1) {}// op=1，添加一个 size// op=-1，移除一个 sizevoid update(int size, int op){for (int i = tree.size() - size; i < tree.size(); i += i & -i){tree[i][0] += op;tree[i][1] += op * size;}}// 返回 >= size 的元素个数，元素和pair<int, int> query(int size){int cnt = 0, sum = 0;for (int i = tree.size() - size; i > 0; i &= i - 1){cnt += tree[i][0];sum += tree[i][1];}return {cnt, sum};}
};class Solution
{
public:vector<int> numberOfAlternatingGroups(vector<int> &a, vector<vector<int>> &queries){int n = a.size();set<int> s;FenwickTree t(n);// op=1，添加一个结束位置 i// op=-1，移除一个结束位置 iauto update = [&](int i, int op){auto it = s.lower_bound(i);int pre = it == s.begin() ? *s.rbegin() : *prev(it);int nxt = it == s.end() ? *s.begin() : *it;t.update((nxt - pre + n - 1) % n + 1, -op); // 移除/添加旧长度t.update((i - pre + n) % n, op);t.update((nxt - i + n) % n, op); // 添加/移除新长度};// 添加一个结束位置 iauto add = [&](int i){if (s.empty()){t.update(n, 1);}else{update(i, 1);}s.insert(i);};// 移除一个结束位置 iauto del = [&](int i){s.erase(i);if (s.empty()){t.update(n, -1);}else{update(i, -1);}};for (int i = 0; i < n; i++){if (a[i] == a[(i + 1) % n]){add(i); // i 是一个结束位置}}vector<int> ans;for (auto &q : queries){if (q[0] == 1){if (s.empty()){ans.push_back(n); // 每个长为 size 的子数组都符合要求}else{auto [cnt, sum] = t.query(q[1]);ans.push_back(sum - cnt * (q[1] - 1));}}else{int i = q[1];if (a[i] == q[2]){ // 无影响continue;}int pre = (i - 1 + n) % n, nxt = (i + 1) % n;// 修改前，先去掉结束位置if (a[pre] == a[i]){del(pre);}if (a[i] == a[nxt]){del(i);}a[i] ^= 1;// 修改后，添加新的结束位置if (a[pre] == a[i]){add(pre);}if (a[i] == a[nxt]){add(i);}}}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O((n+q)logn)，其中 n 是数组 colors 的长度，q 是数组 queries 的长度。

空间复杂度：O(n)，其中 n 是数组 colors 的长度。