算法每日一练 (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;
                else
                    y2 = 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 main

func rotate(matrix [][]int) {

	n := len(matrix)
	if n == 1 {
		return
	}

	f := n & 1
	c := n >> 1

	for i := 0; i < c; i++ {
		for j := i; j < n-i-1; j++ {

			top := matrix[i][j]

			// 右侧坐标
			x1, y1 := j, n-i-1

			// 底部坐标
			x2 := y1
			var y2 int
			if 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 = #matrix
    if n == 1 then
        return
    end

    local f, c = n & 1, n >> 1

    for i = 1, c do
        for j = i, (n - i) do
            local top = matrix[i][j]

            -- 右侧坐标
            local x1, y1 = j, n - i + 1

            -- 底部坐标
            local x2 = y1
            local y2
            if i == j then
                y2 = x2
            elseif f ~= 0 and j + 1 == c then
                y2 = j
            else
                y2 = n - j + 1
            end

            -- 左侧坐标
            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] = top
        end
    end
end

🌺🌺🌺撒花！

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