第 498 场周赛Q1~Q3

Q1Q2题目链接101046. 最小稳定下标 I简单101047. 最小稳定下标 II中等算法原理解法前缀和-前后缀分解Ⅰ中1ms击败100.00%Ⅱ中8ms击败51.69%时间复杂度O(N)思路很简单模拟题述max数组和min数组就是前缀和的经典思路由于我们要求最小下标因此先计算min数组再从前往后遍历获取max数组然后判断max[i]-min[i]≤k是否成立成立就直接返回下标 i细节①上述过程适用数组长度≥2的情况当数组长度为1时max[i]-min[i]必然为0我们仅需判断0≤k是否成立即可②从前往后遍历的时候不能从下标1开始否则会遗漏下标为0的情况因此用if判断一下如果下标0再去更新max数组避免越界Ⅰ和Ⅱ题只是数据范围不同上述思路完全适用Ⅰ题和Ⅱ题因此代码完全相同Java代码class Solution { public int firstStableIndex(int[] nums, int k) { int nnums.length; if(n1) return 0k?0:-1; int[] maxnew int[n]; max[0]nums[0]; int[] minnew int[n]; min[n-1]nums[n-1]; for(int in-2;i0;i--) min[i]Math.min(nums[i],min[i1]); for(int i0;in;i){ if(i0) max[i]Math.max(nums[i],max[i-1]); if(max[i]-min[i]k) return i; } return -1; } }Q3题目链接101045. 多源洪水灌溉中等算法原理解法BFS143ms击败44.35%时间复杂度O(mn)完整思考过程因为此题属于逐层扩散因此参考蓝桥杯关键知识点速记中的网格BFS模板①由于sources[i] [ri, ci, colori]里有三个参数因此我们在创建队列的时候要写成Queueint[],Integer分别表示坐标和对应颜色②但是出现了个问题在后续弹出队列的时候用什么类型接收呢因此我们想到把int[]和Integer封装成一个类全放在一起写成Combine类③那么接下来我们就可以模拟BFS的过程了把sources[i]中的坐标和颜色加入队列只要该位置四周不越界且数值更小整个网格未被填满就可以把其位置扔进队列里对应代码class Combine{ int[] xy; int color; public Combine(int[] xy,int color){ this.xyxy; this.colorcolor; } } class Solution { private final int[] dx{0,0,1,-1}; private final int[] dy{1,-1,0,0}; public int[][] colorGrid(int n, int m, int[][] sources) { int[][] matnew int[n][m]; QueueCombine qnew LinkedList(); for(int[] t:sources) q.add(new int[]{t[0],t[1]},t[2]); while(!q.isEmpty()){ Combine tq.poll(); int at.xy[0]; int bt.xy[1]; int colort.color; for(int k0;k4;k){ int xadx[k],ybdy[k]; if(x0xny0ymmat[x][y]color!check(mat)){ q.add(new int[]{x,y},color); mat[x][y]color; } } } return mat; } //判断是否被填满 private boolean check(int[][] mat){ for(int[] m:mat) for(int x:m) if(x0) return false; return true; } }错误点分析①编译错误QueueCombine只能接收Combine对象原来的q.add(new int[]{...}, color)是错误的传参更改new Combine(new int[]{x,y}, color)创建对象入队②修复初始状态错误初始源点的颜色没有写入mat数组导致初始状态全 0更改初始化队列时同步给源点赋值颜色③修复核心 BFS 逻辑错误题目要求同一时间步的扩散同时发生同位置选最大颜色普通的逐个 poll 的 BFS 会导致先到先染无法正确选最大颜色更改按时间按层处理先收集当前时间所有待扩散的位置对同一位置保留最大颜色统一给所有位置染色再将新染色的节点加入下一层队列④删除无效且超时的 check 函数check函数每次遍历整个矩阵时间复杂度极高更改当没有新的可染色格子时hash为空队列会自动清空循环结束⑤修复扩散条件错误题目仅允许扩散到未着色的格子已着色的格子无论颜色大小都不会被修改更改把mat[x][y]color改为mat[x][y]0修改后的代码思路①初始化源点颜色正确创建Combine对象入队②按时间按层处理保证同一时间的扩散同时计算→利用哈希表存储同一时间下对应位置最大颜色③遍历当前层所有节点收集待扩散位置保留最大颜色仅未着色的格子可被扩散我们可用数字编码坐标x*my存进哈希表避免字符串性能损耗答疑那我用位运算压缩进一个int里不行吗用(x16)|y编码坐标破译的时候用x(key(0xffff16))16key0xffff呗回答不可以因为0xffff 只有 16 位最大值是 65535。但题目里 n 和 m 最大可以到100000超过了 16 位的最大值会导致1.坐标数值溢出编码后的 key 解码出来的x/y和原值不一致2.Java 中是算术右移高位会补符号位解码出负数的 x/y直接触发数组越界④同一染色当前时间下的格子加入下一层队列Java代码class Combine{ int[] xy; int color; public Combine(int[] xy,int color){ this.xyxy; this.colorcolor; } } class Solution { private final int[] dx{0,0,1,-1}; private final int[] dy{1,-1,0,0}; public int[][] colorGrid(int n, int m, int[][] sources) { int[][] matnew int[n][m]; QueueCombine qnew LinkedList(); for(int[] t:sources){ mat[t[0]][t[1]]t[2]; q.add(new Combine(new int[]{t[0],t[1]},t[2])); } while(!q.isEmpty()){ //按层处理按时间走 int sizeq.size(); MapInteger,Integer hashnew HashMap(); //遍历当前层所有节点收集所有待扩散的位置保留最大颜色 for(int i0;isize;i){ Combine tq.poll(); int at.xy[0]; int bt.xy[1]; int colort.color; for(int k0;k4;k){ int xadx[k],ybdy[k]; if(x0xny0ymmat[x][y]0){ int keyx*my; hash.put(key,Math.max(hash.getOrDefault(key,0),color)); } } } //统一染色当前时间的格子加入下一队列 for(Map.EntryInteger,Integer entry:hash.entrySet()){ int keyentry.getKey(); int xkey/m; int ykey%m; int colorentry.getValue(); mat[x][y]color; q.add(new Combine(new int[]{x,y},color)); } } return mat; } }