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/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年11月14日
下一篇 2019年11月18日

相关推荐

  • leetcode752-打开转盘锁

    原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由…

    2019年12月9日
    0290
  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0350
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0130
  • leetcode1103-分糖果II

    原题 排排坐,分糖果。 我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类…

    算法 2020年3月5日
    0140
  • leetcode34--在排序数组中查找元素的第一个和最后一个位置

    原题 给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数…

    算法 2020年1月3日
    0160
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode122-买卖股票的最佳时机II

    原题 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意: 你不能同…

    算法 2020年2月7日
    080
  • leetcode92-反转链表

    原题 https://leetcode.cn/problems/reverse-linked-list-ii/description 题解 头插法 /** * Definition…

    算法 2024年3月28日
    060
  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外,这个整数不会以…

    算法 2019年11月14日
    0140

发表回复

登录后才能评论