208.实现Trie
题目链接：https://leetcode.com/problems/implement-trie-prefix-tree
解法：
这个题非常经典，背下来。
首先需要自己实现Node的类，属性为children和是否为单词的标记，再去初始化Trie的类。
在插入和查询的过程中，都要不断让指针指向children。
参考题解：实现Trie
边界条件：无
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_word = True
def search_prefix(self, word):
node = self.root
for c in word:
if c not in node.children:
return None
node = node.children[c]
return node
def search(self, word: str) -> bool:
node = self.search_prefix(word)
return node is not None and node.is_word
def startsWith(self, prefix: str) -> bool:
node = self.search_prefix(prefix)
return node is not None
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)54.螺旋矩阵
题目链接：https://leetcode.com/problems/spiral-matrix
解法：
顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。代码实现就是去模拟这个过程。
思路很直观，但是要处理好最后（最内部）的一个元素、一行或者一列，还是比较有讲究。如果循环时的边界处理不当，那么最内部的元素、一行或一列可能需要单独处理，这样就麻烦了。
按照以下的遍历顺序去处理，注意到从左到右和其他的三个方向不一样，从左到右把一行的所有元素都遍历了，而其他方向的遍历则少一个元素。这样却比较好处理最后的元素。
把代码运行一遍就理解了。
参考题解：螺旋矩阵
边界条件：
时间复杂度：O(mn)，其中 m和 n分别是输入矩阵的行数和列数
空间复杂度：O(1)
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
l, r, t, b = 0, len(matrix[0])-1, 0, len(matrix)-1
res = []
while True:
for i in range(l, r+1):
res.append(matrix[t][i])
# t要马上加1，因为下面的遍历是从下一行开始的
t += 1
if t > b: break
for i in range(t, b+1):
res.append(matrix[i][r])
r -= 1
if l > r: break
for i in range(r, l-1, -1):
res.append(matrix[b][i])
b -= 1
if t > b:break
for i in range(b, t-1, -1):
res.append(matrix[i][l])
l += 1
if l > r:
break
return res721.账户合并
题目链接：https://leetcode.com/problems/accounts-merge
解法：
并查集基础：图论——并查集(详细版)_哔哩哔哩_bilibili
并查集的代码是作为模板直接用的，有三个部分：初始化，查找父节点（寻根），合并。功能一般是用于查询两个节点是不是有相同的根（相同的集合中）。
一个容易理解的例子是：给出若干个pair对（张三和张五，李四和李六），pair对表示这俩人是亲戚关系，那么可以构建亲戚图谱（合并操作）。再给出一个pair对（张三和李六），问他们俩是不是亲戚（查询是否有相同的根）。
对于并查集的优化有路径压缩和按秩合并。路径压缩实现简单，这里只用了路径压缩。
具体实现直接看代码比较直观。
参考题解：并查集
边界条件：
时间复杂度：O(nlogn)，其中 n是不同邮箱地址的数量，logn 是路径压缩的复杂度。另外对邮箱排序的复杂度也是O(nlogn)文章来源：https://www.toymoban.com/news/detail-808128.html
空间复杂度：O(n)文章来源地址https://www.toymoban.com/news/detail-808128.html
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, idx):
# 查找idx的根节点
if self.parent[idx] != idx:
self.parent[idx] = self.find(self.parent[idx])
return self.parent[idx]
def union(self, idx1, idx2):
# 找到idx1和idx2的根节点，然后合并
root1 = self.find(idx1)
root2 = self.find(idx2)
self.parent[root1] = root2
class Solution:
def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
email_index = {}
email_name = {}
# 把email转化为idx，以便直接使用并查集的模板
for account in accounts:
name = account[0]
for email in account[1:]:
if email not in email_index:
email_index[email] = len(email_index)
email_name[email] = name
# 使用并查集合并邮箱
uf = UnionFind(len(email_index))
for account in accounts:
first_idx = email_index[account[1]]
for email in account[2:]:
next_idx = email_index[email]
uf.union(first_idx, next_idx)
# 把作为根节点的邮箱所连接的所有邮箱收集起来（包含本身）
idx_emails = defaultdict(list)
for email, idx in email_index.items():
root = uf.find(idx)
idx_emails[root].append(email)
# 添加name，获取结果
res = []
for emails in idx_emails.values():
res.append([email_name[emails[0]]] + sorted(emails))
return res到了这里，关于Grind75第13天 | 208.实现Trie、54.螺旋矩阵、721.账户合并的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
