数组NO.10:59.螺旋矩阵II

1.题目

2.解法一

2.1.思路分析

该题属于模拟过程题,所求的未知量一个是平方,一个是逆时针旋转。关键在于逆时针旋转,每一个矩阵可以看成一圈一圈的数字组成,因此解决了最外层的一圈,基本上解决了问题。
要想解决最外层的一圈,循环是关键,要想准确无误地进行循环,确定循环不变量就是解决办法,无论选择左闭右开,还是左闭右闭,只要确定了,那么在循环的过程中就要一直遵循。否则就是一入循环深似海,从此offer是路人

2.2.算法描述

  • 先从左到右填充上行;
  • 再从上到下填充右行;
  • 再从右到左填充下行;
  • 再从下到上填充左行;
  • 循环上面四步,直至填充完毕。

2.3.算法实现

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n, 0));
        int startx = 0;
        int starty = 0;
        int value = 1;
        int loop = n / 2;
        int length = 1;
        int mid = n / 2;
        
        while (loop--) {
            int i = startx;
            int j = starty;
            
            while (j < n + starty - length) {
                result[i][j] = value++;
                j++;
            }
            while (i < n + startx - length) {
                result[i][j] = value++;
                i++;
            }
            while (j > starty) {
                result[i][j] = value++;
                j--;
            }
            while (i > startx) {
                result[i][j] = value++;
                i--;
            }
            
            startx++;
            starty++;
            
            length += 2; 
        }
        
        if (n % 2) {
            result[mid][mid] = value;
        }
       
        return result;
    }
};

3.总结

在解决问题的时候,要将问题一步步分而治之,直至最小问题被解决,否则不可以停止。我在此题中犯的错误是将问题分解止步于确定了循环不变量,但是对于之后的问题并没有进行进一步的细分,比如:

  • 每一次循环的填充长度如何确定?
  • 每一次循环如何和下一次进行对接?
  • 对于循环次数如何确定?
  • 对于奇数时,最中间的值如何处理?
上一篇:记录golang colly爬虫编码问题


下一篇:213. 打家劫舍 II