汉扬编程 编程大纲 leetcode C++题解系列-058 螺旋矩阵 II

leetcode C++题解系列-058 螺旋矩阵 II

leetcode C++题解系列-058 螺旋矩阵 II

leetcode C++题解系列-058 螺旋矩阵 II

题目给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入: 3输出:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]]解题代码与测试//// Created by tannzh on 2020/7/17.///* * 螺旋矩阵 II 给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。示例:输入: 3输出:[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ]] */#include <iostream>#include <vector>using std::vector;class Solution {public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> vec(n, vector<int>(n,-1)); for (int i=0, j=n; _value != n*n; ++i, –j) spiralFilled(i, j, vec); return vec; }private: void spiralFilled(int beg, int end, vector<vector<int> >& vec) { for (int i=beg, j=beg; true; ) { if (vec[i][j] == -1) vec[i][j] = ++_value; else break; if (i == beg && j != end-1) { ++j; continue; } if (j == end-1 && i != end-1) { ++i; continue; } if (i == end-1 && j != beg) { –j; continue; } if (j == beg && i != beg) { –i; continue; } } }private: int _value{0};};int main(int argc, char **argv){ Solution s; for (const auto &v : s.generateMatrix(3)) { for (auto i : v) std::cout << i << " "; std::cout << std::endl; } return 0;}解题思路分析这道题我戏称为“迷宫题”。回忆一下小时候在公园里,是否遇到过这样一种简陋迷宫,迷宫里不断的转圈,最终你进入了一个圆圈的中心,可能有个小广场,小雕塑,或是小房子在那里等着你。

这道题只不过把圈圈变成了正方形罢了。处于中心位置的数,恰好是 n*n.

不知道上述的描述会不会给你什么启发,而我就是完全依照这个思路去解的,所以效率也许并不高,也说不出这属于那种算法的范畴。以三维矩阵为例,设行为i, 列为j,如果把最外圈转一遍,记录步骤如下表:

可以发现,最后我们又回到了原点,却没有像我们想象的那样,停在[1][0]的地方,在迷宫里,这个地方意味着你面对着一堵墙,你不能去撞墙,而是要右转进入下一个圈圈。

程序里,我们就要为墙所在的地方设置标记位。换句话说,我们也可以给不为墙的地方设置标记位,如给二维数组初始化时,将值设为 -1.那么走过的地方自然不可能为 -1,就成了墙。

所以转圈停止的条件为: Matrix[i][j] != -1;

ok,如果将每一步产生的值记录下来(设为value, 每走一步就自加), 那么当 value == nn 的时候就算走到了中心。如果不等于 nn,就要向里面再转一圈。

思路很清楚了,我觉得这个解法很直接,代码也并不繁复,非常好理解。

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/mianfei/6837.html

C语言编程之递归实现汉诺塔图解

C语言如何把结构内容保存到文件中?

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部