54.螺旋矩阵

LeetCode LeetCode 数组分治动态规划

发布时间 : 2000-01-10 00:05

字数:1.2k 阅读 :

评论:

54.螺旋矩阵

54.螺旋矩阵

54.1 题目

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

示例 1：

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

示例 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

54.2 题解

逐层模拟

// 方法一：逐层模拟
// 把矩阵看做是由n层矩形构成的，我们可以一层一层的按顺时针打印他们，直到把最内层打印完毕。
// 就是一圈一圈打印，逐渐缩小圈，直至最内圈打印完
static IList<int> SpiralOrder1(int[][] matrix)
{
    // 检查输入矩阵是否为空或维度为零，如果是，则返回空列表
    if (matrix == null || matrix.GetLength(0) == 0 || matrix[0].Length == 0)
        return new List<int>();

    // 获取矩阵的行数和列数
    int rows = matrix.GetLength(0);
    int cols = matrix[0].Length;

    // 初始化边界指示器
    int top = 0;
    int bottom = rows - 1;
    int left = 0;
    int right = cols - 1;

    // 用于存储结果的列表
    List<int> result = new List<int>();

    // 循环遍历矩阵，按螺旋顺序添加元素到结果列表
    while (top <= bottom && left <= right)
    {
        // 从左到右遍历并添加元素到结果列表
        for (int col = left; col <= right; col++)
        {
            result.Add(matrix[top][col]);
        }

        // 从上到下遍历并添加元素到结果列表
        for (int row = top + 1; row <= bottom; row++)
        {
            result.Add(matrix[row][right]);
        }

        // 检查是否有足够的行和列使得可以从右到左遍历
        if (left < right && top < bottom)
        {
            // 从右到左遍历并添加元素到结果列表
            for (int col = right - 1; col >= left; col--)
            {
                result.Add(matrix[bottom][col]);
            }

            // 从下到上遍历并添加元素到结果列表
            for (int row = bottom - 1; row > top; row--)
            {
                result.Add(matrix[row][left]);
            }
        }

        // 更新边界指示器，缩小螺旋范围
        top++;
        bottom--;
        left++;
        right--;
    }

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

54.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

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

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

        // 示例 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

        #endregion

        #region 测试

        // 示例 1
        int[][] matrix1 = new int[][]
        {
            new int[] { 1, 2, 3 },
            new int[] { 4, 5, 6 },
            new int[] { 7, 8, 9 }
        };
        IList<int> result1 = SpiralOrder1(matrix1);
        Console.WriteLine($"示例1 方法1 输出：{string.Join(", ", result1)}");

        // 示例 2
        int[][] matrix2 = new int[][]
        {
            new int[] { 1, 2, 3, 4 },
            new int[] { 5, 6, 7, 8 },
            new int[] { 9, 10, 11, 12 }
        };
        IList<int> result2 = SpiralOrder1(matrix2);
        Console.WriteLine($"示例2 方法1 输出：{string.Join(", ", result2)}");

        #endregion
    }

    #region 答案

    // 方法一：逐层模拟
    // 把矩阵看做是由n层矩形构成的，我们可以一层一层的按顺时针打印他们，直到把最内层打印完毕。
    // 就是一圈一圈打印，逐渐缩小圈，直至最内圈打印完
    static IList<int> SpiralOrder1(int[][] matrix)
    {
        // 检查输入矩阵是否为空或维度为零，如果是，则返回空列表
        if (matrix == null || matrix.GetLength(0) == 0 || matrix[0].Length == 0)
            return new List<int>();

        // 获取矩阵的行数和列数
        int rows = matrix.GetLength(0);
        int cols = matrix[0].Length;

        // 初始化边界指示器
        int top = 0;
        int bottom = rows - 1;
        int left = 0;
        int right = cols - 1;

        // 用于存储结果的列表
        List<int> result = new List<int>();

        // 循环遍历矩阵，按螺旋顺序添加元素到结果列表
        while (top <= bottom && left <= right)
        {
            // 从左到右遍历并添加元素到结果列表
            for (int col = left; col <= right; col++)
            {
                result.Add(matrix[top][col]);
            }

            // 从上到下遍历并添加元素到结果列表
            for (int row = top + 1; row <= bottom; row++)
            {
                result.Add(matrix[row][right]);
            }

            // 检查是否有足够的行和列使得可以从右到左遍历
            if (left < right && top < bottom)
            {
                // 从右到左遍历并添加元素到结果列表
                for (int col = right - 1; col >= left; col--)
                {
                    result.Add(matrix[bottom][col]);
                }

                // 从下到上遍历并添加元素到结果列表
                for (int row = bottom - 1; row > top; row--)
                {
                    result.Add(matrix[row][left]);
                }
            }

            // 更新边界指示器，缩小螺旋范围
            top++;
            bottom--;
            left++;
            right--;
        }

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

    #endregion
}

54.4 运行结果

示例1 方法1 输出：1, 2, 3, 6, 9, 8, 7, 4, 5
示例2 方法1 输出：1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com