Leetcode - 周赛409
目录
一，3242. 设计相邻元素求和服务
二，3243. 新增道路查询后的最短距离 I
三，3244. 新增道路查询后的最短距离 II
四，3245. 交替组 III
一，3242. 设计相邻元素求和服务
本题纯模拟，代码如下：
class neighborSum {int[][] t;int n, m;public neighborSum(int[][] grid) {n = grid.length;m = grid[0].length;t = grid;}public int adjacentSum(int value) {int x=-1, y=-1;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(t[i][j] == value){x = i;y = j;break;}}if(x!=-1 && y!=-1) break;}int ans = 0;if(x>0) ans += t[x-1][y];if(y>0) ans += t[x][y-1];if(x+1<n) ans += t[x+1][y];if(y+1<m) ans += t[x][y+1];return ans;}public int diagonalSum(int value) {int x=-1, y=-1;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(t[i][j] == value){x = i;y = j;break;}}if(x!=-1 && y!=-1) break;}int ans = 0;if(x>0 && y>0) ans += t[x-1][y-1];if(x>0 && y+1<m) ans += t[x-1][y+1];if(x+1<n && y>0) ans += t[x+1][y-1];if(x+1<n && y+1<m) ans+=t[x+1][y+1];return ans;}
}二，3243. 新增道路查询后的最短距离 I
本题每次查询可以使用 bfs 计算出从 0 到 n-1 的最短路径长度，代码如下：
class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {int t = queries.length;int[] ans = new int[t];List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, e->new ArrayList<>());for(int i=0; i<n-1; i++){g[i].add(i+1);}int k = 0;for(int[] q : queries){g[q[0]].add(q[1]);Queue<Integer> que = new LinkedList<>();boolean[] vis = new boolean[n];vis[0] = true;que.add(0);int cnt = 0;while(!que.isEmpty() && ans[k] == 0){int size = que.size();while(size-- > 0){int poll = que.poll();for(int x : g[poll]){if(!vis[x]){vis[x] = true;que.add(x);if(x == n-1){ans[k] = cnt+1;}}}}cnt++;}k++;}return ans;}
}三，3244. 新增道路查询后的最短距离 II
本题和上一题不同，它多给了一个条件不存在两个查询满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]，也就是说它不会出现两个集合相交的情况。
方法一：
- 可以使用一个有序集合存储每个点，对于每一个查询，我们直接删除在（queries[i][0]，queries[i][1]）范围内的点，这时的答案就是集合的大小 - 1，代码如下：
class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {TreeSet<Integer> set = new TreeSet<>();for(int i=0; i<n; i++) set.add(i);int[] ans = new int[queries.length];for(int i=0; i<queries.length; i++){int l = queries[i][0], r = queries[i][1];找到>=l+1的最小的值,使用红黑树实现，时间复杂度O(logn)Integer ceiling = set.ceiling(l+1);//删除(l,r)之间的点while(ceiling != null && ceiling < r){set.remove(ceiling);ceiling = set.ceiling(l+1);}ans[i] = set.size()-1;}return ans;} }方法二：并查集
- 可以把 i -> i + 1 的这段路当成一个点，这时就可以把它当成一个互不相连的图，画个图理解一下：
class Solution {int[] f;int find(int x){if(f[x] != x){f[x] = find(f[x]);}return f[x];}public int[] shortestDistanceAfterQueries(int n, int[][] queries) {f = new int[n];for(int i=1; i<n; i++){f[i] = i;}int[] ans = new int[queries.length];int cnt = n-1;for(int i=0; i<queries.length; i++){int l = queries[i][0] + 1；int r = queries[i][1];int j = find(l), fr = find(r);while(j < fr){//将节点 [l+1, R] 联通 cnt--;f[j] = fr;j = find(j+1);}ans[i] = cnt;}return ans;} }
四，3245. 交替组 III
代码如下：
class Fenwick{int[][] t;public Fenwick(int n){t = new int[n][2];}void update(int size, int op){int i=t.length-size;while(i < t.length){t[i][0] += op;t[i][1] += op*size;i += i & -i;}}int[] query(int size){int cnt = 0, sum = 0;int i = t.length - size;while(i > 0){cnt += t[i][0];sum += t[i][1];i -= i & -i;}return new int[]{cnt, sum};}
}
class Solution {public List<Integer> numberOfAlternatingGroups(int[] colors, int[][] queries) {List<Integer> ans = new ArrayList<>();TreeSet<Integer> set = new TreeSet<>();int n = colors.length;Fenwick f = new Fenwick(n+1);for(int i=0; i<n; i++){if(colors[i] == colors[(i+1)%n]){add(set, f, n, i);}}for(int[] q : queries){if(q[0] == 1){if(set.isEmpty()){ans.add(n);}else{int[] res = f.query(q[1]);ans.add(res[1]-res[0]*(q[1]-1));}}else{int i = q[1];if(colors[i] == q[2]) continue;int pre = (i - 1 + n) % n;int nxt = (i + 1) % n;if(colors[pre] == colors[i]){del(set, f, n, pre);}if(colors[nxt] == colors[i]){del(set, f, n, i);}colors[i] ^= 1;if(colors[pre] == colors[i]){add(set, f, n, pre);}if(colors[nxt] == colors[i]){add(set, f, n, i);}}}return ans;}private void add(TreeSet<Integer> set, Fenwick f, int n, int i){if(set.isEmpty()){f.update(n, 1);}else{update(set, f, n, i, 1);}set.add(i);}private void del(TreeSet<Integer> set, Fenwick f, int n, int i){set.remove(i);if(set.isEmpty()){f.update(n, -1);}else{update(set, f, n, i, -1);}}private void update(TreeSet<Integer> set, Fenwick f, int n, int i, int op){Integer pre = set.floor(i);if(pre == null){pre = set.last();}Integer nxt = set.ceiling(i);if(nxt == null){nxt = set.first();}f.update((nxt-pre+n-1)%n+1, -op);f.update((i-pre+n)%n, op);f.update((nxt-i+n)%n, op);}
}