快捷導(dǎo)航

Java實(shí)現(xiàn)LeetCode（54.螺旋矩陣）

更新時間：2021年07月09日 09:51:19 作者：莫少俠9527

這篇文章主要介紹了Java實(shí)現(xiàn)LeetCode（螺旋矩陣）,本文列出題目和寫題的思路。給出完整的解法代碼,需要的朋友可以參考下

LeetCode54. 螺旋矩陣 java實(shí)現(xiàn)

題目

難度中
給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，返回矩陣中的所有元素。

示例 1:

輸入:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

輸出: [1,2,3,6,9,8,7,4,5]

示例 2:

輸入:

[

[1, 2, 3, 4],

[5, 6, 7, 8],

[9,10,11,12]

]

輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

思路

找出每個點(diǎn)的坐標(biāo)，每個點(diǎn)每次延順時針分別為右、下、左、上四個方向走一個位置，維護(hù)一個方向變量，不同方向時做相應(yīng)的邊界判斷。每次遇到邊界，必定改變方向，縮短原邊界大小。

解法

public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> order = new ArrayList<>();

        if (matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int len = m * n;
        int row = 0;
        int col = 0;
        int leftMin = 0;
        //每次走上下左右四個方向，一次只走一格
        //注意點(diǎn)，因?yàn)槭菑模?,1）開始走的，所以上界最小row是第二行1
        int topMin = 1;
        //初始方向值
        int k = 0;
        int[][] dir = {
                {1, 0, -1, 0},
                {0, 1, 0, -1}
        };
        for (int i = 0; i < len; i++) {
            order.add(matrix[row][col]);
            col += dir[0][k % 4];
            row += dir[1][k % 4];
            switch (k % 4) {
                case 0:
                    //右
                    if (col > n - 1) {
                        col = n - 1;
                        row++;
                        k++;
                        n--;
                    }
                    break;
                case 1:
                    //下
                    if (row > m - 1) {
                        row = m - 1;
                        col--;
                        k++;
                        m--;
                    }
                    break;
                case 2:
                    //左
                    if (col < leftMin) {
                        col = leftMin;
                        leftMin++;
                        row--;
                        k++;
                    }
                    break;
                case 3:
                    //上
                    if (row < topMin) {
                        row = topMin;

                            topMin++;

                        col++;
                        k++;
                    }
                    break;
            }


        }
        return order;
    }