200. 岛屿数量

遍历搜索

• 找到‘1’后，采用广度优先，将所有在同一岛屿上的‘1’标为‘0’，计数 +1
• 重复以上步骤，直到矩阵内没有‘1’
• 时间复杂度：大于 O(n); 空间复杂度：O(1)

遍历比较

• 从左到右，从上到下遍历点

• 若当前位置为 1，且其左，上位置点均为 0，则标为当前计数 +1

• 若当前位置为 1，左，上位置均不为 0，则标记为较小数，将当前与上一行所有较大数同时变更为较小数，计数 -1

• 时间复杂度：大于 O(n); 空间复杂度：O(1)

  class Solution {
  public:
  int numIslands(vector<vector<char>> &grid) {
      int islandCount = 0;
      int islandId = 0;
      int rowN = grid.size();
      int colN = grid.cbegin()->size();
      for (int i = 0; i < rowN; i++) {
      for (int j = 0; j < colN; j++) {
          if (grid[i][j] == '1') {
          auto top_value = i == 0 ? 0 : grid[i - 1][j] - '0';
          auto left_value = j == 0 ? 0 : grid[i][j - 1] - '0';
          if (top_value == 0 && left_value == 0) {
              grid[i][j] = ++islandId + '0';
              islandCount++;
          } else if (top_value == 0 || left_value == 0) {
              grid[i][j] = top_value == 0 ? left_value + '0' : top_value + '0';
          } else {
              auto cur_value = min(top_value, left_value);
              if (top_value != left_value) {
              replace(grid[i - 1].begin(), grid[i - 1].end(),
                      max(top_value, left_value) + '0', cur_value + '0');
              replace(grid[i].begin(), grid[i].end(),
                      max(top_value, left_value) + '0', cur_value + '0');
              islandCount--;
              }
              grid[i][j] = cur_value + '0';
          }
          }
      }
      }
      return islandCount;
  }
  };

• 运行结果：未通过

  • 48/49 cases passed (N/A)

• 原因：id 采用 char 存储，最大值为 127，当超过 127 时，id 会混乱，导致计算错误