借助偏移量技巧
本题的要点是:
1)创建一个bool类型矩阵dict,将matrix矩阵中访问过的位置标记下来;
2)循环的终止条件为将所有row * col个数字全部导入res数组中;
3)以偏移量的方式替代常用的双重循环遍历数组的方式。
对于矩阵中的点P(x, y)有如下的性质:
P向右移动一位:P = (x + 0, y + 1);
P向下移动一位: P = (x + 1, y + 0);
P向左移动一位:P = (x + 0, y - 1);
P向上移动一位: P = (x - 1, y + 0);
若要顺时针打印矩阵,相当于“贪吃蛇”游戏,在蛇的头部即当前访问的位置即将“撞墙”时改变它的
前进方向,在没有撞墙风险的时候不需要改变前进方向。由题目要求可知,“贪吃蛇”的移动方向
一定是 向右->向下->向左->向上(->向右…)这样循环进行的。
所以我们可以用如下公式定义在本问题中的坐标变化:
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int d = 0;
x = x + dx[d], y = y + dy[d];
这样在无撞墙风险时,就能按照同一个方向访问下去。
在有撞墙风险的时,我们要改变前进方向,只需令
d = (d + 1) % 4;
x = x + dx[d], y = y + dy[d];
执行用时:20 ms, 在所有 Cpp 提交中击败了90.87%的用户
内存消耗:9.7 MB, 在所有 Cpp 提交中击败了94.34%的用户
C++代码
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if(!matrix.size() || !matrix[0].size())return {};
long long row = matrix.size(), col = matrix[0].size();
vector<vector<bool>> dict(row, vector<bool>(col));//用于记录哪些点已经访问过
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};//偏移量数组
vector<int> res(row * col);
for(int x = 0, y = 0, d = 0, k = 0; k < row * col; k ++){
res[k] = matrix[x][y];
dict[x][y] = true;//导入并记录
int a = x + dx[d], b = y + dy[d];//(a, b)是即将访问的节点
if(a < 0 || a >= row || b < 0 || b >= col || dict[a][b])//若(a, b)会“撞墙”
{
d = (d + 1) % 4;//改变方向
a = x + dx[d], b = y + dy[d];//更新a b
}
x = a, y = b;//用(a, b)更新(x, y),即用偏移量技巧代替传统的(i, j)遍历方式
}
return res;
}
};