[Leetcode] Spiral Matrix 螺旋矩陣

waruqi 發(fā)布于2019-08-14 12:42 / 3530人閱讀

摘要：代碼添加該圈第一行添加最后一列添加最后一行添加第一列如果是奇數，加上中間那個點后續(xù)如果在中，給出的是和來代表行數和列數，該如何解決和的本質區(qū)別就是一個是任意長方形，一個是正方形，所以中不需要判斷最后一行或者最后一列。

Spiral Matrix I

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example, Given the following matrix:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

順序添加法 復雜度

時間 O(NM) 空間 O(1)

思路

首先考慮最簡單的情況，如圖我們先找最外面這圈X，這種情況下我們是第一行找前4個，最后一列找前4個，最后一行找后4個，第一列找后4個，這里我們可以發(fā)現，第一行和最后一行，第一列和最后一列都是有對應關系的。即對i行，其對應行是m - i - 1，對于第j列，其對應的最后一列是n - j - 1。

XXXXX
XOOOX
XOOOX
XOOOX
XXXXX

然后進入到里面那一圈，同樣的順序沒什么問題，然而關鍵在于下圖這么兩種情況，一圈已經沒有四條邊了，所以我們要多帶帶處理，只加那唯一的一行或一列。另外，根據下圖我們可以發(fā)現，圈數是寬和高中較小的那個，加1再除以2。

OOOOO  OOO
OXXXO  OXO
OOOOO  OXO
       OXO
       OOO

代碼

public class Solution {
    public List spiralOrder(int[][] matrix) {
        List res = new LinkedList();
        if(matrix.length == 0) return res;
        int m = matrix.length, n = matrix[0].length;
        // 計算圈數
        int lvl = (Math.min(m, n) + 1) / 2;
        for(int i = 0; i < lvl; i++){
            // 計算相對應的該圈最后一行
            int lastRow = m - i - 1;
            // 計算相對應的該圈最后一列
            int lastCol = n - i - 1;
            // 如果該圈第一行就是最后一行，說明只剩下一行
            if(i == lastRow){
                for(int j = i; j <= lastCol; j++){
                    res.add(matrix[i][j]);
                }
            // 如果該圈第一列就是最后一列，說明只剩下一列
            } else if(i == lastCol){
                for(int j = i; j <= lastRow; j++){
                    res.add(matrix[j][i]);
                }
            } else {
                // 第一行
                for(int j = i; j < lastCol; j++){
                    res.add(matrix[i][j]);
                }
                // 最后一列
                for(int j = i; j < lastRow; j++){
                    res.add(matrix[j][lastCol]);
                }
                // 最后一行
                for(int j = lastCol; j > i; j--){
                    res.add(matrix[lastRow][j]);
                }
                // 第一列
                for(int j = lastRow; j > i; j--){
                    res.add(matrix[j][i]);
                }
            }
        }
        return res;
    }
}

2018/2

class Solution:
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if (matrix is None or len(matrix) == 0):
            return []
        rows = len(matrix)
        cols = len(matrix[0])
        level = (min(rows, cols) + 1) // 2
        result = []
        for currLevel in range(0, level):
            firstRow = currLevel
            firstCol = currLevel
            lastRow = rows - currLevel - 1
            lastCol = cols - currLevel - 1
            if firstRow == lastRow:
                for col in range(firstCol, lastCol + 1):
                    result.append(matrix[firstRow][col])
                return result
            if firstCol == lastCol:
                for row in range(firstRow, lastRow + 1):
                    result.append(matrix[row][firstRow])
                return result
            for col in range(firstCol, lastCol):
                result.append(matrix[firstRow][col])
            for row in range(firstRow, lastRow):
                result.append(matrix[row][lastCol])
            for col in range(lastCol, firstCol, -1):
                result.append(matrix[lastRow][col])
            for row in range(lastRow, firstRow, -1):
                result.append(matrix[row][firstCol])
        return result

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example, Given n = 3,
You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

順序添加法 復雜度

時間 O(NM) 空間 O(1)

思路

本題就是按照螺旋的順序把數字依次塞進去，我們可以維護上下左右邊界的四個變量，一圈一圈往里面添加。最后要注意的是，如果n是奇數，要把中心那個點算上。

代碼

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int left = 0, right = n - 1, bottom = n - 1, top = 0, num = 1;
        while(left < right && top < bottom){
            // 添加該圈第一行
            for(int i = left; i < right; i++){
                res[top][i] = num++;
            }
            // 添加最后一列
            for(int i = top; i < bottom; i++){
                res[i][right] = num++;
            }
            // 添加最后一行
            for(int i = right; i > left; i--){
                res[bottom][i] = num++;
            }
            // 添加第一列
            for(int i = bottom; i > top; i--){
                res[i][left] = num++;
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        // 如果是奇數，加上中間那個點
        if(n % 2 == 1){
            res[n / 2][n / 2] = num;
        }
        return res;
    }
}

2018/2

class Solution:
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if n == 0:
            return []
        matrix = [[0 for i in range(0, n)] for j in range(0, n)]
        left, right, top, bottom, num = 0, n - 1, 0, n - 1, 1
        while left < right and top < bottom:
            for col in range(left, right):
                matrix[top][col] = num
                num += 1
            for row in range(top, bottom):
                matrix[row][right] = num
                num += 1
            for col in range(right, left, -1):
                matrix[bottom][col] = num
                num += 1
            for row in range(bottom, top, -1):
                matrix[row][left] = num
                num += 1
            left += 1
            right -= 1
            top += 1
            bottom -= 1
        if n % 2 != 0:
            matrix[left][top] = num
        return matrix

后續(xù) Follow Up

如果在matrix ii中，給出的是m和n來代表行數和列數，該如何解決？

i和ii的本質區(qū)別就是一個是任意長方形，一個是正方形，所以ii中不需要判斷最后一行或者最后一列。既然沒有了正方形的前提，那生成矩陣的方法就和i是一樣的了。

class Solution:
    def generateMatrix(self, m, n):
        # m rows, n cols
        if m == 0 or n == 0:
            return []
        matrix = [[0 for i in range(0, n)] for j in range(0, m)]
        num = 1
        level = (min(m, n) + 1) // 2
        for currLevel in range(0, level):
            lastRow = m - currLevel - 1
            lastCol = n - currLevel - 1
            firstRow = currLevel
            firstCol = currLevel
            if firstRow == lastRow:
                for col in range(firstCol, lastCol + 1):
                    matrix[firstRow][col] = num
                    num += 1
                return matrix
            if firstCol == lastCol:
                for row in range(firstRow, lastRow + 1):
                    matrix[row][firstRow] = num
                    num += 1
                return matrix
            for col in range(firstCol, lastCol):
                matrix[firstRow][col] = num
                num += 1
            for row in range(firstRow, lastRow):
                matrix[row][lastCol] = num
                num += 1
            for col in range(lastCol, firstCol, -1):
                matrix[lastRow][col] = num
                num += 1
            for row in range(lastRow, firstRow, -1):
                matrix[row][firstCol] = num
                num += 1
        return matrix

GPU云服務器云服務器螺旋矩陣 Spiral Matrix modelview matrix

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64650.html

Leetcode 54:Spiral Matrix 螺旋矩陣

摘要：螺旋矩陣給定一個包含個元素的矩陣行列，請按照順時針螺旋順序，返回矩陣中的所有元素。每次轉向或都會自減。循環(huán)可操作性很高，可以直接操作索引坐標改變遍歷方式，不再贅述。 54:Spiral Matrix 螺旋矩陣 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix i...

venmos 2019-07-31 10:37 評論0 收藏0
Leetcode 54:Spiral Matrix 螺旋矩陣

摘要：螺旋矩陣給定一個包含個元素的矩陣行列，請按照順時針螺旋順序，返回矩陣中的所有元素。每次轉向或都會自減。循環(huán)可操作性很高，可以直接操作索引坐標改變遍歷方式，不再贅述。 54:Spiral Matrix 螺旋矩陣 Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix i...

mochixuan 2019-08-16 18:23 評論0 收藏0
LeetCode[54] Spiral Matrix

摘要：復雜度思路注意循環(huán)條件。代碼注意循環(huán)條件，要用而不是除以，因為精度準換問題只有一行或者一列的時候，就不要再繼續(xù)搜索了 LeetCode[54] Spiral Matrix Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. Fo...

YFan 2019-08-14 15:57 評論0 收藏0
leetcode59 Spiral Matrix II

摘要：題目要求也就是將遞加的數字按照順時針的順序依次填入數組之中這道題目聯系到，其實就相當好解決了。題目要求 Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return...

QLQ 2019-08-16 10:37 評論0 收藏0
leetcode54 Spiral Matrix

摘要：題目要求按照順時針方向旋轉訪問數組中的元素思路一按行遍歷，轉化為因為不允許跳躍插入，也就是說如果插入的大于的，就會報出。思路二利用順序插入為了避免類型轉化帶來的不必要的性能下降，最好直接利用順序插入，一次遍歷數組。題目要求 Given a matrix of m x n elements (m rows, n columns), return all elements of the ...

琛ｈ。 2019-08-16 10:37 評論0 收藏0