[LintCode] Matrix Zigzag Traversal

cncoder 發布于2019-08-14 15:21 / 2799人閱讀

摘要：注意兩點兩個循環必須是先走斜上的循環，再走斜下的循環兩個循環之后的平移操作，有著嚴格的相對順序斜上之后的平移，先考慮右移，再考慮下移斜下之后的平移，先考慮下移，再考慮右移。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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