LeetCode 2946. 循环移位后的矩阵相似检查【数学周期性+原地比较】简单

本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你一个下标从 0 开始且大小为m x n的整数矩阵mat和一个整数k。请你将矩阵中的奇数行循环右移k次偶数行循环左移k次。如果初始矩阵和最终矩阵完全相同则返回true否则返回false。示例 1输入mat[[1,2,1,2],[5,5,5,5],[6,3,6,3]],k2输出true解释初始矩阵如图一所示。图二表示对奇数行右移一次且对偶数行左移一次后的矩阵状态。图三是经过两次循环移位后的最终矩阵状态与初始矩阵相同。因此返回true。示例 2输入mat[[2,2],[2,2]],k3输出true解释由于矩阵中的所有值都相等即使进行循环移位矩阵仍然保持不变。因此返回true。示例 3输入mat[[1,2]],k1输出false解释循环移位一次后mat [[2,1]]与初始矩阵不相等。因此返回false。提示1 mat.length 251 mat[i].length 251 mat[i][j] 251 k 50解法 数学周期性原地比较1. 循环移位的对称性在一个长度为n nn的序列中左移k kk次等同于右移n − ( k m o d n ) n - (k\bmod n)n−(kmodn)次。要让一个序列在移位后保持“不变”唯一的条件是该序列具有以d dd为周期的特性且k kk是d dd的倍数。无论向左移还是向右移要回到原点本质上都是在要求这一行数据具有某种周期性。如果一个序列左移k kk次能还原那么它右移k kk次也一定能还原——即一行左移k kk次等于自己那这个过程的逆过程就是把自己右移k kk次得到自己。由于我们要对比的是位移前后的整行是否完全一致对于每一行来说只要满足mat[i][j] mat[i][(j k) % n]那么无论这一行是左移还是右移结果都是一样的。代码实现时的技巧我们不需要真的去模拟左移和右移。只需要检查每一行是否满足m a t [ i ] [ j ] ≡ m a t [ i ] [ ( j k ) m o d n ] mat[i][j] \equiv mat[i][(j k) \bmod n]mat[i][j]≡mat[i][(jk)modn]如果矩阵的所有元素都满足这个等式返回true。因为循环移动k kk位后保持不变意味着这一行存在一个步长为k m o d n k\bmod nkmodn的周期行数据的周期性。classSolution{publicbooleanareSimilar(int[][]mat,intk){intnmat[0].length;for(int[]row:mat){for(intj0;jn;j){if(row[j]!row[(jk)%n]){returnfalse;}}}returntrue;}}classSolution{public:boolareSimilar(vectorvectorintmat,intk){intnmat[0].size();for(autorow:mat){for(intj0;jn;j){if(row[j]!row[(jk)%n]){returnfalse;}}}returntrue;}};classSolution:defareSimilar(self,mat:List[List[int]],k:int)-bool:k%len(mat[0])# 右移 n 次等价于右移 0 次右移 n1 次等价于右移 1 次依此类推先模个 nreturnk0orall(rowrow[k:]row[:k]forrowinmat)# 写法二classSolution:defareSimilar(self,mat:List[List[int]],k:int)-bool:nlen(mat[0])forrowinmat:forjinrange(n):ifrow[j]!row[(jk)%n]:returnFalsereturnTrueimplSolution{pubfnare_similar(mat:VecVeci32,k:i32)-bool{letnmat[0].len();letkkasusize;forrowinmat{forjin0..n{ifrow[j]!row[(jk)%n]{returnfalse;}}}true}}funcareSimilar(mat[][]int,kint)bool{n:len(mat[0])for_,row:rangemat{forj,x:rangerow{ifx!row[(jk)%n]{returnfalse}}}returntrue}// 写法二funcareSimilar(mat[][]int,kint)bool{k%len(mat[0])// 右移 n 次等价于右移 0 次右移 n1 次等价于右移 1 次依此类推先模个 nfor_,row:rangemat{if!slices.Equal(row,append(row[k:],row[:k]...)){returnfalse}}returntrue}varareSimilarfunction(mat,k){constnmat[0].length;for(constrowofmat){for(letj0;jn;j){if(row[j]!row[(jk)%n]){returnfalse;}}}returntrue;};boolareSimilar(int**mat,intmatSize,int*matColSize,intk){intnmatColSize[0];for(inti0;imatSize;i){int*rowmat[i];for(intj0;jn;j){if(row[j]!row[(jk)%n]){returnfalse;}}}returntrue;}复杂度分析时间复杂度O ( m n ) O(mn)O(mn)其中m mm和n nn分别是m a t matmat的行数和列数。空间复杂度O ( 1 ) O(1)O(1)。