Leecode热题100-48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

我先用一个比较简单的使用一个辅助矩阵的解一下（这个虽然也能过也超过100%的人但是面试过不去，慎用）

class Solution {public void rotate(int[][] matrix) {int len = matrix.length;if(len == 1) return;/*这个解法的空间复杂度是O(N^2)int[][] copy = new int[len][len];for(int i = 0; i < len; i++) {for(int j = 0; j < len; j++) {copy[j][len - 1 - i] = matrix[i][j];}}for(int i = 0; i < len; i++) {for(int j = 0; j < len; j++) {matrix[i][j] = copy[i][j];}}*///翻转代替旋转//matrix[row][col] 水平轴翻转得到matrix[n−row−1][col]//对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，即//主对角线翻转，即Matrix[row][col]变成matrix[col][row]//将它们联立即可得到：matrix[row][col]水平轴翻转matrix[n−row−1][col]//主对角线翻转得到matrix[col][n−row−1]for(int i = 0 ; i < len; i++) {for(int j = 0; j < len; j++) {if(i < len - 1 - i) {swap(matrix, i, j, len - 1 - i, j);}}}for(int i = 0; i < len; i++) {for(int j = 0; j < len; j++) {if(i < j) {swap(matrix, i, j, j, i);}}}}public void swap(int[][] matrix, int i1, int j1, int i2, int j2) {int temp = matrix[i1][j1];matrix[i1][j1] = matrix[i2][j2];matrix[i2][j2] = temp;}
}

本题的正确解法，这个是独家解法，百分比天下第一的解

class Solution {/**解题大概思路是从外到内一圈一圈进行旋转，刚开始的时候左上和右下点分别是(0,0),(n-1,n-1)针对于某一圈来说，我们把这些点分为几类，四个顶点作为第0种节点，然后左上角右移i，右上角下移i，右下角左移i，左下角上移i作为第i种节点每种节点各有四个，i的变化范围从0到当前圈的长度-1，这个长度通过左上角的顶点（tr,tc）和右下角的点(dr,dc)计算得到对于第i种节点，这四个节点分别是(tr,tc+i) (tr+i, dc) (dr,dc-i) (dr-i,tc) */public void rotate(int[][] matrix) {/**首先确认第一个圈的左上角*/int tr = 0, tc = 0;/**确人第一个圈的右下角 */int dr = matrix.length - 1, dc = matrix.length - 1;/**每次tr，tc变为tr+1,tc+1作为下个圈的左上角 ，dr,dc变为dr-1, dc -1 作为右下角tr相对于dr每次会变化2，如果tr>dr才是正方形，不然的话没有任何形状*/while(tr < dr) {rotateCurCircle(matrix, tr++, tc ++, dr --, dc --);}}/***在matrix上90度旋转以(tr，tc)作为左上角和以(dr,dc)作为右下角的正方形*/public void rotateCurCircle(int[][] matrix, int tr, int tc, int dr, int dc) {/**正方形的边长 */int sideLen = dr - tr + 1;/**对于这样一个正方形，我们有边长-1种点 */for(int i = 0; i < sideLen - 1; i++) {/**下面要进行的是四个点的互换工作，也就是旋转90度，先记录一下第四个点的值 *//**四个点分别旋转90度，先记录第四个点到temp */int temp = matrix[dr-i][tc];/**第三个点的值赋值给第四个点 */matrix[dr-i][tc] = matrix[dr][dc-i];/**第二个点的值赋值给第三个点 */matrix[dr][dc-i] = matrix[tr+i][dc];/**第一个点的值赋值给第二个点 */matrix[tr+i][dc] = matrix[tr][tc+i];/**temp（原来保存的第四个点的值）赋值给第一个点 */matrix[tr][tc+i] = temp;}}
}