2014年5月11日星期日

Loop Solution - Spiral Matrix II - Matrix Recursive

The idea is similar to Spiral Matrix I. A result matrix us constructed by each edge, and pass the new start position x, y to next recursive call. A base number is also passed as the next value on that position, and also used inside each call for each edge. Next level n is reduced by 2 since the matrix size change (inside two edge). Result is passed as Java passing by reference. When n is 1, it is time to end the recursion and return.

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] results = new int[n][n];
        generateMatrixOps(results, n, 0, 0, 0);
        return results;
    }
   
    private void generateMatrixOps(int[][] results, int n, int base, int x, int y){
        if(n <= 0){
            return;
        }
        if(n == 1){
            results[x][y] = base + 1; // see line 17... plus 1 !!!
            return;// return ...... get out of the current loop!!!
        }
        for(int i  = 0; i < n; i++){
            results[x + 0][y + i] = base + i + 1;
        }
        base = results[x + 0][y + n - 1];
        for(int i = 1; i < n; i++){
            results[x + i][y + n - 1] = base + i;
        }
        base = results[x + n - 1][y + n - 1];
        for(int i = 1; i < n; i++){
            results[x + n - 1][y + n - 1 - i] = base + i;
        }
        base = results[x + n - 1][y];
        for(int i = 1; i < n - 1; i++){
            results[x + n - 1 - i][y] = base + i;
        }
        base = results[x + 1][y];
       
        generateMatrixOps(results, n - 2, base, x + 1, y + 1);
    }
}

没有评论: