A.每日一题：2946. 循环移位后的矩阵相似检查

题目链接2946. 循环移位后的矩阵相似检查简单算法原理解法模拟1ms击败100.00%时间复杂度O(mn)针对每一行a首先我们要找到左移和右移k次后的位置在哪n为该行一维数组的长度右移k次i的最终位置在(ik)%n左移k次i的最终位置在(i-k)%n由于是减法因此需要额外n避免负数且k要%n否则会出现0-32%2-1的情况那么接下来就很好解决了对每一行进行判断如果该行是奇数行就右移检查最终是否相同如果该行是偶数行就左移检查最终是否相同只要其中有一个不相同直接返回false优化1ms击败100.00%时间复杂度O(mn)在上述式子中如果要保证移位后的数组与原数组相同右移要保证a[(ik)%n]a[i]①左移要保证a[(i-k)%n]a[i]②其实这两个式子是等价的因为我们把 i(i-k)%n代入①式会发现a[i%n]a[(i-k)%n]也就是说a[i]a[(i-k)%n]这正好就是①式因此我们针对奇偶数完全可以只用这一个式子来判断Java代码class Solution { public boolean areSimilar(int[][] mat, int k) { int mmat.length; for(int i0;im;i) if(!turn(mat[i],k,i%21)) return false; return true; } private boolean turn(int[] a,int k,boolean odd){ int na.length; k%n; int[] retnew int[n]; if(odd) for(int i0;in;i) ret[(ik)%n]a[i]; else for(int i0;in;i) ret[(i-kn)%n]a[i]; for(int i0;in;i) if(ret[i]!a[i]) return false; return true; } }class Solution { //优化 public boolean areSimilar(int[][] mat, int k) { int mmat.length; for(int i0;im;i) if(!turn(mat[i],k)) return false; return true; } private boolean turn(int[] a,int k){ int na.length; int[] retnew int[n]; for(int i0;in;i) ret[(ik)%n]a[i]; for(int i0;in;i) if(ret[i]!a[i]) return false; return true; } }