8.29 - 高算2

这节课讲了两种数据结构，Trie和并查集。并查集的作用在不考虑顺序，只考虑集合的情况，可以增加边，不可以减少边的情况。find和union的操作都是O(1)， Trie可以实现查询prefix和word，查询prefix是hashtable无法做到的。

并查集的模板

    def union(self, a, b):
        f1 = self.find(a)
        f2 = self.find(b)
        if f1 != f2:
            self.m[f2] = f1
    
    def find(self, n):
        if n == self.m[n]:
            return n
        self.m[n] = self.find(self.m[n])
        return self.m[n]

Trie的模板

class TrieNode:
  def __init__(self, c):
    self.c = c
    self.stop = False
    self.children = {}

class Trie:
  def __init__(self):
    self.root = TrieNode("")

  def insert(self, word):
      node = self.root
      for c in word:
          if c not in node.children:
              node.children[c] = TrieNode(c)
          node = node.children[c]
      node.stop = True

  def search(self, word):
      node = self.root
      for c in word:
          if c not in node.children:
              return False
          node = node.children[c]
      return node.stop

  def startsWith(self, prefix):
      node = self.root
      for c in prefix:
          if c not in node.children:
              return False
          node = node.children[c]
      return True

1. Number of Islands: 其实这道题用bfs，dfs和并查集都可以做。并查集的做法是先把如果某个元素的左或上有1元素的话，就做一次union，然后再数数有多少个boss

2. Connecting Graph：很直观的并查集，找到自己的boss，只是union的时候要注意顺序，把小一些的值做为union的father节点。

3. Connecting Graph II：和上一题类似，加一个size dict来记录每个boss的size就可以了

4. Connecting Graph III：和上一题类似，加一个全局count在union的时候不停的递减

5. Graph Valid Tree： 利用上一题的记录count的想法，valid tree要满足，所有节点都有一个boss，任何两个节点在做union之前不能有同一个boss（否则就会形成环）

6. Add and Search Word: 在search的时候用一个递归来做，其它都类似模板

7. Implement Trie： 见Trie模板

8. Find the Weak Connected Component in the Directed Graph：直接用并查集就可以了

9. Connected Component in Undirected Graph： 和上一题解法一模一样

10. Number of Islands II： 盘古开天地的操作，和第一题很类似，只是要搜索上下左右四个方向，并且把新出现的岛屿做为boss

11. Word search: 这题可以用backtracking来做

12. Word search II: 直接loop words再对每一个word用上面的解法就过不了了，TLE。 可以把words先变为Trie，然后针对Trie在进行backtracking，这样会减少运行时间。

13. Surrounded Regions: 类似第一题，只是要把边界上的0和其它地方的0区别对待（设为不同的boss），其实这题用bfs或者dfs应该很好做

14. Word Squares： 利用Trie来找到拥有某一个prefix的所有words，实现这样的操作就容易多了。