螺旋矩阵 | LeetCode-59 | LeetCode-54 | 分类讨论

发表于 更新于 分类于 ， ， 阅读次数： 阅读次数： Waline： 本文字数： 4.8k 阅读时长 ≈ 8 分钟
分类不好，这道题就做不出来！
LeetCode链接：59. 螺旋矩阵 II
LeetCode链接：54. 螺旋矩阵

题目1：螺旋矩阵II

1.题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

img

1
2
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1
2
输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

2.题解

2.1 直接法-分类讨论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int[][] generateMatrix(int n) {
        // 创建一个 n x n 的矩阵，用于存放螺旋顺序的数字
        int[][] result = new int[n][n];
        // 计算需要填充螺旋圈的数量（当 n 为偶数时，正好填满；当 n 为奇数时，中间会剩余一个元素）
        int k = n / 2;
        // 初始化数字计数器，从 1 开始
        int count = 1;
        // 定义四个边界：上、下、左、右
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;

        // 循环处理每一层的螺旋圈
        for (int i = 0; i < k; i++) {
            // 从左到右填充当前顶部的一行
            for (int j = left; j < right; j++) result[top][j] = count++;
            // 从上到下填充当前右边的一列
            for (int j = top; j < bottom; j++) result[j][right] = count++;
            // 从右到左填充当前底部的一行
            for (int j = right; j > left; j--) result[bottom][j] = count++;
            // 从下到上填充当前左边的一列
            for (int j = bottom; j > top; j--) result[j][left] = count++;
            // 缩小边界，进入下一层螺旋圈
            left++;
            right--;
            top++;
            bottom--;
        }
        // 如果 n 是奇数，填充矩阵中心的最后一个元素
        if (n % 2 != 0) {
            result[left][top] = count;
        }
        // 返回填充好的螺旋矩阵
        return result;
    }
}

2.2 方法二-解决中心值忘记赋值问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int[][] generateMatrix(int n) {
        // 创建一个 n x n 的矩阵，用于存放螺旋顺序的数字
        int[][] result = new int[n][n];
        // 初始化数字计数器，从 1 开始
        int count = 1;
        // 目标值，表示填充到矩阵中的最大数字
        int target = n * n;
        // 定义四个边界：上、下、左、右
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;

        // 开始填充矩阵，直到填满目标值
        while (count <= target) {
            // 从左到右填充当前顶部的一行
            for (int i = left; i <= right; i++) result[top][i] = count++;
            // 填充完一行后，移动上边界下移一行
            top++;
            // 从上到下填充当前右边的一列
            for (int i = top; i <= bottom; i++) result[i][right] = count++;
            // 填充完一列后，移动右边界左移一列
            right--;
            // 从右到左填充当前底部的一行
            for (int i = right; i >= left; i--) result[bottom][i] = count++;
            // 填充完一行后，移动下边界上移一行
            bottom--;
            // 从下到上填充当前左边的一列
            for (int i = bottom; i >= top; i--) result[i][left] = count++;
            // 填充完一列后，移动左边界右移一列
            left++;
        }
        // 返回填充好的螺旋矩阵
        return result;
    }
}

2.3 方法3-通解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int[][] generateMatrix(int n) {
        // 创建一个 n x n 的矩阵用于存储结果
        int[][] result = new int[n][n];
        // 初始化从 1 开始的计数器
        int count = 1;
        // 目标计数为 n*n，表示矩阵中应有的最大值
        int target = n * n;
        // 定义四个边界：上(top)、下(bottom)、左(left)、右(right)
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;

        // 循环继续，直到所有的边界都相交
        while (left <= right && top <= bottom) {
            // 从左到右填充矩阵的上边界
            for (int i = left; i <= right; i++) result[top][i] = count++;
            // 从上到下填充矩阵的右边界
            for (int i = top + 1; i <= bottom; i++) result[i][right] = count++;
            
            // 确保矩阵中至少有两行两列，然后填充底边和左边
            if (left < right && top < bottom) {
                // 从右到左填充矩阵的下边界
                for (int i = right - 1; i > left; i--) result[bottom][i] = count++;
                // 从下到上填充矩阵的左边界
                for (int i = bottom; i > top; i--) result[i][left] = count++;
            }
            
            // 调整边界，以缩小矩阵范围
            bottom--;
            right--;
            top++;
            left++;
        }

        // 返回生成的螺旋矩阵
        return result;
    }
}

题目2：螺旋矩阵

1.题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

img

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

img

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

2.题解

2.1 方法1-通解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 创建一个列表用于存储结果
        List<Integer> result = new ArrayList<>();
        // 获取矩阵的行数和列数
        int m = matrix.length;
        int n = matrix[0].length;
        // 定义四个边界：左(left)、右(right)、上(top)、下(bottom)
        int left = 0, right = n - 1;
        int top = 0, bottom = m - 1;
        // 循环执行，直到所有边界重合
        while (left <= right && top <= bottom) {
            // 从左到右填充矩阵的上边界
            for (int i = left; i <= right; i++) result.add(matrix[top][i]);
            // 从上到下填充矩阵的右边界
            for (int i = top + 1; i <= bottom; i++) result.add(matrix[i][right]);
            
            // 确保矩阵中至少有两行两列，然后填充底边和左边
            if (left < right && top < bottom) {
                // 从右到左填充矩阵的下边界
                for (int i = right - 1; i > left; i--) result.add(matrix[bottom][i]);
                // 从下到上填充矩阵的左边界
                for (int i = bottom; i > top; i--) result.add(matrix[i][left]);
            }
            
            // 调整边界，以缩小矩阵范围
            bottom--;  // 下边界上移
            right--;   // 右边界左移
            top++;     // 上边界下移
            left++;    // 左边界右移
        }

        // 返回最终的结果列表
        return result;
    }
}

2.2 方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 创建一个列表用于存储结果
        List<Integer> result = new ArrayList<>();

        // 获取矩阵的行数和列数
        int m = matrix.length;
        int n = matrix[0].length;

        // 定义四个边界：左(left)、右(right)、上(top)、下(bottom)
        int left = 0, right = n - 1;
        int top = 0, bottom = m - 1;

        // 循环执行
        while (left <= right && top <= bottom) {
            // 从左到右遍历矩阵的上边界，并将元素加入结果列表
            for (int i = left; i <= right; i++) result.add(matrix[top][i]);

            // 将上边界下移，如果上边界超过下边界，跳出循环
            if (++top > bottom) break;

            // 从上到下遍历矩阵的右边界，并将元素加入结果列表
            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            // 将右边界左移，如果左边界超过右边界，跳出循环
            if (left > --right) break;

            // 从右到左遍历矩阵的下边界，并将元素加入结果列表
            for (int i = right; i >= left; i--) result.add(matrix[bottom][i]);
            // 将下边界上移，如果上边界超过下边界，跳出循环
            if (top > --bottom) break;

            // 从下到上遍历矩阵的左边界，并将元素加入结果列表
            for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);     
            // 将左边界右移，如果左边界超过右边界，跳出循环
            if (++left > right) break;
        }

        // 返回最终的结果列表
        return result;
    }
}
-------------本文结束感谢您的阅读-------------