leetcode_spiral_matrix_ii

发表于

解题思路：和spiral_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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ret;
        for(int i = 0; i < n; i++)
        {
            ret.push_back(vector<int>(n));
        }
        int current_n = n;
        int left_top_bound = 0;
        int i = 0, j = 0;
        int number = 1;
        while(current_n > 0)
        {
            i = left_top_bound;
            j = left_top_bound;
            if(current_n == 1)
            {
                ret[i][j] = number++;
                current_n--;
            }
            else if(current_n > 1)
            {
                for(; j < left_top_bound + current_n; j++)
                {
                    ret[i][j] = number++;
                }
                j--;
                i++;
                for(; i < left_top_bound + current_n; i++)
                {
                    ret[i][j] = number++;
                }
                i--;
                j--;
                for(; j >= left_top_bound; j--)
                {
                    ret[i][j] = number++;
                }
                j++;
                i--;
                for(; i > left_top_bound; i--)
                {
                    ret[i][j] = number++;
                }
                current_n -= 2;
                left_top_bound++;
            }
            
        }
        return ret;
    }
};

运行结果：时间3ms，超过18.5％

上面的代码不够简洁。在写一下思路：

1
2
3
4
5
6
7
8
9
0 	1 	2 	3
11 	12 	13 	4
10	15 	14 	5
9	8	7	6

[0,0] [0,1] [0,2]	//col++
[0,3] [1,3] [2,3]	//row++
[3,3] [3,2] [3,1]	//col--
[3,0] [2,0] [1,0]	//row--
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ret (n, vector<int>(n,0));
        int width = n;
        int number = 1;
        int row = 0;
        int col = 0;
        while(width > 0)
        {
            if(width == 1)
            {

                ret[row][col] = number++;
                break;
            }
            else
            {
                int iter_number = width-1;
                for(int i = 0 ;i < iter_number; i++)
                {
                    // cout<<"row:"<<row<<" col:"<<col<<endl;
                    // cout<<"number:"<<number<<endl;
                    ret[row][col++] = number++;
                    // cout<<"ret[][]:"<<ret[row][col-1]<<endl;
                }
                for(int i = 0 ;i < iter_number; i++)
                {

                    ret[row++][col] = number++;
                }
                for(int i = 0; i < iter_number; i++)
                {

                    ret[row][col--] = number++;
                }

                for(int i = 0; i < iter_number; i++)
                {
                    ret[row--][col] = number++;
                }
                row +=1;
                col +=1;
                width -=2;
            }
        }
        return ret;
    }
};

运行时间：3ms，超过17.41%