Leetcode 498. Diagonal Traverse 練習

Difficulty : Medium
Java 演算法Algorithm

撰寫人KVJK_2125Fri, Mar 29, 2024 16:00

題目

說明 Description

原文：Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
翻譯：給一個 m x n 的矩陣mat，回一個以對角線遍歷，並包含該陣列所有元素的陣列。

範例 Example

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

限制條件 Constraints

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• -105 <= mat[i][j] <= 105

解題

思路 Intuition/Approach

以Example 1做解釋：

• Step1.
  先標注出xy軸：
  

  

• Step2.
  記下輸出時的xy順序以及走訪方向：
  - 第1次對角線走訪：右上 (0,0)
  - 第2次對角線走訪：左下 (0,1)(1,0)
  - 第3次對角線走訪：右上 (2,0)(1,1)(0,2)
  - 第4次對角線走訪：左下 (1,2)(2,1)
  - 第5次對角線走訪：右上 (2,2)
  

• Step3.
  發現在第3次時，x走訪順序為2 –> 1 –> 0 由大到小；
  而第2、4次時，x走訪順序為0 –> 1 –> 2 由小到大。
  建立一個計次變數count = 1，在奇數次數時，反轉陣列再儲存。

• Step4.
  要創建兩個ArrayList：
  一個用作走訪對角線，並進行判斷反轉；
  一個用作儲存可輸出的結果。

• Step5.
  因為Step3.的'拿取後反轉'，可統一走訪方式為'右上至左下'。
  及每次走訪路線均為(++, --)。

• Step6.
  建立int x = 0以及int y = 0：
  x會累加至row走訪完，
  y會計算至col走訪完。
  建立int i = x以及int j = y在走訪迴圈內：
  用於計算被統一的走訪方式，寫作i++以及j--。
  當 y > col時，即 x不會再出現0，
  於是x++，且y = col並繼續。直到x >= row且y >= col。

程式碼 Code（加註解）

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        ArrayList<Integer> list = new ArrayList<>();    //用來存放最後結果的陣列
        int row = mat.length-1; //row
        int col = mat[0].length-1;  //col
        int x = 0, y = 0, count = 1;
        while(x<=row && y<=col){
            int i = x;
            int j = y;
            //在迴圈內建立一個新的ArrayList，在新一輪的xy中，用來遇到x為0時reverse
            ArrayList<Integer> get = new ArrayList<>();
            while(i>=0 && i<=row && j>=0){
                get.add(mat[i][j]); //加入陣列
                //向左上移動
                i++;    //向右
                j--;    //向上
            }
            //如果是在第奇數次數走訪，則反轉該次陣列
            if(count%2 != 0){
                Collections.reverse(get);
            }
            
            list.addAll(get);
            count++;    //次數++
            y++;    
            //在y大於col時，表示x不會再是0
            if(y>col){
                x++;    //x必須+1
                y = col;    //y最大就是col
            }
        }
        //沒有在Leetcode、沒有另外用class，可以用這個直接輸出
        //System.out.println(list);
        
        //Leetcode因為另外用了class，所以必須return相同型態的變數
        //建立一個與一開始傳入的陣列相同的變數，並以該陣列回傳
        int [] ans = new int[(row+1)*(col+1)];
        int size = 0;
        for(int i: list){
            ans[size++] = i;
        }
        //System.out.println("the output about that mat do Diagonal Traverse : \n" + ans) ;
        return ans;
    }
}