59.Spiral-Matrix-II

59. Spiral Matrix II

题目地址

https://leetcode.com/problems/spiral-matrix-ii/

题目描述

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

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

代码

Approach 1: Recursive

1、生成二维数组

2、每次对n的外圈进行四次loop赋值

3、n-2进入下一次递归

class Solution {
    public int[][] generateMatix(int n) {
        int result[][] = new int[n][n];
        setValue(0, 0, result, n);
        return result;
    }

    void setValue(int row, int col, int[][] result, int n) {

    // exit condition
        if (n <= 0)    return;
        if (row == 0 && col == 0) {
            result[row][col] = 1;
        }

        /// top: row, col + [0, n-1]
        for (int i = 0; i <= n - 1; i++) {
            result[row][col + i] = result[row][col] + i;
        }

        // right: row + [1, n-1], col
        for (int i = 1; i <= n - 1; i++) {
            result[row + i][col + n - 1] = result[row][col + n - 1] + i;
        }

        // bottom: row + [n-2, 0], col + n - 1
        for (int i = n - 2; i >= 0; i--) {
            result[row + n - 1][col + i] = result[row + n - 1][col + n - 1] + n - 1 - i;
        }

        // left: row, col + [n - 2, 1]
        for (int i = n - 2; i >= 1; i--) {
            result[row + i][col] = result[row + n - 1][col] + n - 1 - i;
        }


        if (row + 1 < n && col + 1 < n) {
            result[row + 1][col + 1] = result[row + 1][col] + 1;
            setValue(row + 1, col + 1, result, n - 2);
        }

    }

}

Approach 2: Iterative

class Solution {
  public int[][] generateMatrix(int n) {
    if (n < 0)  return null;

    int[][] result = new int[n][n];

    int xStart = 0;
    int yStart = 0;
    int num = 1;

    while (n > 0) {
      if (n == 1) {
        result[yStart][xStart] = num++;
        break;
      }

      // top
      for (int i = 0; i < n - 1; i++) {
        result[yStart][xStart + i] = num++;
      }

      // right
      for (int i = 0; i < n - 1; i++) {
        result[yStart + i][xStart + n - 1] = num++;
      }

      // bottom
      for (int i = 0; i < n - 1; i++) {
        result[yStart + n - 1][xStart + n - 1 - i] = num++;
      }

      // left
      for (int i = 0; i < n - 1; i++) {
        result[yStart + n - 1 - i][xStart] = num++;
      }

      xStart++;
      yStart++;
      n = n - 2;
    }

    return result;
  }
}

Approach #3 Traverse Layer by Layer in Spiral Form

class Solution {
  public int[][] generateMatrix(int n) {
    int[][] result = new int[n][n];
    int cnt = 1;
    for (int layer = 0; layer < (n + 1) / 2; layer++) {
      // direction 1 - traverse from left to right
      for (int ptr = layer; ptr < n - layer; ptr++) {
          result[layer][ptr] = cnt++;
      }
      // direction 2 - traverse from top to bottom
      for (int ptr = layer + 1; ptr < n - layer; ptr++) {
          result[ptr][n - layer - 1] = cnt++;
      }
      // direction 3 - traverse from right to left
      for (int ptr = layer + 1; ptr < n - layer; ptr++) {
          result[n - layer - 1][n - ptr - 1] = cnt++;
      }
      // direction 4 - traverse from bottom to top
      for (int ptr = layer + 1; ptr < n - layer - 1; ptr++) {
          result[n - ptr - 1][layer] = cnt++;
      }
    }
    return result;
  }
}