讨论/《数组和字符串》 - 旋转矩阵/
《数组和字符串》 - 旋转矩阵
共 38 个回复
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //1. 对角翻转
        for(auto row=0;row<matrix.size();row++)
        {
            for(auto column=0;column<=row;column++){ 
                swap(matrix[row][column],matrix[column][row]);
            }
        }
      // 2. 镜像翻转
        for(int row=0;row<matrix.size();row++)
        {
            for(int column=0;column<matrix.size()/2;column++){ 
                swap(matrix[row][column],matrix[row][matrix.size()-column-1]);
            }
        }
    }
};
9

JAVA

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;
        if(len==1) return;

        int maxIdx = len-1;
        int[][] newMatrix = new int[len][len];
        for(int y=0; y<len; y++){
            for(int x=0; x<len; x++){
                newMatrix[y][maxIdx-x]=matrix[x][y];
            }
        }
        /* 采用逐个赋值的方法,而不是 matrix=newMatrix。
         *
         * 本题中,java的参数是一个指向源数组的指针,
         * 直接使用 matrix=newMatrix 赋值改变的是参数的指向,
         * 不是传输进去的源数组的指向。所以需要为参数逐个赋值。*/
        for(int y=0; y<len; y++){
            for(int x=0; x<len; x++){
                matrix[x][y]=newMatrix[x][y];
            }
        }
    }
}
7

Python3使用zip,一行搞定

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix[:]=zip(*matrix[::-1])
4

配合std函数,简洁明了的C++写法

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int N = matrix.size();

        //对角线翻转 —— std::swap
        for(int i = 0; i < N; i++)
            for(int j = i + 1; j < N; j++)
                swap(matrix[i][j], matrix[j][i]);

        //水平翻转 —— std::reverse
        for(auto& vec: matrix)
            reverse(vec.begin(), vec.end());
    }
};
4
print('Hello 同学们老师们!')
    def rotate(self, matrix: List[List[int]]) -> None:    
        N = len(matrix)
        #沿着左上端点至右下端点的对角线翻转
        '''通过这一步可以通过第一排前几个元素最后翻转到对应位置,再根据这些结果,推演找出的规律
        需要一定的耐心,基本凭空很难理解,需要根据推演出的规律进行一定量的实验,检验方能在脑中形成大概的肌肉记忆'''
        for i in range(N):
            '''第一层,这里的i即里面每一个列表作为一个整体元素,遍历它们N次'''          
            for j in range(i): 
                '''第二层,这里j的遍历次数为i次,随着第一层的i增大,j遍历的范围也随之增大到最终的i
                在j每一轮遍历里,i都是一个固定值,而且下面的公式时同时进行没有先后,即横坐标纵坐标互换
                那为什么是两组呢,正因为是两组才表示是互换,而且必须同时传递
                如果只有一组matrix[i][j]=matrix[j][i] 就表示单纯把一个位置的值传递给了另一个位置而已就不是互换了
                特别注意:
                i遍历的范围是第一个行遍到最后一行方向向下,J遍历的范围是从0个元素开始,逐渐增大到i'''
                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
        #沿着垂直中心线翻转
        for i in range(N):
            matrix[i][:] = matrix[i][::-1]
            '''matrix[i][::-1]的意思就是第二层里所有的元素反向遍历一遍
            测试了下matrix[::-1][i]展示的样子是沿着水平中心线翻转的效果
            进一步证明了表达的意思是第一层里所有的元素反向遍历一遍
            如果凭空难以在脑中构建感性认识,只需要创造一个矩阵实验下即可
            记得调用
            import numpy as np
            把列表b = [[ 5, 1, 9,11],[ 2, 4, 8,10],[13, 3, 6, 7],[15,14,12,16]]
            传入b  = np.array(b)
            然后再对b进行操作b[::-1][:]或者b[:][::-1]查看结果'''

自我总结:
如果是顺时针旋转90°
一定是先对角线翻转,再水平翻转
如果是逆时针旋转90°
一定是先水平翻转,再对角线翻转
多练习,多观察,如果还是像我一样多次尝试过,仍旧无法理解大神们引用的知识和解题思路,就记住这个应用的套路就行~!
另外我用一张手撕的图来举例说明对角线翻转的时候,是一一互换哪些元素位置,帮助大家有个感性的认识
1617239815(1).png
别人3分钟讲完的东西,我竟然。。。墨迹了4天才搞明白个大概可还行。。
如果哪里有错误的地方,也欢迎大家来毒打我,积极动手实验和一起讨论~

2

因为是整型数据的交换采用异或运算来替代了temp

    /**
     * 给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。
     * <p>
     * 不占用额外内存空间能否做到?
     *
     * @param matrix int类型二维数组
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix[i][j] ^ matrix[n - i - 1][j];
                matrix[n - i - 1][j] = matrix[i][j] ^ matrix[n - i - 1][j];
                matrix[i][j] = matrix[i][j] ^ matrix[n - i - 1][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                matrix[i][j] = matrix[i][j] ^ matrix[j][i];
                matrix[j][i] = matrix[i][j] ^ matrix[j][i];
                matrix[i][j] = matrix[i][j] ^ matrix[j][i];
            }
        }
    }
2

Java
先转置,后列变换。

class Solution {
    public void rotate(int[][] matrix) {
        matrix = Solution.Transpose(matrix);
        matrix = Solution.changeCol(matrix);
    }
    public static int[][] changeCol (int[][] b){
		int [] tmp = new int[b.length];
		for (int i = 0; i< b.length; i++){
			for (int j =0 ;j<b.length/2; j++){
				int temp = b[i][j];
				b[i][j]= b[i][b[i].length-1-j];
				b[i][b[i].length-1-j] = temp;
			}
		}
		return b;
	}
    public static int[][] Transpose(int[][] matrix) {
        for (int i = 0; i< matrix.length; i++){
            for(int j= i; j< matrix[i].length; j++){
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
		return matrix;
    }
}
1

记录一下艰辛的通过过程,不按严格的缩进,根本过不了测试用例。一次次修改,算法已无问题,就是语法错误

1

做点小改进

void rotate(vector<vector<int>>& matrix) {
        int count = matrix.size();
        for(int i = 0; i < count-1; ++i){
            for(int j = i + 1; j < count; ++j){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for(int i = 0; i != count; ++i){
            for(int j = 0; j < count/2; ++j){
                swap(matrix[i][j], matrix[i][count-j-1]);
            }
        }
#    }

image.png

class Solution {
    public void rotate(int[][] matrix) {
        int length = matrix.length;
        int[][] nMatrix = new int[length][length];
        for(int i=0;i<length;i++) {
            for(int j=0;j<matrix[i].length;j++) {
                nMatrix[j][length-(i+1)] = matrix[i][j];
            }
        }
        for(int i=0;i<length;i++){
            for(int j=0;j<nMatrix[i].length;j++) {
                matrix[i][j] = nMatrix[i][j];
            }
        }
        nMatrix = null;
    }
}