螺旋矩阵2
感觉比1好做一点,所以先做这题了
找到循环的思路
把一次循环分成这样来进行
- 计算好循环次数 n/2
- n是奇偶,奇数需要补齐中间值
- 用一个偏移量,记录好每次循环中的偏移,因为可以发现每次循环左右都会向内缩
- 做好循环,思路清晰
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int times=n/2;
int Odd=n%2==0?0:1;
int offset=0;
vector<vector<int>> ans(n,vector<int>(n));
int num=1;
while(times--)
{
for(int i=offset;i<n-offset-1;i++)
{
ans[offset][i]=num++;
}
for(int j=offset;j<n-offset-1;j++)
{
ans[j][n-offset-1]=num++;
}
for(int i=n-offset-1;i>offset;i--)
{
ans[n-1-offset][i]=num++;
}
for(int j=n-offset-1;j>offset;j--)
{
ans[j][offset]=num++;
}
offset++;
}
if(Odd)
{
ans[offset][offset]=num;
}
return ans;
}
};
54螺旋矩阵
好晕,好多变量
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
vector<vector<bool>>visited(m,vector<bool>(n,0));
int offset=0;
int m2=(m/2)*2;
int n2=(n/2)*2;
int Oddm=(m%2==0)?0:1;
int Oddn=(n%2==0)?0:1;
vector<int> ans;
while(m2>0&&n2>0)
{
for(int i=offset;i<n-1-offset;i++)
{
ans.push_back(matrix[offset][i]);
//有一个--
visited[offset][i]=1;
}m2--;
for(int j=offset;j<m-1-offset;j++)
{
ans.push_back(matrix[j][n-1-offset]);
//--
visited[j][n-1-offset]=1;
}n2--;
for(int i=n-1-offset;i>offset;i--)
{
ans.push_back(matrix[m-1-offset][i]);
//谁--
visited[m-1-offset][i]=1;
}m2--;
for(int j=m-1-offset;j>offset;j--)
{
ans.push_back(matrix[j][offset]);
visited[j][offset]=1;
//谁--
}n2--;
offset++;
}
if(Oddm||Oddn)
{
if(n>m)
{
for(int i=offset;i<n-offset;i++)
{
if(!visited[offset][i])
ans.push_back(matrix[offset][i]);
}
}
else
{
for(int i=offset;i<m-offset;i++)
{
if(!visited[i][offset])
ans.push_back(matrix[i][offset]);
}
}
}
return ans;
}
};
螺旋矩阵3
我认为这题比上题简单很多,循环更好找
从选定点出发向右1格,向下1格,想做2格,向上2格,向右3格,向下3格,向左4个,向上4格....
每两次循环offset就++就可以了,然后判断一下在不在格子内,
对于循环次数,
- 我这里是采取了最蠢的方法,循环(row*col)^2
- 其实可以每次循环中记录遍历了几格,遍历了就++,直到遍历次数=格子数,我改改。。
结果难绷:
class Solution {
public:
vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart,
int cStart) {
vector<vector<int>> ans;
int offset = 1;
int times = pow((max(rows, cols)), 2);
while (times--) {
for (int i = 0; i < offset; i++) {
if (cStart < cols && rStart < rows && cStart >= 0 &&
rStart >= 0) {
ans.push_back({rStart, cStart});
}
cStart++;
}
for (int i = 0; i < offset; i++) {
if (cStart < cols && rStart < rows && cStart >= 0 &&
rStart >= 0) {
ans.push_back({rStart, cStart});
}
rStart++;
}
offset++;
for (int i = 0; i < offset; i++) {
if (cStart < cols && rStart < rows && cStart >= 0 &&
rStart >= 0) {
ans.push_back({rStart, cStart});
}
cStart--;
}
for (int i = 0; i < offset; i++) {
if (cStart < cols && rStart < rows && cStart >= 0 &&
rStart >= 0) {
ans.push_back({rStart, cStart});
}
rStart--;
}
offset++;
}
return ans;
}
};
螺旋矩阵4
思路:
- 规定一个方向数组,按顺序是向右,向下,向左,向上
- 从0开始遍历,一开始的方向是向右
- 如果遇到访问过的,或者超标了,方向就到下一个
direction=(direction+1)%4
- 循环次数是m*n-1,因为第一个是我手动输入的
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
vector<vector<int>> ans(m,vector<int>(n));
vector<vector<bool>> visited(m,vector<bool>(n,0));
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int times=0;
int direction=0;
int x=0;
int y=0;
ans[0][0]=head->val;
visited[0][0]=1;
head=head->next;
while(times<m*n-1)
{
int nextx=x+dir[direction][0];
int nexty=y+dir[direction][1];
if(nextx<0||nexty<0||nextx>=m||nexty>=n||visited[nextx][nexty])
{
direction=(direction+1)%4;
continue;
}
if(!visited[nextx][nexty])
{
if(head!=nullptr)
{
ans[nextx][nexty]=head->val;
head=head->next;
}
else
{
ans[nextx][nexty]=-1;
}
visited[nextx][nexty]=true;
times++;
x=nextx;
y=nexty;
}
}
return ans;
}
};