[LintCode] Spiral Matrix I & Spiral Matrix II

tuantuan 发布于2019-08-14 15:19 / 2358人阅读

摘要：如果不在前两个循环之后的话，那么那多余的一行或一列就会被加入数组两次，造成错误的结果。解法和一样，只是简化了，甚至可以用一样的方法去做，只要把也换成。使用，以及最后讨论是否为奇数以判断中间是否有一个未循环的点，是这道题的两个有趣的地方。

Spiral Matrix I Problem

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

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].

Note

解法很形象，先从左上角开始，从左向右添加第一行的元素，然后到了右上角，从最后一列从上到下，到了右下角，在最后一行从右到左，到了左下角，从第一列从下到上，如此循环。每一圈循环count加一，直到count到了最中间的一行或者最中间的一列，只需进行从左到右或从上到下的操作，然后break。
为什么要break？这样做的理由其实很简单，不论行数m还是列数n更大，最后一个循环发生在count*2 == m or n的时候，此时一定只剩下一行或一列要走。也就是说，四个for循环，只走一次。如果不在前两个for循环之后break的话，那么那多余的一行或一列就会被加入res数组两次，造成错误的结果。
要注意，在第一次之后的for循环要避开之前遍历过的点。

Solution

public class Solution {
    public List spiralOrder(int[][] matrix) {
        List res = new ArrayList ();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;
        int m = matrix.length;
        int n = matrix[0].length;
        int count = 0;
        while (2*count < m && 2*count < n) {
            for (int i = count; i <= n-1-count; i++) {
                res.add(matrix[count][i]);
            }
            for (int i = count+1; i <= m-1-count; i++) {
                res.add(matrix[i][n-1-count]);
            }
            if (2*count+1 == m || 2*count+1 == n) break;
            for (int i = n-2-count; i >= count; i--) {
                res.add(matrix[m-1-count][i]);
            }
            for (int i = m-2-count; i >= count+1; i--) {
                res.add(matrix[i][count]);
            }
            count++;
        }
        return res;
    }
}

Spiral Matrix II Problem

Given an integer n, generate a square matrix filled with elements from 1 to n^2 in spiral order.

Example

Given n = 3,

You should return the following matrix:

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

Note

解法和Spiral Matrix I一样，只是简化了，甚至可以用一样的方法去做，只要把m也换成n。
使用num++，以及最后讨论n是否为奇数以判断中间是否有一个未循环的点，是这道题的两个有趣的地方。

Solution

public class Solution {
    public int[][] generateMatrix(int n) {
        int num = 1;
        int[][] res = new int[n][n];
        for (int cur = 0; cur < n/2; cur++) {
            for (int j = cur; j < n-1-cur; j++) {
                res[cur][j] = num++;
            }
            for (int i = cur; i < n-1-cur; i++) {
                res[i][n-1-cur] = num++;
            }
            for (int j = n-1-cur; j > cur; j--) {
                res[n-1-cur][j] = num++;
            }
            for (int i = n-1-cur; i > cur; i--) {
                res[i][cur] = num++;
            }
        }
        if (n % 2 != 0) res[n/2][n/2] = num;
        return res;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65613.html

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
[Leetcode] Spiral Matrix 螺旋矩阵

摘要：代码添加该圈第一行添加最后一列添加最后一行添加第一列如果是奇数，加上中间那个点后续如果在中，给出的是和来代表行数和列数，该如何解决和的本质区别就是一个是任意长方形，一个是正方形，所以中不需要判断最后一行或者最后一列。 Spiral Matrix I Given a matrix of m x n elements (m rows, n columns), return all ele...

waruqi 2019-08-14 12:42 评论0 收藏0
LeetCode[54] Spiral Matrix

摘要：复杂度思路注意循环条件。代码注意循环条件，要用而不是除以，因为精度准换问题只有一行或者一列的时候，就不要再继续搜索了 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
Leetcode 54:Spiral Matrix 螺旋矩阵

摘要：螺旋矩阵给定一个包含个元素的矩阵行列，请按照顺时针螺旋顺序，返回矩阵中的所有元素。每次转向或都会自减。循环可操作性很高，可以直接操作索引坐标改变遍历方式，不再赘述。 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 螺旋矩阵

摘要：螺旋矩阵给定一个包含个元素的矩阵行列，请按照顺时针螺旋顺序，返回矩阵中的所有元素。每次转向或都会自减。循环可操作性很高，可以直接操作索引坐标改变遍历方式，不再赘述。 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