【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] 表示四方向偏移数组，存储上下左右四个移动增量，常用于网格类算法。具体含义如下：

• if 的判断条件拆解：螺旋遍历数组时，若下一格坐标越界或下一格已经走过，则顺时针旋转90°（h%4）：

  1.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可看作是上解的优化方案，二者的解决思路比较相似。