54.spiral-matrix.md

螺旋矩阵

题目

思路

根据传入的数组, 设置一个对应的数组, 来标记是否未走. 同时设置当前的坐标[0, 0]

[ [1,2,3], [4,5,6], [7,8,9] ]

=>

[ [true, true, true], [true, true, true], [true, true, true] ]

1. 根据题目, 坐标将会顺时针走.
2. 坐标走时, 对下一个坐标进行判断, 判断是否允许走, 不允许走则换个方向走
3. 方向顺序为 右 -> 下 -> 左 -> 上 -> 右. 一直循环, 直到走完.

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  const xLength = matrix.length
  if (xLength === 0) {
    return []
  }
  const yLength = matrix[0].length
  const length = xLength * yLength

  const result = []
  /** 走过的路径 */
  const walkMatrix = new Array(xLength).fill(true)
  walkMatrix.forEach((v, i) => {
    walkMatrix[i] = new Array(yLength).fill(true)
  })
  // 0  1  2  3
  // 右 下 左 上
  let dir = 0
  const points = [0, 0]

  while (result.length < length) {
    result.push(matrix[points[0]][points[1]])
    walkMatrix[points[0]][points[1]] = false

    switch (dir) {
      case 0:
        if (points[1] === yLength - 1 || !walkMatrix[points[0]][points[1] + 1]) {
          dir++
          points[0]++
        } else {
          points[1]++
        }
        break
      case 1:
        if (points[0] === xLength - 1 || !walkMatrix[points[0] + 1][points[1]]) {
          dir++
          points[1]--
        } else {
          points[0]++
        }
        break
      case 2:
        if (points[1] === 0 || !walkMatrix[points[0]][points[1] - 1]) {
          dir++
          points[0]--
        } else {
          points[1]--
        }
        break
      case 3:
        if (points[0] === 0 || !walkMatrix[points[0] - 1][points[1]]) {
          dir = 0
          points[1]++
        } else {
          points[0]--
        }
        break
    }
  }
  return result
};

class Solution {
  /**
   * @param Integer[][] $matrix
   * @return Integer[]
   */
  function spiralOrder($matrix) {
    $xLength = count($matrix);

    if ($xLength === 0) {
      return [];
    }
    $yLength = count($matrix[0]);
    $length = $xLength * $yLength;

    $result = [];
    $walkMatrix = [];

    for ($i = 0; $i < $xLength; $i++) {
      for ($j = 0; $j < $yLength; $j++) {
        if ($j === 0) {
          array_push($walkMatrix, [true]);
        } else {
          array_push($walkMatrix[$i], true);
        }
      }
    }

    $dir = 0;
    $points = [0, 0];
    while (count($result) < $length) {
      array_push($result, $matrix[$points[0]][$points[1]]);
      $walkMatrix[$points[0]][$points[1]] = false;
      switch ($dir) {
        case 0:
          if ($points[1] === $yLength - 1 || !$walkMatrix[$points[0]][$points[1] + 1]) {
            $dir++;
            $points[0]++;
          } else {
            $points[1]++;
          }
          break;
        case 1:
          if ($points[0] === $xLength - 1 || !$walkMatrix[$points[0] + 1][$points[1]]) {
            $dir++;
            $points[1]--;
          } else {
            $points[0]++;
          }
          break;
        case 2:
          if ($points[1] === 0 || !$walkMatrix[$points[0]][$points[1] - 1]) {
            $dir++;
            $points[0]--;
          } else {
            $points[1]--;
          }
          break;
        case 3:
          if ($points[0] === 0 || !$walkMatrix[$points[0] - 1][$points[1]]) {
            $dir = 0;
            $points[1]++;
          } else {
            $points[0]--;
          }
          break;
      }
    }
    return $result;
  }
}

class Solution {
  public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<Integer>();

    int xLength = matrix.length;
    if (xLength == 0) {
      return result;
    }
    int yLength = matrix[0].length;
    int length = xLength * yLength;

    List<List<Boolean>> walkMatrix = new ArrayList<>();

    for (int i = 0; i < xLength; i++) {
      for (int j = 0; j < yLength; j++) {
        if (j == 0) {
          List<Boolean> tmp = new ArrayList<Boolean>();
          tmp.add(true);
          walkMatrix.add(tmp);
        } else {
          walkMatrix.get(i).add(true);
        }
      }
    }
    int dir = 0;
    int[] points = {0, 0};

    while (result.size() < length) {
      result.add(matrix[points[0]][points[1]]);
      walkMatrix.get(points[0]).set(points[1], false);
      switch (dir) {
        case 0:
          if (points[1] == yLength - 1 || !walkMatrix.get(points[0]).get(points[1] + 1)) {
            dir++;
            points[0]++;
          } else {
            points[1]++;
          }
          break;
        case 1:
          if (points[0] == xLength - 1 || !walkMatrix.get(points[0] + 1).get(points[1])) {
            dir++;
            points[1]--;
          } else {
            points[0]++;
          }
          break;
        case 2:
          if (points[1] == 0 || !walkMatrix.get(points[0]).get(points[1] - 1)) {
            dir++;
            points[0]--;
          } else {
            points[1]--;
          }
          break;
        case 3:
          if (points[0] == 0 || !walkMatrix.get(points[0] - 1).get(points[1])) {
            dir = 0;
            points[1]++;
          } else {
            points[0]--;
          }
          break;
      }
    }
    return result;
  }
}