leetcode54-螺旋矩阵

原题

给定一个包含 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,6,9,8,7,4,5]

解法

思想

拐点规律移动规律

  1. 当横坐标x等于纵坐标y+1时,且之前是向上移动的,拐点向右。
  2. 当横坐标x加纵坐标y等于列数减一,且之前是向右移动的,拐点向下。
  3. 当行数和横坐标x之差等于列数与纵坐标y之差时,且之前是向下移动的,拐点向左。
  4. 当横坐标x加纵坐标y等于行数减一,且之前是向左移动的,拐点向上。

当不满足上述拐点情况时,坐标会随着之前的运动方向继续运动。可以设置代表四个方向运动状态的布尔值来记录运动状态。

代码

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if(matrix==null) return null;
        int x = matrix.length;
        List<Integer> ret = new ArrayList<Integer>();
        if(x==0) return ret;
        int y = matrix[0].length;//获取二维数组的行数和列数,排除null和空情况。

        int x_now=0,y_now=0;
        int size = x*y;
        //代表向各个方向移动的布尔值。
        boolean toRight=true,toLeft=false,toTop=false,toBottom=false;

        for(int i=0;i<size;i++) {
            ret.add(matrix[x_now][y_now]);
            if(x_now==y_now+1&&toTop) {//拐向右
                toRight=true;
                toTop=false;
            }else if(y_now==y-x_now-1&&toRight) {//拐向下
                toBottom=true;
                toRight=false;
            }else if(x-x_now==y-y_now&&toBottom){//拐向左
                toLeft=true;
                toBottom=false;
            }else if(x_now==x-y_now-1&&toLeft) {//拐向上
                toTop=true;
                toLeft=false;
            }
            //移动坐标
            if(toRight) y_now++;
            if(toLeft) y_now--;
            if(toTop) x_now--;
            if(toBottom) x_now++;
        }
        return ret;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode54-%e8%9e%ba%e6%97%8b%e7%9f%a9%e9%98%b5/

发表回复

登录后才能评论