力扣48.旋转图像

一、前言

力扣48.旋转图像

这道题要求把给定矩阵旋转90度，并且不允许使用额外矩阵来完成旋转图像。

于是这道题只能使用原地旋转的方法来解决

二、原地旋转

对于一个N=3的矩阵来说，只需要两次循环就可以完成了

1. 将A1放到A3的位置，A3放到C3的位置，C3放到C1的位置，A1的位置放原C1的值
2. 将A2放到B3的位置，B3放到C2的位置，C2放到B1的位置，A2的位置放原B1的值

也就是需要循环N - 1次

而对于一个N=4的，会出现两个环，每个环需要进行需要进行3次循环。

从此可以得出规律，对于每一个N × N的矩阵来说，都会有N / 2个环需要原地旋转，每个环需要循环N - 1 - i次，其中i为第几个环，因为环越往内，环的循环次数就越少。

int n = matrix.length;
int k = n / 2;
for (int i = 0; i < k; i++) {
    for (int j = i; j < n - i - 1; j++) {
		// 交换
    }
}

于是，本题的关键就是需要确定四个需要交换数值的坐标的表达式

1. 左上：(i, j)
2. 左下：(n - j -1, i)，**n - j -1是因为在同一个环中，行是会变化的，而列却不会变化，永远是同一列，随着环的变化，列才会变化！**比如N=4，第一次左上为A1，左下为D1；第二次左上为A2，而左下为C1；因此可以看出行是会跟着j变化的，而列是跟着i变化的。
3. 右上：(j, n - i -1)，行是跟着j变化的，而列是跟着i变化的，比如N=4，A1对应的是A4，A2对应的是B4，其中列随着环变化而变化，而行随着j变化而变化。
4. 右下：(n - i -1, n - j - 1)，和前面分析差不多

推算出来四个需要交换的下标后，这道题就完成了百分之九十了

public void rotate(int[][] matrix) {
    int n = matrix.length;
    int k = n / 2;
    for (int i = 0; i < k; i++) {
        for (int j = i; j < n - i - 1; j++) {
            int t = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n  - j - 1][i] = matrix[n  - i- 1][n - j - 1];
            matrix[n  - i - 1][n -  j - 1] = matrix[j][n - i - 1];
            matrix[j][n  - i - 1] = t;
        }
    }
}