算法每日一练 (6)

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

官方站点： 力扣 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（由循环变量进行控制顶部元素）$$

  • 右侧位置：
    $$\begin{gathered} x1=j(顶部元素的列值) \\ y1=n-i-1(控制列数，其中n表示矩阵的阶数，随着行数的增加，目标列在减小) \end{gathered}$$

  • 底部位置：
    $$x2=y1(右侧元素的列值)$$
    对于底部元素的列值需要分成三部分讨论：

    • 对角线位置
      $$y2=x2(当前元素位于对角线，那么行、列相等)$$
    • 中值位置
      $$y2=x1(当是奇数阶矩阵并且位于中值位置时，列值就是对应顶部元素的列值)$$
    • 其他位置
      $$y2=n-j+1(控制列数，其中n表示矩阵的阶数，随着列数的增大，目标列在减小)$$

  • 左侧位置：

$$\begin{gathered} x3=y2(底部元素的列值) \\ y3=i(顶部元素的行值) \end{gathered}$$

• 另外，由于题目要求不能借助任何辅助容器，需要在原数组中进行处理，在迭代中只需要借助一个变量，保存 ”顶部位置“ 的值即可。

• 最后根据上面移动的顺序，进行依次进行覆盖。

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

$$\begin{gathered} (0,0)=>(0,2)=>(2，2)=>(2，0) \\ (0,1)=>(1,2)=>(2，1)=>(1，0) \end{gathered}$$

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

$$\begin{gathered} (0,0)=>(0,3)=>(3,3)=>(3,0) \\ (0,1)=>(1,3)=>(3,1)=>(1,0) \\ (0,2)=>(2,3)=>(3,1)=>(1,0) \\ (1,1)=>(1,2)=>(2,2)=>(2,1) \end{gathered}$$

解题代码

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

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。