Leetcode - 498: traversée diagonale

Description du sujet

Pour vous donner une taille de m x n La matrice de mat ,S'il vous plaît, dans l'ordre Diagonal,Renvoie tous les éléments de cette matrice dans un tableau.

Exemple

Exemple 1：
Entrée：nums = [2,7,11,15], target = 9
Produits：[0,1]
Explication：Parce que nums[0] + nums[1] == 9 ,Retour [0, 1] .

Exemple 2：
Entrée：mat = [[1,2],[3,4]]
Produits：[1,2,3,4]

Processus de résolution des problèmes

Idées et étapes

（1）m * n Matrice bidimensionnelle de, En tout. m + n - 1 Diagonale, La diagonale adjacente traverse une direction différente;
（2）Que la diagonale soit numérotée de haut en bas comme [0,m + n − 2].Quand i Même nombre, La direction de traversée est de gauche en bas à droite en haut;Quand i Nombre impair,La direction de traversée est de droite en bas à gauche;
（3）Quand i Les diagonales sont parcourues du bas gauche vers le haut à droite, C'est - à - dire: i Même nombre, Chaque index de ligne moins 1, Index des colonnes plus 1, Jusqu'au bord de la matrice;
      Quand i < m Heure, Le point de départ de la traversée diagonale est (i, 0);
      Quand i ≥ m Heure,Le point de départ de la traversée diagonale est (m − 1, i − m + 1);
（4）Quand i  Les diagonales sont parcourues de droite en bas à gauche , C'est - à - dire: i Nombre impair,  Chaque index de ligne plus  1,  Index des colonnes moins  1, Jusqu'au bord de la matrice;
      Quand i < n Heure, Le point de départ de la traversée diagonale est (0, i);
      Quand i ≥ n Heure, Le point de départ de la traversée diagonale est  (i − n + 1, n − 1);

Affichage du Code

public class FindDiagonalOrder {
    

    /** * Réponse officielle： * m * n Matrice bidimensionnelle de, En tout. m + n - 1 Diagonale, La diagonale adjacente traverse une direction différente * Que la diagonale soit numérotée de haut en bas comme [0,m + n − 2] * Quand i Même nombre, La direction de traversée est de gauche en bas à droite en haut; * Quand i Nombre impair,La direction de traversée est de droite en bas à gauche; * * Quand i Les diagonales sont parcourues du bas gauche vers le haut à droite, C'est - à - dire: i Même nombre, Chaque index de ligne moins 1, Index des colonnes plus 1, Jusqu'au bord de la matrice; * Quand i < m Heure, Le point de départ de la traversée diagonale est (i, 0); * Quand i ≥ m Heure,Le point de départ de la traversée diagonale est (m − 1, i − m + 1); * * Quand i  Les diagonales sont parcourues de droite en bas à gauche , C'est - à - dire: i Nombre impair,  Chaque index de ligne plus  1,  Index des colonnes moins  1, Jusqu'au bord de la matrice; * Quand i < n Heure, Le point de départ de la traversée diagonale est (0, i); * Quand i ≥ n Heure, Le point de départ de la traversée diagonale est  (i − n + 1, n − 1); **/

    public int[] findDiagonalOrder(int[][] mat) {
    
        // D'accord
        int m = mat.length;
        // Colonnes
        int n = mat[0].length;
        int[] result = new int[m * n];
        int index = 0;
        for (int i = 0; i < m + n - 1; i++) {
    
            if (i % 2 == 0) {
    
                //  Nombre pair de diagonales 
                int row = 0;
                int line = 0;
                if (i < m) {
    
                    row = i;
                }
                if (i >= m) {
    
                    row = m - 1;
                    line = i - m + 1;
                }
                while (row >= 0 && line < n) {
    
                    result[index] = mat[row][line];
                    row--;
                    line++;
                    index++;
                }
            } else {
    
                //  Nombre impair de diagonales 
                int row = 0;
                int line = 0;
                if (i < n) {
    
                    line = i;
                }
                if (i >= n) {
    
                    row = i - n + 1;
                    line = n - 1;
                }
                while (row < m && line >= 0) {
    
                    result[index] = mat[row][line];
                    row++;
                    line--;
                    index++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
    
        int[][] mat = {
    {
    1,2,3},
                       {
    4,5,6},
                       {
    7,8,9}};
        int[] result = new FindDiagonalOrder().findDiagonalOrder(mat);
        for (int i = 0; i < result.length; i++) {
    
            System.out.printf("%2d", result[i]);
        }
        System.out.println();
    }

}