【LeetCode 54】螺旋矩阵

问题描述解法1、模拟参考自【LeetCode 54】螺旋矩阵-CSDN博客int *spiralOrder(int **matrix, int matrixSize, int *matrixColSize, int *returnSize) { static const int dirs[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int *ans malloc(sizeof(*ans) * 100); int row matrixSize; int col matrixColSize[0]; int num row * col; int i 0; int j 0; int k 0; int h 0; *returnSize num; while (num--) { /* 记录元素并标记为已记录 */ ans[k] matrix[i][j]; matrix[i][j] 0xff; /* 下一步可能的位置 */ int curr i dirs[h][0]; int next j dirs[h][1]; /* 判断下一步可能的位置是否合理越界或已记录则右转90° */ if (curr 0 || curr row || next 0 || next col || matrix[curr][next] 0xff) h (h 1) 0x03; // (x % 4) - (x 0x03) /* 下一步的位置 */ i dirs[h][0]; j dirs[h][1]; } return ans; }矩阵 dirs[4][2] 表示四方向偏移数组存储上下左右四个移动增量常用于网格类算法。具体含义如下下标上解的hdx, dy移动方向0(0, 1)右列 11(1, 0)下行 12(0,-1)左列 - 13(-1,0)上行 - 1if 的判断条件拆解螺旋遍历数组时若下一格坐标越界或下一格已经走过则顺时针旋转90°h%41.curr 0下一步行坐标小于 0继续向上则将走出矩阵上边界2. curr row下一步行坐标 ≥ 总行数继续向下则将走出矩阵下边界3. next 0下一步列坐标小于 0继续向左则将走出矩阵左边界4. next col下一步列坐标 ≥ 总列数继续向右则将走出矩阵右边界5. matrix[curr][next] 0xff下一步坐标合法且没有越界但之前已经遍历过(h % 4) → (h 0x03)对一个正整数取4的余数本质就是截取其二进制的最后两位用位运算更快是常见的优化方式。2、建立并维护边界int* sprialOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) { if (!matrix) return NULL; int top 0, btm matrixSize - 1, left 0, right matrixColSize[0] - 1; *returnSize 0; int* arr malloc(sizeof(int) * matrixSize * matrixColSize[0]); while (top btm left right) { /* 左-右访问第top行 */ for (int i left; i right; i) arr[(*returnSize)] matrix[top][i]; top; /* 上-下访问第right列 */ for (int i top; i btm; i) arr[(*returnSize)] matrix[i][right]; right--; /* 右-左访问第btm行需要判断即将遍历的这条边是否存在 */ if (top btm) { for (int i right; i left; i--) arr[(*returnSize)] matrix[btm][i]; btm--; } /* 下-上访问第left列 */ if (left right) { for (int i btm; i top; i--) arr[(*returnSize)] matrix[i][left]; left; } } return arr; }【LeetCode 54】螺旋矩阵-CSDN博客解法2可看作是上解的优化方案二者的解决思路比较相似。