题目链接Q13880. 两个值之间的最小绝对差值简单Q23881. 恰好看到 K 个人的方向选择中等Q33882. 网格图中最小异或路径中等算法原理Q1解法双指针时间复杂度O(N)1ms击败100.00%双指针专题模型可参考下面这篇博客一轮复习——B.双指针模型总结本题属于“同向双指针-求两点A、B间距离“思路很简单用prev指向前一个是1或2的位置当前遍历时遇到2或1就更新取距离最小值其中prev初始化为-1保证一开始指向非0位置并且在枚举过程中能够不断更新位置比如nums[0,1,1,2]当 i 枚举到2时prev在下标2的1而不是停留在下标1的1上Q2解法高中的排列组合快速幂费马小定理时间复杂度O(min(k,n)190ms击败25.30%从上图我们可以发现其实对pos位置的人来说无所谓左右边有几个L、R我们完全可以看成“是否有效”我们仅需关注一共有多少个有效的个数即可那么这个过程其实就是在5个位置中选2个结果×pos位置的两种选择(L或R)即可在5个位置中选2个在高中的排列组合知识中可表示为排除pos这个位置后还有n-1个位置从中选k个因此此题的返回值就简单return 2×(1)计算方法设计①k0或n直接返回1②计算时取min(k,n-k)减小计算次数③我们发现上下都是k个数因此我们仅需循环k次每次循环只干两件事Ⅰ×分子(n-ki)依次是(n−k1), (n−k2), …, nⅡ÷分母i 依次是1, 2, …, k细节计算机的模运算里不认可除法比如15÷3正常数学中15÷35没问题在%7的世界中15%711÷3注意这里不是0.333……而是找一个x∈0~6使得3×x%71我们来尝试3×13 → 余 3 ≠13×26 → 余 6 ≠13×39 → 9%72 ≠13×412→12%75≠13×515→15%71 ✅因此我们不能直接写 ret / i 而是要×即× i 的倒数在模运算的世界中“倒数”叫“逆元”数学家们发现MOD为质数时i 的逆元iᴹᴼᴰ⁻²费马小定理因此要写成retret*pow(i,MOD-2)%MOD;(2)快速幂方法设计快速幂的原理可参考下面这篇博客中的Q514届蓝桥杯省赛Java A 组Q4~Q5优化4ms击败100.00%时间复杂度O(1)根据公式我们其实仅需用到所有数的阶乘和其阶乘的逆元题目范围1≤n≤10⁵因此我们可以干脆一次性把所有数的阶乘及其阶乘逆元全部预处理出来然后排列组合时用到哪个直接拿哪个即可①这里的阶乘逆元计算时采用倒着递推因此代码写成//预处理所有阶乘的逆元 //先算出第一个 INV_F[MX-1]pow(F[MX-1],MOD-2); //倒着推出所有逆元 for(int iMX-1;i0;i--) INV_F[i-1]INV_F[i]*i%MOD;②计算方法设计根据因此可直接返回n!×k!的逆元×(n-k)!的逆元F[n]×INV_F[k]×INV_F[n-k]过程中持续取模防止溢出代码写成return F[n]*INV_F[k]%MOD*INV_F[n-k]%MOD;Q3解法动态规划时间复杂度O(M×N×1024)120ms击败90.80%①状态表示dp[i][j][x]从起点 (0, 0) 出发到达网格位置 (i, j) 时是否存在一条路径使得该路径上所有数值的异或结果恰好等于 xtrue表示可达false表示不可达②状态转移方程到达位置 (i, j) 的路径只能来自两个方向从上方 (i-1, j) 移动而来从左方 (i, j-1) 移动而来因此状态转移需合并这两个方向的可行状态if(dp[i-1][j][x]) dp[i][j][x^grid[i][j]]true; if(dp[i][j-1][x]) dp[i][j][x^grid[i][j]]true;③初始化起点没有任何移动路径异或值自身的值dp[0][0][grid[0][0]] true;第一行只能由左方移动而来//处理第一行 for(int j1;jn;j){ for(int x0;x1024;x){ if(dp[0][j-1][x]){ dp[0][j][x^grid[0][j]]true; } } }第一列只能由上方移动而来//处理第一列 for(int i1;im;i){ for(int x0;x1024;x){ if(dp[i-1][0][x]){ dp[i][0][x^grid[i][0]]true; } } }④填表顺序从上往下从左往右⑤返回值终点 (m-1, n-1) 的所有可行异或值中的最小值Java代码Q1class Solution { //3880. 两个值之间的最小绝对差值 public int minAbsoluteDifference(int[] nums) { int ret0x3f3f3f3f,prev-1; for(int i0;inums.length;i){ if(prev-1nums[i]!0) previ; if(prev!-1){ if(nums[prev]1nums[i]2||nums[prev]2nums[i]1){ retMath.min(ret,Math.abs(i-prev)); previ; } if(nums[prev]nums[i]) previ; } } return ret0x3f3f3f3f?-1:ret; } }Q2class Solution { //3881. 恰好看到 K 个人的方向选择 private final int MOD1_000_000_007; public int countVisiblePeople(int n, int pos, int k) { return (int)(2*comb(n-1,k)%MOD); } private long pow(long a,long b){ long ret1; for(;b0;b1){ if((b1)1) retret*a%MOD; aa*a%MOD; } return ret%MOD; } private long comb(int n,int k){ if(k0||kn) return 1; kMath.min(k,n-k); long ret1; for(int i1;ik;i){ //先乘分子取模避免溢出 retret*(n-ki)%MOD; //÷i:直接/i会算错因此×i的倒数费马小定理i的倒数iᴹᴼᴰ⁻² retret*pow(i,MOD-2)%MOD; } return ret; } }class Solution { //优化 //3881. 恰好看到 K 个人的方向选择 private static final int MOD1_000_000_007; private static final int MX100_001; //记录各数阶乘 private static final long[] Fnew long[MX]; //记录各数逆元 private static final long[] INV_Fnew long[MX]; //标记是否预处理过 private static boolean initfalse; public Solution(){ if(init) return; inittrue; F[0]1;//0!1 //预处理所有阶乘递推计算1!~1e5! for(int i1;iMX;i) F[i]F[i-1]*i%MOD; //预处理所有阶乘的逆元 INV_F[MX-1]pow(F[MX-1],MOD-2); //倒着推出所有逆元 for(int iMX-1;i0;i--) INV_F[i-1]INV_F[i]*i%MOD; } public int countVisiblePeople(int n, int pos, int k) { return (int)(2*comb(n-1,k)%MOD); } private long pow(long a,long b){ long ret1; for(;b0;b1){ if((b1)1) retret*a%MOD; aa*a%MOD; } return ret%MOD; } private long comb(int n,int k){ return F[n]*INV_F[k]%MOD*INV_F[n-k]%MOD; } }Q3class Solution { public int minCost(int[][] grid) { int mgrid.length; int ngrid[0].length; boolean[][][] dpnew boolean[m][n][1024]; dp[0][0][grid[0][0]]true; //处理第一行 for(int j1;jn;j){ for(int x0;x1024;x){ if(dp[0][j-1][x]){ dp[0][j][x^grid[0][j]]true; } } } //处理第一列 for(int i1;im;i){ for(int x0;x1024;x){ if(dp[i-1][0][x]){ dp[i][0][x^grid[i][0]]true; } } } //处理剩余网格 for(int i1;im;i){ for(int j1;jn;j){ //从上方(i-1,j)转移而来 for(int x0;x1024;x){ if(dp[i-1][j][x]){ dp[i][j][x^grid[i][j]]true; } } //从左方(i,j-1)转移而来 for(int x0;x1024;x){ if(dp[i][j-1][x]){ dp[i][j][x^grid[i][j]]true; } } } } //遍历终点所有可行异或值找到最小值 for(int x0;x1024;x){ if(dp[m-1][n-1][x]){ return x; } } //照顾编译器 return -1; } }