当前位置：首页 > article >正文

算法每日一练 (6)

article 2025/2/28 12:09:08

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

文章目录

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