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(n2)，其中 n 是数组 grid 的行（列）数。
空间复杂度：O(n2)，其中 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] = i
iota(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，移除一个 size
void 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，移除一个结束位置 i
auto 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); // 添加/移除新长度
};
// 添加一个结束位置 i
auto add = [&](int i)
{
if (s.empty())
{
t.update(n, 1);
}
else
{
update(i, 1);
}
s.insert(i);
};
// 移除一个结束位置 i
auto 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 的长度。
标签：周赛,lc,int,题解,复杂度,vector,Leetcode,dp,size From： https://blog.csdn.net/ProgramNovice/article/details/141754447