本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你两个大小为n x n的二进制矩阵mat和target。现以 90 度顺时针轮转矩阵mat中的元素若干次如果能够使mat与target一致返回true否则返回false。示例 1输入mat[[0,1],[1,0]],target[[1,0],[0,1]]输出true解释顺时针轮转90度一次可以使 mat 和 target 一致。示例 2输入mat[[0,1],[1,1]],target[[1,0],[0,1]]输出false解释无法通过轮转矩阵中的元素使 equal 与 target 一致。示例 3输入mat[[0,0,0],[0,1,0],[1,1,1]],target[[1,1,1],[0,1,0],[0,0,0]]输出true解释顺时针轮转90度两次可以使 mat 和 target 一致。提示n mat.length target.lengthn mat[i].length target[i].length1 n 10mat[i][j]和target[i][j]不是0就是1解法1 先旋转再比较枚举m a t matmat旋转0 , 1 , 2 , 3 0,1,2,30,1,2,3次判断旋转后的m a t matmat是否等于t a r g e t targettarget。旋转方阵有原地算法见[[LeetCode 48. 旋转图像【数组,矩阵】中等]]。classSolution{publicbooleanfindRotation(int[][]mat,int[][]target){for(inti0;i4;i){if(Arrays.deepEquals(mat,target)){returntrue;}rotate(mat);}returnfalse;}// 48. 旋转图像publicvoidrotate(int[][]matrix){intnmatrix.length;for(inti0;in;i){int[]rowmatrix[i];for(intji1;jn;j){// 遍历对角线上方元素做转置inttmprow[j];row[j]matrix[j][i];matrix[j][i]tmp;}for(intj0;jn/2;j){// 遍历左半元素做行翻转inttmprow[j];row[j]row[n-1-j];row[n-1-j]tmp;}}}}classSolution{// 48. 旋转图像voidrotate(vectorvectorintmatrix){intnmatrix.size();for(inti0;in;i){for(intji1;jn;j){// 遍历对角线上方元素做转置swap(matrix[i][j],matrix[j][i]);}ranges::reverse(matrix[i]);// 行翻转}}public:boolfindRotation(vectorvectorintmat,vectorvectorinttarget){for(inti0;i4;i){if(mattarget){returntrue;}rotate(mat);}returnfalse;}};classSolution:# 48. 旋转图像defrotate(self,matrix:List[List[int]])-None:nlen(matrix)fori,rowinenumerate(matrix):forjinrange(i1,n):# 遍历对角线上方元素做转置row[j],matrix[j][i]matrix[j][i],row[j]row.reverse()# 行翻转deffindRotation(self,mat:List[List[int]],target:List[List[int]])-bool:for_inrange(4):ifmattarget:returnTrueself.rotate(mat)returnFalse// 48. 旋转图像funcrotate(matrix[][]int){n:len(matrix)fori,row:rangematrix{forj:i1;jn;j{// 遍历对角线上方元素做转置row[j],matrix[j][i]matrix[j][i],row[j]}slices.Reverse(row)// 行翻转}}funcfindRotation(mat,target[][]int)bool{forrange4{ifslices.EqualFunc(mat,target,slices.Equal[[]int]){returntrue}rotate(mat)}returnfalse}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是m a t matmat的行数和列数。空间复杂度O ( 1 ) O(1)O(1)解法2 直接比较顺时针旋转90 ° 90\degree90°后位于( i , j ) (i, j)(i,j)的元素去哪了根据[[LeetCode 48. 旋转图像【数组,矩阵】中等]]结论如下( i , j ) → 旋转 90 ° ( j , n − 1 − i ) → 旋转 90 ° ( n − 1 − i , n − 1 − j ) → 旋转 90 ° ( n − 1 − j , i ) (i, j) \to^{旋转90\degree} (j, n - 1 - i) \to^{旋转90\degree} (n - 1 - i, n - 1 - j) \to^{旋转90\degree} (n - 1 - j, i)(i,j)→旋转90°(j,n−1−i)→旋转90°(n−1−i,n−1−j)→旋转90°(n−1−j,i)所以对于m a t [ i ] [ j ] mat[i][j]mat[i][j]它需要比较四个位置的值旋转0 00次比较t a r g e t [ i ] [ j ] target[i][j]target[i][j]。旋转1 11次比较t a r g e t [ j ] [ n − 1 − i ] target[j][n - 1 - i]target[j][n−1−i]。旋转2 22次比较t a r g e t [ n − 1 − i ] [ n − 1 − j ] target[n - 1 - i][n - 1-j]target[n−1−i][n−1−j]。旋转3 33次比较t a r g e t [ n − 1 − j ] [ i ] target[n - 1 - j][i]target[n−1−j][i]。如果对于某个旋转次数所有的比较都为真那么返回t r u e truetrue。否则返回f a l s e falsefalse。classSolution{publicbooleanfindRotation(int[][]mat,int[][]target){intnmat.length;intok(14)-1;// boolean[] ok {true, true, true, true};for(inti0;in;i){for(intj0;jn;j){intxmat[i][j];if(x!target[i][j]){ok~(10);// ok[0] false}if(x!target[j][n-1-i]){ok~(11);// ok[1] false}if(x!target[n-1-i][n-1-j]){ok~(12);// ok[2] false}if(x!target[n-1-j][i]){ok~(13);// ok[3] false}if(ok0){// 所有的 ok[i] 都是 falsereturnfalse;}}}returntrue;// 至少有一个 ok[i] 是 true}}classSolution{public:boolfindRotation(vectorvectorintmat,vectorvectorinttarget){intnmat.size();intok(14)-1;// bool ok[4] {true, true, true, true}for(inti0;in;i){for(intj0;jn;j){intxmat[i][j];if(x!target[i][j]){ok~(10);// ok[0] false}if(x!target[j][n-1-i]){ok~(11);// ok[1] false}if(x!target[n-1-i][n-1-j]){ok~(12);// ok[2] false}if(x!target[n-1-j][i]){ok~(13);// ok[3] false}if(ok0){// 所有的 ok[i] 都是 falsereturnfalse;}}}returntrue;// 至少有一个 ok[i] 是 true}};classSolution:deffindRotation(self,mat:List[List[int]],target:List[List[int]])-bool:ok(14)-1# ok [True] * 4fori,rowinenumerate(mat):forj,xinenumerate(row):ifx!target[i][j]:ok~(10)# ok[0] Falseifx!target[j][-1-i]:ok~(11)# ok[1] Falseifx!target[-1-i][-1-j]:ok~(12)# ok[2] Falseifx!target[-1-j][i]:ok~(13)# ok[3] Falseifok0:# 所有的 ok[i] 都是 FalsereturnFalsereturnTrue# 至少有一个 ok[i] 是 TruefuncfindRotation(mat,target[][]int)bool{n:len(mat)ok:14-1// ok : [4]bool{true, true, true, true}fori,row:rangemat{forj,x:rangerow{ifx!target[i][j]{ok^10// ok[0] false}ifx!target[j][n-1-i]{ok^11// ok[1] false}ifx!target[n-1-i][n-1-j]{ok^12// ok[2] false}ifx!target[n-1-j][i]{ok^13// ok[3] false}ifok0{// 所有的 ok[i] 都是 falsereturnfalse}}}returntrue// 至少有一个 ok[i] 是 true}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是m a t matmat的行数和列数。空间复杂度O ( 1 ) O(1)O(1)
LeetCode 1886. 判断矩阵经轮转后是否一致【矩阵旋转】简单
本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你两个大小为n x n的二进制矩阵mat和target。现以 90 度顺时针轮转矩阵mat中的元素若干次如果能够使mat与target一致返回true否则返回false。示例 1输入mat[[0,1],[1,0]],target[[1,0],[0,1]]输出true解释顺时针轮转90度一次可以使 mat 和 target 一致。示例 2输入mat[[0,1],[1,1]],target[[1,0],[0,1]]输出false解释无法通过轮转矩阵中的元素使 equal 与 target 一致。示例 3输入mat[[0,0,0],[0,1,0],[1,1,1]],target[[1,1,1],[0,1,0],[0,0,0]]输出true解释顺时针轮转90度两次可以使 mat 和 target 一致。提示n mat.length target.lengthn mat[i].length target[i].length1 n 10mat[i][j]和target[i][j]不是0就是1解法1 先旋转再比较枚举m a t matmat旋转0 , 1 , 2 , 3 0,1,2,30,1,2,3次判断旋转后的m a t matmat是否等于t a r g e t targettarget。旋转方阵有原地算法见[[LeetCode 48. 旋转图像【数组,矩阵】中等]]。classSolution{publicbooleanfindRotation(int[][]mat,int[][]target){for(inti0;i4;i){if(Arrays.deepEquals(mat,target)){returntrue;}rotate(mat);}returnfalse;}// 48. 旋转图像publicvoidrotate(int[][]matrix){intnmatrix.length;for(inti0;in;i){int[]rowmatrix[i];for(intji1;jn;j){// 遍历对角线上方元素做转置inttmprow[j];row[j]matrix[j][i];matrix[j][i]tmp;}for(intj0;jn/2;j){// 遍历左半元素做行翻转inttmprow[j];row[j]row[n-1-j];row[n-1-j]tmp;}}}}classSolution{// 48. 旋转图像voidrotate(vectorvectorintmatrix){intnmatrix.size();for(inti0;in;i){for(intji1;jn;j){// 遍历对角线上方元素做转置swap(matrix[i][j],matrix[j][i]);}ranges::reverse(matrix[i]);// 行翻转}}public:boolfindRotation(vectorvectorintmat,vectorvectorinttarget){for(inti0;i4;i){if(mattarget){returntrue;}rotate(mat);}returnfalse;}};classSolution:# 48. 旋转图像defrotate(self,matrix:List[List[int]])-None:nlen(matrix)fori,rowinenumerate(matrix):forjinrange(i1,n):# 遍历对角线上方元素做转置row[j],matrix[j][i]matrix[j][i],row[j]row.reverse()# 行翻转deffindRotation(self,mat:List[List[int]],target:List[List[int]])-bool:for_inrange(4):ifmattarget:returnTrueself.rotate(mat)returnFalse// 48. 旋转图像funcrotate(matrix[][]int){n:len(matrix)fori,row:rangematrix{forj:i1;jn;j{// 遍历对角线上方元素做转置row[j],matrix[j][i]matrix[j][i],row[j]}slices.Reverse(row)// 行翻转}}funcfindRotation(mat,target[][]int)bool{forrange4{ifslices.EqualFunc(mat,target,slices.Equal[[]int]){returntrue}rotate(mat)}returnfalse}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是m a t matmat的行数和列数。空间复杂度O ( 1 ) O(1)O(1)解法2 直接比较顺时针旋转90 ° 90\degree90°后位于( i , j ) (i, j)(i,j)的元素去哪了根据[[LeetCode 48. 旋转图像【数组,矩阵】中等]]结论如下( i , j ) → 旋转 90 ° ( j , n − 1 − i ) → 旋转 90 ° ( n − 1 − i , n − 1 − j ) → 旋转 90 ° ( n − 1 − j , i ) (i, j) \to^{旋转90\degree} (j, n - 1 - i) \to^{旋转90\degree} (n - 1 - i, n - 1 - j) \to^{旋转90\degree} (n - 1 - j, i)(i,j)→旋转90°(j,n−1−i)→旋转90°(n−1−i,n−1−j)→旋转90°(n−1−j,i)所以对于m a t [ i ] [ j ] mat[i][j]mat[i][j]它需要比较四个位置的值旋转0 00次比较t a r g e t [ i ] [ j ] target[i][j]target[i][j]。旋转1 11次比较t a r g e t [ j ] [ n − 1 − i ] target[j][n - 1 - i]target[j][n−1−i]。旋转2 22次比较t a r g e t [ n − 1 − i ] [ n − 1 − j ] target[n - 1 - i][n - 1-j]target[n−1−i][n−1−j]。旋转3 33次比较t a r g e t [ n − 1 − j ] [ i ] target[n - 1 - j][i]target[n−1−j][i]。如果对于某个旋转次数所有的比较都为真那么返回t r u e truetrue。否则返回f a l s e falsefalse。classSolution{publicbooleanfindRotation(int[][]mat,int[][]target){intnmat.length;intok(14)-1;// boolean[] ok {true, true, true, true};for(inti0;in;i){for(intj0;jn;j){intxmat[i][j];if(x!target[i][j]){ok~(10);// ok[0] false}if(x!target[j][n-1-i]){ok~(11);// ok[1] false}if(x!target[n-1-i][n-1-j]){ok~(12);// ok[2] false}if(x!target[n-1-j][i]){ok~(13);// ok[3] false}if(ok0){// 所有的 ok[i] 都是 falsereturnfalse;}}}returntrue;// 至少有一个 ok[i] 是 true}}classSolution{public:boolfindRotation(vectorvectorintmat,vectorvectorinttarget){intnmat.size();intok(14)-1;// bool ok[4] {true, true, true, true}for(inti0;in;i){for(intj0;jn;j){intxmat[i][j];if(x!target[i][j]){ok~(10);// ok[0] false}if(x!target[j][n-1-i]){ok~(11);// ok[1] false}if(x!target[n-1-i][n-1-j]){ok~(12);// ok[2] false}if(x!target[n-1-j][i]){ok~(13);// ok[3] false}if(ok0){// 所有的 ok[i] 都是 falsereturnfalse;}}}returntrue;// 至少有一个 ok[i] 是 true}};classSolution:deffindRotation(self,mat:List[List[int]],target:List[List[int]])-bool:ok(14)-1# ok [True] * 4fori,rowinenumerate(mat):forj,xinenumerate(row):ifx!target[i][j]:ok~(10)# ok[0] Falseifx!target[j][-1-i]:ok~(11)# ok[1] Falseifx!target[-1-i][-1-j]:ok~(12)# ok[2] Falseifx!target[-1-j][i]:ok~(13)# ok[3] Falseifok0:# 所有的 ok[i] 都是 FalsereturnFalsereturnTrue# 至少有一个 ok[i] 是 TruefuncfindRotation(mat,target[][]int)bool{n:len(mat)ok:14-1// ok : [4]bool{true, true, true, true}fori,row:rangemat{forj,x:rangerow{ifx!target[i][j]{ok^10// ok[0] false}ifx!target[j][n-1-i]{ok^11// ok[1] false}ifx!target[n-1-i][n-1-j]{ok^12// ok[2] false}ifx!target[n-1-j][i]{ok^13// ok[3] false}ifok0{// 所有的 ok[i] 都是 falsereturnfalse}}}returntrue// 至少有一个 ok[i] 是 true}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是m a t matmat的行数和列数。空间复杂度O ( 1 ) O(1)O(1)
