59. Spiral Matrix II

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        unordered_map<int, pair<int, int>> dirPositionChanges = {
            // 0, 1, 2, 3 means right, down, left, up
            // the pair means the row and column's step
                {0, {0, 1}}, {1, {1, 0}}, {2, {0, -1}}, {3, {-1, 0}}};
        unordered_map<int, int> dirBorders = {{0, n - 1}, {1, n - 1}, {2, 0}, {3, 0}};
        vector<vector<int>> matrix(n, vector<int>(n));
        for (int i = 1, dir = 0, row = 0, column = 0, size = n * n; i <= size; i++) {
            matrix[row][column] = i;

            if (dir == 0 && column == dirBorders[dir]) {
                ++dirBorders[3];
                dir = (dir + 1) % 4;
            } else if (dir == 1 && row == dirBorders[dir]) {
                --dirBorders[0];
                dir = (dir + 1) % 4;
            } else if (dir == 2 && column == dirBorders[dir]) {
                --dirBorders[1];
                dir = (dir + 1) % 4;
            } else if (dir == 3 && row == dirBorders[dir]) {
                ++dirBorders[2];
                dir = (dir + 1) % 4;
            }

            row += dirPositionChanges[dir].first; // use map to get step, let the code more neat
            column += dirPositionChanges[dir].second;
        }

        return matrix;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// more neat. but slower
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        unordered_map<int, pair<int, int>> dirPositionChanges = {
                {0, {0, 1}}, {1, {1, 0}}, {2, {0, -1}}, {3, {-1, 0}}};
        unordered_map<int, int> dirBorders = {{0, n - 1}, {1, n - 1}, {2, 0}, {3, 0}};
        unordered_map<int, pair<int, int>> dirBordersChange = {
                {0, {3, 1}}, {1, {0, -1}}, {2, {1, -1}}, {3, {2, 1}}};
        vector<vector<int>> matrix(n, vector<int>(n));
        for (int i = 1, dir = 0, row = 0, column = 0, size = n * n; i <= size; i++) {
            matrix[row][column] = i;

            if (dir == 0 && column == dirBorders[dir] || dir == 1 && row == dirBorders[dir] ||
                dir == 2 && column == dirBorders[dir] || dir == 3 && row == dirBorders[dir]) {
                dirBorders[dirBordersChange[dir].first] += dirBordersChange[dir].second;
                dir = (dir + 1) % 4;
            }

            row += dirPositionChanges[dir].first;
            column += dirPositionChanges[dir].second;
        }

        return matrix;
    }
};