LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

标记走过的陆地，最终 DFS 的次数即为结果

class Solution {
 public:
  int numIslands(vector<vector<char>>& grid) {
    if (empty(grid) || empty(grid[0])) {
      return 0;
    }
    int res = 0;
    for (int i = 0; i < size(grid); ++i) {
      for (int j = 0; j < size(grid[0]); ++j) {
        if (grid[i][j] == '1') {
          ++res;
          dfs(grid, i, j);
        }
      }
    }
    return res;
  }

  void dfs(vector<vector<char>>& grid, int i, int j) {
    if (grid[i][j] == '1') {
      grid[i][j] = '#';
      if (i > 0) {
        dfs(grid, i - 1, j);
      }
      if (i + 1 < size(grid)) {
        dfs(grid, i + 1, j);
      }
      if (j > 0) {
        dfs(grid, i, j - 1);
      }
      if (j + 1 < size(grid[0])) {
        dfs(grid, i, j + 1);
      }
    }
  }
};

对于不相交的集合，可以用并查集来处理，并查集有两个核心操作，一是查找（Find）给定元素所在的唯一集合，二是合并（Union）两个集合

v[i] = a b c a d a a b c
i    = 0 1 2 3 4 5 6 7 8

对于上述数组，将相同字符的元素分为同一组
对相同字符元素，用一个新数组 p[i] 记录其中一个的索引
v[i] = a b c a d a a b c
p[i] = 0 1 2 0 4 0 0 1 2
i    = 0 1 2 3 4 5 6 7 8

这样就相当于对 v[i] 进行了分组，分组情况记录在 p[i] 中
v[0]、v[3]、v[5]、v[6] 均为 a，分为一组，对应有
p[0]、p[3]、p[5]、p[6] 均为 0，即第一个 a 的索引，p[0] 可视为这一组的代表者
一组只会有一个代表者，代表者的核心特征是，p[i] == i
最后遍历 p[i]，其中代表者的数量（即满足 p[i] == i 的元素数）即为分组数量

现在开始构建 p[i]
首先初始化 p[i] 为 i，即每个元素单独为一组，因为每个元素均为代表者
p[i] = 0 1 2 3 4 5 6 7 8
i    = 0 1 2 3 4 5 6 7 8

把 v[3] 所在组合并到 v[0] 所在组
设置 p[3] 为 p[0]，此时 v[3] 和 v[0] 为一组，v[0] 为代表者（p[0] == 0）
p[i] = 0 1 2 3 4 5 6 7 8
i    = 0 1 2 0 4 5 6 7 8

把 v[4] 所在组合并到 v[3] 所在组，v[3] 不是代表者（p[3] != 3），因此要先找到该组代表者
p[p[3]] = p[0]，p[0] == 0，找到代表者，将 p[4] 设为 p[0]
p[i] = 0 1 2 3 4 5 6 7 8
i    = 0 1 2 0 0 5 6 7 8

这样，通过一个组的任意组员，均可以合并到该组，比如把 v[5] 合并到该组

如果通过 v[4]：
p[4] != 4，不为代表者 => p[p[4]] = p[0]，p[0] == 0，为代表者 => p[5] = p[0]

如果通过 v[3]：
p[3] != 3，不为代表者 => p[p[3]] = p[0]，p[0] == 0，为代表者 => p[5] = p[0]

如果通过 v[0]：
p[0] == 0，为代表者 => p[5] = p[0]

现在不直接这样合并，考虑先把 v[5] 添加到 v[6] 所在组，再把 v[6] 添加到 v[3] 所在组
这样 v[0]、v[3]、v[4]、v[5]、v[6] 应被合并为一组

v[5] 合并到 v[6] 所在组，令 v[6] 为代表者，设置 p[5] = p[6] 即可
p[i] = 0 1 2 3 4 5 6 7 8
i    = 0 1 2 0 0 6 6 7 8
现在 v[5] 和 v[6] 为一组，v[0]、v[3]、v[4] 为一组

v[6] 所在组合并到 v[4] 所在组
p[6] = 6，为代表者
p[4] != 4，不为代表者 => p[p[4]] = p[0]，p[0] == 0，为代表者 => p[6] = p[0]
p[i] = 0 1 2 3 4 5 6 7 8
i    = 0 1 2 0 0 6 0 7 8
现在 v[0]、v[3]、v[4]、v[5]、v[6] 即为一组

虽然 p[5] 不为 0，但是依然可以找到该组的代表
p[5] != 5 => p[p[5]] = p[6]，p[6] != 6 => p[p[6]] = p[0]，p[0] == 0，为代表者

可见并査集的方便在于，通过两组的任意成员，均可合并两组
因为一组只能有一个代表者，合并时必须找到两组的代表者
将其中一个的值设定为另一个，这样代表者将只保留一个，并完成了合并

并查集简单实现如下

class DisjointSetUnion {
 public:
  void MakeSet(int n) {
    p.resize(n);
    p.shrink_to_fit();
    iota(begin(p), end(p), 0);  // p 初始化为 0 1 2 ... n - 1
  }

  int FindSet(int i) const {  // 查找代表者
    while (p[i] != i) {
      i = p[i];  // 最终 p[i] == i
    }
    return i;  // 返回值为代表者索引
  }

  void Union(int parent, int child) {  // 合并 child 所在集合到 parent 所在集合
    p[FindSet(child)] = p[FindSet(parent)];
  }

  int SetCount() const {
    int res = 0;
    for (int i = 0; i < size(p); ++i) {
      if (p[i] == i) {
        ++res;
      }
    }
    return res;
  }

  void PrintAllSet() const {
    for (int i = 0; i < size(p); ++i) {
      cout << FindSet(i) << ' ';
    }
    cout << endl;
  }

 private:
  vector<int> p;
};

int main() {
  DisjointSetUnion dsu;
  dsu.MakeSet(5);               // 初始化为 5 个集合
  dsu.PrintAllSet();            // 0 1 2 3 4
  dsu.Union(0, 1);              // 将 1 所在集合合并到 0 所在集合
  dsu.PrintAllSet();            // 0 0 2 3 4
  dsu.Union(2, 3);              // 将 3 所在集合合并到 2 所在集合
  dsu.PrintAllSet();            // 0 0 2 2 4
  dsu.Union(1, 4);              // 将 4 所在集合合并到 1 所在集合
  dsu.PrintAllSet();            // 0 0 2 2 0
  dsu.Union(3, 4);              // 将 4 所在集合合并到 3 所在集合
  dsu.PrintAllSet();            // 2 2 2 2 2
  assert(dsu.SetCount() == 1);  // 共 1 个集合
}

解法如下

class Solution {
 public:
  int numIslands(vector<vector<char>>& grid) {
    if (empty(grid) || empty(grid[0])) {
      return 0;
    }
    int m = size(grid);
    int n = size(grid[0]);
    vector<int> p{MakeSet(m * n)};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int t = i * n + j;  // 二维坐标转为一维
        if (i + 1 < m && grid[i][j] == grid[i + 1][j]) {
          Union(p, t, t + n);  // 合并下
        }
        if (j + 1 < n && grid[i][j] == grid[i][j + 1]) {
          Union(p, t, t + 1);  // 合并右
        }
      }
    }
    int res = 0;
    for (int i = 0; i < size(p); ++i) {
      if (p[i] == i && grid[i / n][i % n] == '1') {
        ++res;
      }
    }
    return res;
  }

 private:
  vector<int> MakeSet(int n) {
    vector<int> res(n);
    iota(begin(res), end(res), 0);
    return res;
  }

  int FindSet(vector<int>& p, int i) {
    while (p[i] != i) {
      i = p[i];
    }
    return i;
  }

  void Union(vector<int>& p, int parent, int child) {
    p[FindSet(p, child)] = p[FindSet(p, parent)];
  }
};

并查集空间复杂度为 O(n)，MakeSet 摊还代价为 O(1)，如果使用路径压缩（查询时，把被查询节点到根节点路径上所有节点的父节点设为根节点）和按秩合并（合并时比较两棵树的秩的大小，将较大树的根节点作为合并后的根节点，单元素集合的秩为 0，秩不同的两棵树合并，新树的秩为原来的较大者，秩相同的两棵树合并，新树的秩为原来的秩加一）优化，Find 和 Union 的摊还代价为 O(α(n))，其中 α 为反阿克曼函数
阿克曼函数是一个递归函数

A(0, n) = n + 1 for n ≥ 0
A(m, 0) = A(m - 1, 1) for m > 0
A(m, n) = A(m - 1, A(m, n - 1)) for m, n > 0

更直观地用 Haskell 定义如下

ack :: (Num a, Eq a) => a -> a -> a
ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))

阿克曼函数的函数值表为

m\n	0	1	2	3	4	n
0	1	2	3	4	5	n + 1
1	2	3	4	5	6	n + 2
2	3	5	7	9	11	2 * (n + 3) - 3
3	5	13	29	61	125	2 ^ (n + 3) - 3
4	13	65533	2 ^ 65536 - 3	2 ^ 2 ^ 65536 - 3	2 ^ 2 ^ 2 ^ 65536 - 3	2 ^ 2 ^ 2 ^ 2 ^ … - 3（共 n + 3 个 2）
5	65533	A(4, 65533)	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3)	A(4, A(5, n - 1))
6	A(5, 1)	A(5, A(5, 1))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))	A(5, A(6, n - 1))

函数 f(n) = A(n, n) 的增速极快，因此其反函数 α(n) 的增速极慢，对于实际使用的 n，α(n) 不会超过 4