旋转图像

题目地址：https://leetcode-cn.com/problems/rotate-image/

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

说明：

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定 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]
]

四指针

这一题与前面写到的旋转数组一题相似，之前是一维的，现在相当于是二维版。同样是两种思路一种是直接设置值到最终的地方，被覆盖的值先用备份变量拿出来再往它的目的地去设。第二种就是反转的思路。

旋转上图过程

1
2
3
4
5
6
7
8
9
10
11
12
13
(1) 
backup = m[0][1]
m[0][1] = m[0][0]
(2)
temp = backup
backup = m[1][1]
m[1][1] = temp
(3)
temp = backup
backup = m[1][0]
m[1][0] = temp
(4)
m[0][0] = backup

由于是2×2所以一次旋转设值完事，如果是3×3

和之前那一题还是有点差别，这边设置值的传递固定是四个完成一组，然后需要判断一圈有多少组

1
2
3
1×1 0组
2×2 1组
3×3 2组

四次设置值是一个单元操作，之后指针变动第一个指针是水平向右移动，第二个指针是垂直向下其他依次，直到头length-1。那么外循环条件是有几圈２×２，３×３都只有一圈，４×４与５×５是两圈。也就是length/2圈，内循环为每圈要移动多少组数字它取决于终点索引，并且每往内一圈length都会少２两边都会靠近1格。

  • 外圈（第一圈）起点matrix[0][0] 终点matrix[0][2] 有三组
  • 内圈（第二圈）起点matrix[1][1] 终点matrix[1][1] 只有一组

也就是当外循环完毕内循环的起点是和外循环相同，也就是j = i然后j在往后递增直到终点，终点会往内圈慢慢递减

我们这里只看首指针的变化，其他一样推总结在代码里

  • 第一圈从[0][0]--->[0][4]　5组
  • 第二圈从[1][1]--->[1][3]　3组
  • 第三圈就[2][2]　1组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void rotate(int[][] matrix) {
	int n = matrix.length;
    int s = n;
    for (int i = 0; i < n/2; i++,s--) {
    	for (int j = i; j < s-1; j++) {
          
        	int backup = matrix[j][n-i-1];
            matrix[j][n-i-1] = matrix[i][j];
            
            int temp = matrix[n-i-1][n-j-1];
            matrix[n-i-1][n-j-1] = backup;
            backup = temp;
            
            temp = matrix[n-j-1][i];
            matrix[n-j-1][i] = backup;
   			backup = temp;
            
            matrix[i][j] = backup;
        }
    }
}

总体实现了这样一个主线，但就是我们去存将被覆盖的值其实不需要另外添加一个变量backup我们可以直接把它存在首指针的地方，那个地方到最后才被设值中途是啥都没有关系我们就暂时用它存（空间已经存在了不用白不用）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void rotate(int[][] matrix) {
	int n = matrix.length;
    int s = n;
    for (int i = 0; i < n/2; i++,s--) {
    	for (int j = i; j < s-1; j++) {
            
            int temp =　matrix[i][j]
        	matrix[i][j] = matrix[j][n-i-1];
            matrix[j][n-i-1] = temp;
            
            temp = matrix[n-i-1][n-j-1];
            matrix[n-i-1][n-j-1] = matrix[i][j];
            matrix[i][j] = temp;
            
            temp = matrix[n-j-1][i];
            matrix[n-j-1][i] = matrix[i][j];
   			matrix[i][j] = temp;
 
        }
    }
}

两次反转

第二种方式就反转和旋转数组一题一样我们直接观察输入图与目标图通过怎样的变换可以得到

旋转90度的关系肯定是没有直接方式的，这里我们肯定是用到的设值。通过图形变换反转类似的方式就两数交换完成就可能进行几组反转比起上面直接的一步的到位的设值方式在单元操作上两数交换比起四数看起来简一点。但有进行多组遍历的可能。它是转90而不是180如果是180就上下反转然后左右反转。所以这里只能对角反转加左右反转先后无所谓

无论怎么转都可以实现总之是通过两个数的交换就很简单，然后要进行两次。下面代码按照第一条进行，第一个变换只需要遍历左上一半即可每个完成和下面的交换即可因此列的起点是递增的j = i，第二个变换循环时列只需要左边一半就换行所以j = length/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tmp = matrix[j][i];
            matrix[j][i] = matrix[i][j];
            matrix[i][j] = tmp;
        }
    }
   
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = tmp;
        }
    }
}

总结

总体来说都是一个原地算法，时间也都是Ｏ(n^2)，像这一题与之前一题都是属于数组内原地的变化位置即多值交换以及换成多组反转即两值交换的组合。主要也是体会在数组这样的数据结构当中我们可以有的算法思想：遍历、逆序、原地交换、快慢指针。万变不离其中，那么从更新《LeetCode日常》系列开始到这篇为止LeetCode初级算法合集中的数组篇章完结即将开启下一篇章字符串相关算法