数组NO.10:59.螺旋矩阵II
2021/12/21 23:24:52
本文主要是介绍数组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.总结
在解决问题的时候,要将问题一步步分而治之,直至最小问题被解决,否则不可以停止。我在此题中犯的错误是将问题分解止步于确定了循环不变量,但是对于之后的问题并没有进行进一步的细分,比如:
- 每一次循环的填充长度如何确定?
- 每一次循环如何和下一次进行对接?
- 对于循环次数如何确定?
- 对于奇数时,最中间的值如何处理?
这篇关于数组NO.10:59.螺旋矩阵II的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南