leetcode498-对角线遍历

这是一个Z字形编排问题,JEPG的编码过程中也会用到。

原题

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

示例:

输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ] ] 输出: [1,2,4,7,5,3,6,8,9] 解释:
leetcode498-对角线遍历

说明:

  1. 给定矩阵中的元素总数不会超过 100000 。

解法

思想

找拐点的规律:

  1. 当横坐标x为0,纵坐标y是偶数,且y不是最后一列的时候,拐点向右。
  2. 当横坐标x为最后一行,若行数为偶数且纵坐标y为奇数或行数为奇数但纵坐标y为偶数时,拐点向右。
  3. 当纵坐标y为0,横坐标x是奇数,且x不是最后一行的时候,拐点向下。
  4. 当纵坐标y为最后一列,若列数为偶数且横坐标x为偶数或列数为奇数但横坐标x为奇数时,拐点向右。
  5. 其他情况,当横坐标x为偶数且纵坐标y为奇数或x为奇数且y为偶数的时候,拐点向左下
  6. 当横坐标x为偶数且纵坐标y为偶数或x为奇数且y为奇数的时候,拐点向右上

代码

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        //获取二维数组的长宽、大小
        int x = matrix.length;
        if(x == 0) return new int[0];
        int y = matrix[0].length;
        int size = x*y;

        int x_now=0,y_now=0;//落点位置
        int[] ret = new int[size];//用于存储并返回的一维数组
        int i = 0;
        while( x_now < x && y_now < y ){
            ret[i] = matrix[x_now][y_now]; //存入元素
            i++;
            if((x_now==0&&y_now%2==0&&y_now!=y-1)||(x_now == x-1&&(y_now+x)%2==0)){//向右
                y_now += 1;
            }else if((y_now==0&&x_now%2==1&&x_now!=x-1)||(y_now == y-1&&(x_now+y)%2==1)){//向下
                x_now += 1;
            }
            else if((x_now+y_now)%2==0){//向右上
                y_now +=1;
                x_now -=1;
            }else if((x_now+y_now)%2==1){//向左下
                y_now -=1;
                x_now +=1;
            }
        }
        return ret;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode498-%e5%af%b9%e8%a7%92%e7%ba%bf%e9%81%8d%e5%8e%86/

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

相关推荐

  • leetcode160-相交链表

    原题 编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入: intersectVal = 8, listA = [4,1,…

    2019年12月14日
    090
  • leetcode1-两数之和

    原题 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能…

    算法 2019年12月20日
    090
  • 剑指offer64-求1+2+…+n

    原题(来源Leetcode) 求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 示例1…

    算法 2020年6月2日
    0550
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0120
  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输…

    算法 2020年5月23日
    0170
  • leetcode542-01矩阵

    原题 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 示例1: 输入: 0 0 0 0 1 0 0 0 0 输出: 0 0 …

    2019年12月13日
    080
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0710
  • leetcode205-同构字符串

    原题 给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。 所有出现的字符都必须用另一个字符替换,同时保留字符的顺…

    算法 2019年12月21日
    0220
  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明: 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3…

    算法 2020年5月24日
    0310
  • leetcode131-分割回文串

    原题 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], …

    算法 2020年5月22日
    0100

发表回复

登录后才能评论