网站开发联系方式,专注郑州网站建设,html教程 it教程网,个人网站怎么建设目录
一#xff0c;3242. 设计相邻元素求和服务
二#xff0c;3243. 新增道路查询后的最短距离 I
三#xff0c;3244. 新增道路查询后的最短距离 II
四#xff0c;3245. 交替组 III 一#xff0c;3242. 设计相邻元素求和服务 本题纯模拟#xff0c;代码如下#xff…目录
一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 i0; in; i){for(int j0; jm; j){if(t[i][j] value){x i;y j;break;}}if(x!-1 y!-1) break;}int ans 0;if(x0) ans t[x-1][y];if(y0) ans t[x][y-1];if(x1n) ans t[x1][y];if(y1m) ans t[x][y1];return ans;}public int diagonalSum(int value) {int x-1, y-1;for(int i0; in; i){for(int j0; jm; j){if(t[i][j] value){x i;y j;break;}}if(x!-1 y!-1) break;}int ans 0;if(x0 y0) ans t[x-1][y-1];if(x0 y1m) ans t[x-1][y1];if(x1n y0) ans t[x1][y-1];if(x1n y1m) anst[x1][y1];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];ListInteger[] g new ArrayList[n];Arrays.setAll(g, e-new ArrayList());for(int i0; in-1; i){g[i].add(i1);}int k 0;for(int[] q : queries){g[q[0]].add(q[1]);QueueInteger 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] cnt1;}}}}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) {TreeSetInteger set new TreeSet();for(int i0; in; i) set.add(i);int[] ans new int[queries.length];for(int i0; iqueries.length; i){int l queries[i][0], r queries[i][1];找到l1的最小的值,使用红黑树实现时间复杂度O(logn)Integer ceiling set.ceiling(l1);//删除(l,r)之间的点while(ceiling ! null ceiling r){set.remove(ceiling);ceiling set.ceiling(l1);}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 i1; in; i){f[i] i;}int[] ans new int[queries.length];int cnt n-1;for(int i0; iqueries.length; i){int l queries[i][0] 1int r queries[i][1];int j find(l), fr find(r);while(j fr){//将节点 [l1, R] 联通 cnt--;f[j] fr;j find(j1);}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 it.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 ListInteger numberOfAlternatingGroups(int[] colors, int[][] queries) {ListInteger ans new ArrayList();TreeSetInteger set new TreeSet();int n colors.length;Fenwick f new Fenwick(n1);for(int i0; in; i){if(colors[i] colors[(i1)%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(TreeSetInteger 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(TreeSetInteger 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(TreeSetInteger 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-pren-1)%n1, -op);f.update((i-pren)%n, op);f.update((nxt-in)%n, op);}
}
