算法每日一练 (6)

💢欢迎来到张胤尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

文章目录

算法每日一练 (6)
- 旋转图像
- - 题目描述
  - 解题思路
  - 解题代码
  - - `c/c++`
    - `golang`
    - `lua`

官方站点：力扣 Leetcode

算法每日一练 (6)

旋转图像

题目地址：旋转图像

题目描述

给定一个 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

解题思路

首先根据题意进行边界条件的判断，当 n * n 的二维矩阵中只有一个元素时，不需要任何处理，直接返回即刻。
从旋转角度出发，观察现象，将一个矩阵分为四部分：
- 顶部位置
- 右侧位置
- 底部位置
- 左侧位置
根据以上划分的四部分， n 阶矩阵旋转的逻辑就是：左侧位置 -> 顶部位置、底部位置 -> 左侧位置、右侧位置 -> 底部位置、顶部位置 -> 右侧位置。
再次观察矩阵的特点，将矩阵的旋转想象成每一圈的旋转，从外层圈再到内层圈的旋转。另外如果是奇数阶矩阵，最内层就不再需要旋转，因为只剩下一个元素。
在每一圈中根据顶部位置坐标分别计算出：右侧位置、底部位置、左侧位置的坐标。
接下来，坐标计算公式如下所示：
- 顶部位置：
  $i ， j （由循环变量进行控制顶部元素）$
- 右侧位置：
  $(顶部元素的列值)\\ y1 = n - i - 1 (控制列数，其中n表示矩阵的阶数，随着行数的增加，目标列在减小)$
- 底部位置：
  $x 2 = y 1 (右侧元素的列值)$
  对于底部元素的列值需要分成三部分讨论：
  - 对角线位置
    $y 2 = x 2 (当前元素位于对角线，那么行、列相等)$
  - 中值位置
    $y 2 = x 1 (当是奇数阶矩阵并且位于中值位置时，列值就是对应顶部元素的列值)$
  - 其他位置
    $y 2 = n - j + 1 (控制列数，其中 n 表示矩阵的阶数，随着列数的增大，目标列在减小)$
- 左侧位置：

$y2(底部元素的列值)\\ y3 = i(顶部元素的行值)$

另外，由于题目要求不能借助任何辅助容器，需要在原数组中进行处理，在迭代中只需要借助一个变量，保存 ”顶部位置“ 的值即可。
最后根据上面移动的顺序，进行依次进行覆盖。

根据以上的解题思路，下面以 3 * 3 二维矩阵为例：

在这里插入图片描述

$(0,0)=>(0,2)=>(2，2)=>(2，0)\\ (0,1)=>(1,2)=>(2，1)=>(1，0)$

下面再以 4 * 4 二维矩阵为例：

在这里插入图片描述

$\\ (0,1)=>(1,3)=>(3,1)=>(1,0) \\ (0,2)=>(2,3)=>(3,1)=>(1,0) \\ (1,1)=>(1,2)=>(2,2)=>(2,1)$

解题代码

`c/c++`

#include <vector>class Solution
{
public:void rotate(std::vector<std::vector<int>> &matrix){int n = matrix.size();if (n == 1)return;int f = n & 1;int c = n >> 1;for (int i = 0; i < c; i++){for (int j = i; j < n - i - 1; j++){int top = matrix[i][j];// 右侧坐标int x1 = j;int y1 = n - i - 1;// 底部坐标int x2 = y1;int y2;if (i == j)y2 = x2;else if (f && j == c)y2 = j;elsey2 = n - j - 1;// 左侧坐标int x3 = y2;int y3 = i;// 左侧移动到顶部matrix[i][j] = matrix[x3][y3];// 底部移动到左侧matrix[x3][y3] = matrix[x2][y2];// 右侧移动到底部matrix[x2][y2] = matrix[x1][y1];// 顶部移动到右侧matrix[x1][y1] = top;}}}
};

`golang`

package mainfunc rotate(matrix [][]int) {n := len(matrix)if n == 1 {return}f := n & 1c := n >> 1for i := 0; i < c; i++ {for j := i; j < n-i-1; j++ {top := matrix[i][j]// 右侧坐标x1, y1 := j, n-i-1// 底部坐标x2 := y1var y2 intif i == j {y2 = x2} else if f != 0 && j == c {y2 = j} else {y2 = n - j - 1}// 左侧坐标x3, y3 := y2, i// 左侧移动到顶部matrix[i][j] = matrix[x3][y3]// 底部移动到左侧matrix[x3][y3] = matrix[x2][y2]// 右侧移动到底部matrix[x2][y2] = matrix[x1][y1]// 顶部移动到右侧matrix[x1][y1] = top}}
}

`lua`

local function rotate(matrix)local n = #matrixif n == 1 thenreturnendlocal f, c = n & 1, n >> 1for i = 1, c dofor j = i, (n - i) dolocal top = matrix[i][j]-- 右侧坐标local x1, y1 = j, n - i + 1-- 底部坐标local x2 = y1local y2if i == j theny2 = x2elseif f ~= 0 and j + 1 == c theny2 = jelsey2 = n - j + 1end-- 左侧坐标local x3, y3 = y2, i-- 左侧移动到顶部matrix[i][j] = matrix[x3][y3]-- 底部移动到左侧matrix[x3][y3] = matrix[x2][y2]-- 右侧移动到底部matrix[x2][y2] = matrix[x1][y1]-- 顶部移动到右侧matrix[x1][y1] = topendend
end