[LintCode] Matrix Zigzag Traversal

cncoder 发布于2019-08-14 15:21 / 2801人阅读

摘要：注意两点两个循环必须是先走斜上的循环，再走斜下的循环两个循环之后的平移操作，有着严格的相对顺序斜上之后的平移，先考虑右移，再考虑下移斜下之后的平移，先考虑下移，再考虑右移。

Problem

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

Example

Given a matrix:

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

return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]

Note

Z字形走法，从左下到右上，右移或下移一位，再从右上到左下，下移或右移一位，如此往复。
注意两点：

两个while循环必须是先走斜上的循环，再走斜下的循环；

两个while循环之后的平移操作，有着严格的相对顺序：斜上之后的平移，先考虑右移，再考虑下移；斜下之后的平移，先考虑下移，再考虑右移。

Solution

public class Solution {
    public int[] printZMatrix(int[][] matrix) {
        if (matrix == null) return null;
        int m = matrix.length, n = matrix[0].length, count = m * n;
        int[] res = new int[count];
        res[0] = matrix[0][0];
        int i = 1, r = 0, c = 0;
        while (i < count) {
            while (r-1 >= 0 && c+1 < n) res[i++] = matrix[--r][++c];
            if (c+1 < n) res[i++] = matrix[r][++c];
            else if (r+1 < m) res[i++] = matrix[++r][c];
            while (r+1 < m && c-1 >= 0) res[i++] = matrix[++r][--c];
            if (r+1 < m) res[i++] = matrix[++r][c];
            else if (c+1 < n) res[i++] = matrix[r][++c];
        }
        return res;
    }
}

云服务器 GPU云服务器 Zigzag Traversal Matrix LintCode

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

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

[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 评论0 收藏0
[Leetcode] Binary Tree Traversal 二叉树遍历

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路用迭代法做深度优先搜索的技巧就是使用一个显式声明的存储遍历到节点，替代递归中的进程栈，实际上空间复杂度还是一样的。对于先序遍历，我们出栈顶节点，记录它的值，然后将它的左右子节点入栈，以此类推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

RaoMeng 2019-08-14 12:25 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
【LC总结】Iterator题目<Zigzag 1&2><BST>&

摘要：方法直接查找数组的位的迭代器，调用方法得到的整数即为要返回的元素。再写迭代器的方法返回指针元素的并让指针通过递归方法指向下一个元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...

WelliJhon 2019-08-14 15:49 评论0 收藏0
[LintCode/LeetCode] Binary Tree InOrder Traversal

摘要：递归法不说了，栈迭代的函数是利用的原理，从根节点到最底层的左子树，依次入堆栈。然后将出的结点值存入数组，并对出的结点的右子树用函数继续迭代。 Problem Given a binary tree, return the inorder traversal of its nodes values. Example Given binary tree {1,#,2,3}, 1 ...

tomorrowwu 2019-08-14 15:39 评论0 收藏0