LeetCode刷题记录（图论篇）

LeetCode刷题记录（图论篇），个人向。
之后为了提高效率，转而以Hot 100作为刷题蓝图。

[200] Number of Islands

难度：Medium
语言：C++

题目描述。
把1看成节点，上下左右相邻的1之间看成有边，相当于求图有几个连通分量。依次以不同的起点做遍历，查看有几个可开始遍历的起点即可。遍历使用DFS或BFS都可以，这里也同时给出了两种遍历的写法。

class Solution {
 public:
  void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x,
           int y, const vector<pair<int, int>>& directions) {
    visited[x][y] = true;
    int m = grid.size(), n = grid[0].size();

    for (auto [dx, dy] : directions) {
      int nx = x + dx, ny = y + dy;
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny] &&
          grid[nx][ny] == '1') {
        dfs(grid, visited, nx, ny, directions);
      }
    }
  }

  // use DFS
  int numIslands(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size(), result = 0;
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    vector<pair<int, int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (!visited[i][j] && grid[i][j] == '1') {
          ++result;
          dfs(grid, visited, i, j, directions);
        }
      }
    }
    return result;
  }

  // use BFS
  int numIslandsBFS(vector<vector<char>>& grid) {
    int m = grid.size(), n = grid[0].size(), result = 0;
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    vector<pair<int, int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    queue<pair<int, int>> q;

    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (!visited[i][j] && grid[i][j] == '1') {
          ++result;
          q.push({i, j});
          visited[i][j] = true;

          while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            for (auto [dx, dy] : directions) {
              int nx = x + dx, ny = y + dy;
              if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny] &&
                  grid[nx][ny] == '1') {
                q.push({nx, ny});
                visited[nx][ny] = true;
              }
            }
          }
        }
      }
    }
    return result;
  }
};

[994] Rotting Oranges

难度：Medium
语言：C++

题目描述。
模拟广度优先搜索。需要注意的是，我们为了把每一轮新访问到的节点区分出来，需要先记录一下队列的大小，然后处理该指定数量的元素来作为BFS的一轮（类似于树的层序遍历，为了区分出每一层，队列大小就是该层的节点数量）。

class Solution {
 public:
  int orangesRotting(vector<vector<int>>& grid) {
    int nr = grid.size();
    int nc = grid[0].size();
    vector<pair<int, int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int result = 0;
    queue<pair<int, int>> q;
    int count = 0;

    for (int i = 0; i < nr; ++i) {
      for (int j = 0; j < nc; ++j) {
        if (grid[i][j] == 1) {
          count += 1;
        } else if (grid[i][j] == 2) {
          q.push({i, j});
        }
      }
    }

    while (count > 0 && !q.empty()) {
      ++result;
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        auto [x, y] = q.front();
        q.pop();
        for (auto [dx, dy] : directions) {
          int nx = x + dx, ny = y + dy;
          if (nx >= 0 && ny >= 0 && nx < nr && ny < nc && grid[nx][ny] == 1) {
            grid[nx][ny] = 2;
            count -= 1;
            q.push({nx, ny});
          }
        }
      }
    };

    return count ? -1 : result;
  }
};

[207] Course Schedule

难度：Medium
语言：C++

题目描述。
基本的拓扑排序，只不过从算法变成具体实现的代码需要注意的细节还是比较多。
先把输入prerequisites转成邻接表以及同时统计节点度数，然后把入度为0的点放入队列进行BFS即可（遍历到的节点从图中去掉，取新的入度为0的节点入队）。最后查看是否每个节点都遍历到了（能从图中去掉）即可。
这道题也可使用DFS，可参考这篇solution。

class Solution {
 public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    unordered_map<int, vector<int>> map;
    vector<int> degree(numCourses, 0);
    for (auto edge : prerequisites) {
      map[edge[1]].push_back(edge[0]);
      degree[edge[0]] += 1;
    }

    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
      if (degree[i] == 0) {
        q.push(i);
      }
    }

    int visited = 0;
    while (!q.empty()) {
      ++visited;
      int cur = q.front();
      q.pop();
      for (auto course : map[cur]) {
        if (--degree[course] == 0) {
          q.push(course);
        }
      }
    }

    return visited == numCourses;
  }
};

[208] Implement Trie (Prefix Tree)

难度：Medium
语言：C++

题目描述。
题目限定了英文小写字符，因此直接指定26个children，以children的index来对应相应的小写字符。此外，使用bool变量isEnd来表示当前node是否可作为单词的结尾。
插入时类似链表，一层一层往下插入，在结尾node标记一下isEnd为true即可。查找时也类似链表查找，需要注意的是search需要最后找到的node刚好是可作为结尾的node（isEnd为true），而startWith只需要找到对应node（说明存在该前缀）即可。

class Trie {
  vector<Trie*> children;
  bool isEnd;

 public:
  Trie() {
    isEnd = false;
    children = vector<Trie*>(26);
  }

  void insert(string word) {
    Trie* node = this;
    for (auto c : word) {
      if (node->children[c - 'a'] == nullptr) {
        node->children[c - 'a'] = new Trie();
      }
      node = node->children[c - 'a'];
    }
    node->isEnd = true;
  }

  bool search(string word) {
    Trie* node = this;
    for (auto c : word) {
      if (node->children[c - 'a'] == nullptr) {
        return false;
      }
      node = node->children[c - 'a'];
    }
    return node->isEnd;
  }

  bool startsWith(string prefix) {
    Trie* node = this;
    for (auto c : prefix) {
      if (node->children[c - 'a'] == nullptr) {
        return false;
      }
      node = node->children[c - 'a'];
    }
    return true;
  }
};

总结

由于现在暂时改成按照Hot 100来刷，所以相比之前长篇的二叉树，这里图论只刷了4道。
首先要注意的是图的表示形式，有邻接表和邻接矩阵，但一般来说邻接表用得多一些。（若稠密图，也可使用邻接矩阵）。
图的遍历方式主要是DFS与BFS，一些题目使用两种遍历方式都可（200、207），一些题目则只适合其中一种（994）。
最后的实现前缀树（208）则和链表的操作很类似，只不过一个节点同时对应了很多个后继而已。

AllenY's blog