[クラシックアルゴリズム]時計回りの印刷マトリクスを優雅に実現


詳細
Googleの面接で質問されたのを覚えています.時計回りの印刷マトリクスの問題の説明について、みんなは次のテーマを検索することができて、大まかな情報は以下の通りです:1、2*2マトリクスのようなすべての要素を印刷するまで外層から時計回りに印刷することを要求して、   1 2    3 4出力:1 2 4 3 2、3*4マトリクス   1 2 3 4    5 6 7 8    9 1 2 3出力:1 2 3 4 8 3 2 1 9 5 6 7一見、この問題は簡単で、特に面接では、最も速いスピードでコードを書くことを目標に、直接4つのforで手書きコードを循環します.しかし、書く過程で、注意しなければならない境界問題が多いことに気づいたが、最後にはつまずいて書き終わった.その後は考えず、最近偶然ネット上の解法を見て、もっと優雅な書き方があるのではないかと思った.考えてみると,マトリクスの4つの座標を考慮し,4つの座標の境界で制御すればよい.最外層を循環するたびに、4つの境界を1層縮小すればよい.最後に、最外層サイクル終了条件として印刷出力があるか否かでよい.これにより,1つのforサイクルのみで解決し,最も優雅な方法でこの問題を完璧に解決した.同時に、最小限のサイクルで、複雑な境界判断を避ける.くだらないことは言わないで、直接コードをつけて、レンガを撮ることを歓迎します.


public class Test { 
        
        private boolean valid(int cc, int m, int n){ 
                if( cc >= m && cc <= n ){ 
                        return true; 
                } 
                return false; 
        } 
        
        public void print(int m, int n, int a[][], boolean visited[][]){ 
                int offsetX[] = new int[]{0,1,0,-1}; 
                int offsetY[] = new int[]{1, 0, -1, 0}; 
                
                int sX = 0, eX = n - 1; 
                int sY = 0, eY = m - 1; 
                
                boolean flag = false; 
                do{ 
                        if( sX > eX || sY > eY ){ 
                                break; 
                        } 
                        int xTmp = sX; 
                        int yTmp = sY; 
                        for( int ii = 0; ii < offsetX.length;){ 
                                if( valid( xTmp, sY, eY) && valid(yTmp, sX, eX) && !visited[xTmp][yTmp]){ 
                                        System.out.print(a[xTmp][yTmp]+"\t"); 
                                        visited[xTmp][yTmp] = true; 
                                        flag = true; 
                                } 
                                
                                if( valid(xTmp + offsetX[ii], sY, eY) && valid(yTmp + offsetY[ii], sX, eX) ){ 
                                        xTmp += offsetX[ii]; 
                                        yTmp += offsetY[ii]; 
                                }else{ 
                                        ii++; 
                                } 
                                
                        } 
                        sX++; 
                        eX--; 
                        sY++; 
                        eY--; 
                }while( flag ); 
        } 
        
        public static void main(String[] args) { 
                int a[][]; 
                int m = (int)(Math.random() * 5)+1; 
                int n = (int)(Math.random() * 5)+1; 
                
//                m = 10; 
//                n = 1; 
                
                a = new int[m][n]; 
                boolean visited[][] = new boolean[m][n]; 
                
                System.out.println( m + " * " + n); 
                
                for( int i = 0; i < m; i++ ){ 
                        for( int j = 0; j < n; j++ ){ 
                                int tmp = (int)(Math.random() * 10); 
                                a[i][j] = tmp; 
                                visited[i][j] = false; 
                                System.out.print(tmp+"\t"); 
                        } 
                        System.out.println(); 
                } 
                System.out.println(); 
                
                System.out.println("     :"); 
                Test t = new Test(); 
                t.print(m, n, a, visited); 
        } 
        
} 

印刷方向を考慮する必要はなく、1つのforサイクルだけで、時計回りの印刷タスクを優雅に完了します.境界条件をできるだけ少なく判断し,誤り確率を低減する.