leetcoad208-实现Trie（前缀树）
N叉树：每个节点可能包含m-1个值且可以有m个子节点
B树：n叉树的一种特例，广泛用于磁盘的访问（还有其他的一些性质没有补充进来）
// 一般的多叉树的节点
struct TreeNode {
VALUETYPE value; //结点值
TreeNode* children[NUM]; //指向孩子结点
};
// 字典树的节点
struct TrieNode {
bool isEnd; //该结点是否是一个串的结束
TrieNode* next[26]; //字母映射表
};
解释：
- 先明白它的节点设计，TrieNode中没有直接保存字符值的数据或成员
- TrieNode* next[26]中保存了对当前节点而言下一个可能出现的所有字符的链接，可以通过父节点来预知它所有子节点的值
for (int i = 0; i < 26; i++) {
char ch = 'a' + i;
if (parentNode->next[i] == NULL) {
说明父结点的后一个字母不可为 ch
} else {
说明父结点的后一个字母可以是 ch
}
}
字典树：tire是一种 N 叉树，前缀树，字典树、单词查找树(更是一种哈系数的变种)
前缀树是N叉树的一种特殊形式。通常来说，一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。用于高效存储和检索字符串数据集中的键。
改变二叉树里面节点的存储方式，字典树每个节点不再是存放单词本身，而是把字符串拆成单个单个的字母
基本性质：
- 节点本身不存完整单词
- 从根节点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串
- 每个结点的所有子节点路径代表的字符都不相同。
核心思想： - 空间换时间
- 利用字符串的公共前缀来降低查询时间的开销达到提高效率的目的
应用场景：自动补充和拼音检查，统计、排序和保存大量的字符串（不仅限于字符串）[一次建树，多次查询]
优点：利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高
参考链接：https://blog.csdn.net/m0_46202073/article/details/107253959
方法一：采用哈希集合来解题：
前缀树里面有一个好大好大的字典：键：值，键：值….,键：值。其中值又可以切分成新的字典，不断的套娃实现字典树
# 这种最基本的方式是必须要完完全全掌握清楚的，然后形成自己的模板形式，记下来备用。
# 使用哈希表来构建
class Trie:
def __init__(self):
# 先构建一个字典
self.root={}
# 一个单词的结束字符,该路径是否形成了一个有效的字符串
self.isEnd = False
# 描述：插入一个字符
def insert(self, word: str) -> None:
# 先拷贝这个root结点
nownode = self.root
for s in word:
# 如果这个字母不在这个nownode字典里面，相当于没有创建链条来连接
if s not in nownode:
# 创建下一个结点
nownode[s]={}
# nownode指向下一个结点
nownode= nownode[s]
# 插入结束后，将，插入一个标识符，并将值改为：True
# 对于每插入一个字符串，都会在里面加入一个isend=True的键值对
nownode[self.isEnd] = True
# 描述：查找Trie中是否存在单词word
# 实现：从根节点的子节点开始，一直向下匹配，如果出现节点值为空就返回false，如果匹配到最后一个字符，只需判断 该字符是不是单词的末尾
def search(self, word: str) -> bool:
nownode = self.root
for s in word:
if s in nownode:
nownode= nownode[s]
else:
return False
# 看这个标识符是否在字典里面，如果在说明之前插入过这个
if self.isEnd in nownode:
return True
else:
return False
# 描述：判断Trie中是或有以prefix为前缀的单词
# 实现：和search的操作比较类似，只是不需要判断最后一个字符节点，能匹配到最后一个字符，那后面一定有单词是以它为前缀的
def startsWith(self, prefix: str) -> bool:
nownode = self.root
for s in prefix:
if s in prefix:
nownode = nownode[s]
else:
return False
return True
方法二：采用字典树解题：
对于search的实现：
- 采用一个布尔判断：判断是不是字符的末尾
- 或者用一个特殊的字符：在最后的时候加入一个结束符，每次走到最后的节点的时候，看有没有这样的一个结束符
# 采用字典树,建TrieNode结构结点
class TrieNode:
def __init__(self):
self.children = {}
self.isEnd = False
class Trie:
def __init__(self):
self.root = TrieNode()
# 描述：插入一个字符
def insert(self, word: str) -> None:
nownode= self.root
for s in word:
# 如果s不在任何一个分支上的话(不在nownode的孩子里面),也即没有一个字母是有的
if s not in nownode.children:
# 添加一个nownode.children[s]做成的Trie的形式
# 随着数据的不断插入，需要不断的创建TrieNode节点
nownode.children[s]=TrieNode()
nownode = nownode.children[s]
nownode.isEnd=True
# 描述：查找Trie中是否存在单词word
# 实现：从根节点的子节点开始，一直向下匹配，如果出现节点值为空就返回false，如果匹配到最后一个字符，只需判断 该字符是不是单词的末尾
def search(self, word: str) -> bool:
nownode=self.root
for s in word:
# 如果这个字母没有在nownode的子节点里面
if s not in nownode.children:
# 直接返回False
return False
# 如果在这个结点里面，就指向下一个结点
nownode= nownode.children[s]
# 返回终止符的标记。
# 如果最终的标识符是False，表明给定的单词实际上没有走完一个原本插入的路径，自然搜不到
# 如果最终的标识符是True，表明给定的单词走完了一个完整的路径，已经搜索到了。
return nownode.isEnd
# 描述：判断Trie中是或有以prefix为前缀的单词
# 实现：和search的操作比较类似，只是不需要判断最后一个字符节点，能匹配到最后一个字符，那后面一定有单词是以它为前缀的
def startsWith(self, prefix: str) -> bool:
nownode=self.root
for s in prefix:
if s not in nownode.children:
return False
nownode= nownode.children[s]
# 直接返回true即可
# 因为不需要标识符
return True
这两种方法进行比较的过程:
- 一个是采用哈希表的方法（不断的字典套字典的过程），一个是采用的构建字典树的方法
- 用isEnd这个标识符也不太一样，在哈希表里面就是一个键，它的值是False/True(单词末尾会变成True),在字典树里面，isEnd这个包含在TrieNode里面了
- 在search中的判断条件不一样：
leetcoad720-词典中的最长单词
这道题是自己和陈刚一起做过的一道，实际上自己提交的版本并没有把它真正的弄懂，弄清楚
暴力解题的思路：
- 单词必须最长，因此找出列表中最长的单词
- 单词必须由其它短的单词组成，因此要写个在长单词里找短单词的func set()的查询是O(1)的
- 找到符合要求的单词后按字典序排列
采用哈希集合的方式：
- 单词必须最长，且要按照字典序进行排序，因此找出列表中最长的单词，字符串长度按照降序排列，如果字符串相同，字典序按照升序排列（用到了排序的思想）
- 对排序后的字符进行一个个的遍历，对选定的某个字符进行切分至最末尾，查看切分的是否在集合内
- 返回第一个所有切分的字符都是集合里面（因为前面已经运用了贪心排序的思想，那样第一个就是题目要求的那一个）
# 方法一：采用哈希集合,这种方式是自己必须要掌握的形式。本地调试的过程很重要，相应的思路要深深的刻在自己的脑袋里面。
class Solution:
def longestWord(self, words: List[str]) -> str:
# 创建一个words的无序的无重复的set集合
words_set = set(words)
# print(words_set)
# 对words进行一个排序，其中key = lambda s:[-len(s), s]为排序的准则，有两个准则，
# 将字符串按从大到小的顺序排列，如果字符串长度相同的时候，按照x的大小按照从小到大的顺序排列（按照字典序进行排序）
# 如果能够满足单词是由一个个单词逐步添加一个字母而成的，就可以找到，有贪心的思想在里面，会特别的快 ，很可能第一个数就能够满足
words.sort(key = lambda s:[-len(s), s])
print('排序后的words为-->',words)
# 在排序好的words中进行遍历
for s in words:
for i in range(1, len(s)):
# 这里加入一行打印，主要是为了理解这里的过程
print(s[:i])
# 对于选定的s,判断从索引为0一直倒索引为i-1的字符是否在words_set这个集合中
if s[:i] not in words_set:
break
else:
return s
# 如果在整个过程中都没有找到，直接返回空字符串
return ""
# 头文件
if __name__ == '__main__':
# 输入一个特定的需要求解的数组
words=["w","wo","wor","worl","world"]
# words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
res = Solution().longestWord(words)
#print(res)
print(" 输出 => " ,res)
# 输出结果
# 主要是为了理解为什么要创建set集合：为了便于好定位
# {'wor', 'worl', 'world', 'wo', 'w'}
# 排序后的words为--> ['world', 'worl', 'wor', 'wo', 'w'](这里的排序按照字符串长度递减，字典序递增的方式)
# w
# wo
# wor
# worl
# 输出 => world
采用前缀树+DFS的方法
- 将所有单词插入trie，然后从trie进行深度优先搜索，每找到一个单词表示该单词的全部前缀均存在，我们选取长度最长的单词
- 在python中，我们使用defaultdict的方法
leetcoad211-添加与搜索单词-数据结构设计
采用的方法：字典树+DFS
理解题目的意思：设计一个数据结构，支持添加新单词和查找字符串是否与任何先前添加的字符串匹配，并且还有一个模糊查找的功能，也是这一题的难点所在。（这题没有这么简单，if嵌套的东西特别的多）
构建：
- 根节点不保存任何信息，保存chilldren是使用的字典，相应的保存结构是{字符：Node}
- 关键词放到「前缀树」时，需要把它拆成各个字符，每个字符按照字母表的顺序，放到children对应的位置。
- 一个字符串构建结束的时候，把该结点的endword 标记为True(这里有一个关键点：并不是达到叶子节点才形成一个关键字，只要endword是True就行)
附上一张图片辅助理解：c和cv都是加入的字符串，两个的endword都是True
对于’.’的处理：
在匹配的过程中，如果遇到’.’需要对当前结点的所有子树进行遍历，只要有任何一个子树能够最终完成匹配，那就代表能够匹配完成
对字典树和哈希集合+DFS有了深入的了解后再来回顾！！！！！
以下的算例没有通过。
# ["WordDictionary","addWord","addWord","addWord","addWord","search","search","addWord","search","search","search","search","search","search"]
# [[],["at"],["and"],["an"],["add"],["a"],[".at"],["bat"],[".at"],["an."],["a.d."],["b."],["a.d"],["."]]
并查集：Union Find
相关的系类题目：（牢牢理解并掌握）
- leetcoad128:最长连续的序列
- leetcoad130:被围绕的区域(**)
- leetcoad200:岛屿数量
- leetcoad547：省份数量
- leetcoad399:除法求值
- leetcoad695-岛屿的最大面积
参考链接：https://www.bilibili.com/video/BV1Q5411H7v5
union:合并两个元素为同一个根节点(将两个子集合并成同一个集合)
Find:找到某个和元素的根节点(可以被用来确定两个元素是否属于同一个子集，加入路径压缩，复杂度近乎O(1))
用于解决动态连通性的问题，能动态连接两个点，并判断两个点是否连通，处理元素的合并与查询问题,组团或配对的问题，任给两个人是不是朋友的问题
- 先初始化：count和parent ,其中parent[i]=i
- 如何寻找给定任何一个数p，怎么找它的集合是谁（如何找它集合和它集合的领头元素），不能用parent[p]=p,需要不断的向上找它的parent,直到parent[i]=i（数组的索引=索引对应的元素）,说明找到了它所在集合的领头元素
- 不断的把parent[p]赋给p本身的一个过程（不断的往上找parent，最后找到root的一个过程：p[root]==root）
- 把p它的爷爷节点直接赋给现在的parent[p]直接往上多窜了一层
- 如何进行union的操作
- 首先调用find找出它的p的集合所在的领头元素，找出来之后赋给rootP
- 另外的找q赋给rootQ
- 如果它们两个相等的话就不用管，如果相等的话，把其中一个rootP放在括号里面，或者两个替换一下：把rootP的parent弄成rootQ(反过来也行)，相当于把这两个集合合并在一起了。
- count–:里面独立的集合就减少一个（在最后输出后就表示有多少孤立的集合）
java的实现过程：
//用一个UnionFind类
class UnionFind{
//两个成员变量count和parent
private int count =0;
private int[] parent;
public UnionFind(int n){
//count初始化一个数组长度
count =n;
parent = new int[n];
for (int i =0;i<n;i++){
//数组parent初始：parent[i] = i,是指向指针的关系，和数组是相同的道理
parent[i] = i;
}
}
//接下来就是一个寻找的过程,给定任何一个数p,找它的集合的领头的过程
public int find(int p) {
while (p!=parent[p]){
// 不断的往上找parent的过程
// 把p爷爷的节点直接赋给现在的parent[p].,直接往上多窜了一层
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
// 如何进行union的合并操作，在上一步中调用find找到p的领头元素
// 把集合p q合并的一个过程
public void union(int p,int q){
// 找出p的领头元素赋给rootP
int rootP= find(p);
int rootQ= find(q);
// 如果两者相等直接返回
if （rootP==rootQ) return;
// 如果两者不相等的话，把rootP的parent弄成rootQ，将两个集合合并在一起了
parent[rootP]= rootQ;
// 里面的独立集合就减少了一个
count--;
}
}
python模板一：
# 初始化的过程
# for i =0...n:p[i]=i
def init(p):
# 每一个数，它的祖先都是它自己
p = [i for i in range(n)]
# parent代码，不断的去找p[root]的过程（就是find函数，换了一个名字好理解）
# 这一段代码也是比较抽象和晦涩难懂的一部分
# 其中p是一个集合，root既是索引也是值
def _parent(self,p,i):
# 把i赋给root,不断的找p[i]=i这件事，通过下面的代码找到它的root，root满足的条件就是p[root]==root
root = i
# 同java的版本一起理解，这里用两个while循环替换递归的操作（可能更好理解，本质上是一样的）
# 第一个循环终止条件：p[root]=root
while p[root] != root:
root = p[root]
# 第一个循环结束之后
# 路径压缩，把沿路上所有的parent[i]让它等于i，也可以不做，直接返回root(写了可以减少检索时间)
# 把原本间接与根节点相连的节点，让它与根直接相连
# 第二个循环终止条件：p[i]=i
while p[i] != i:
# 交换了一下，继续往上，再走
x ,i,p[x] = i,p[i],root
return root
# union的过程：把i和j对应的根节点p1和p2合并在一起的这样一个过程
def _union(self,p,i,j):
# 调用parent找到i和j的根节点
p1 = self._parent(p,i)
p2 = self._parent(p,j)
# 如果相等，表明i和j本来就是连在一起的
if p1==p2:
return
# 把p1的parent用p2赋值过去
p[p1]=p2
python模板二：
# 附上另外的一个python模板(辅助理解，代码的书写上有一些差别，但是个人感觉在理解之后写出来的会更加的清爽)
# 写一个UnionFind类，后面也是直接就拿来用的那种(这里题目的原型是岛屿的数量问题，加入了count变量)
# 这里定义了__init__方法，但是在后面没有将root传入进去，所以后面有用到root的地方都要用到self
# 这样对写代码提出了要求，但是阅读起来更加的直观，find就只用传入一个参数，union传入两个参数
class UnionFind:
def __init__(self,grid):
row=len(grid)
col=len(grid[0])
# 单个集合的个数
n=row*col
# 表明最初的孤立的集合数量为n个
# 后面随着不断地连通，相应的孤立集合就减少
self.count=n
# self.root=[i for i in range(n)]
# 如果觉得上面的初始化的方式不好理解，可以采用下面的方式
self.root=[-1]*n
for i in range(n):
self.root[i]=i
def find(self,p):
# 如果节点p正好和它对应的根节点相同
if p==self.root[p]:
return self.root[p]
else:
self.root[p]=self.find(self.root[p])
return self.root[p]
# 然后是union函数部分
def union(self,p,q):
# 分别调用find函数找到节点p和q的根节点
rootP=self.find(p)
rootQ=self.find(q)
# 如果它们的根节点不相同才需要合并（相同的时候不需要合并）
if rootP!=rootQ:
# 任取一个加入到另外一个上
root[rootP]=rootQ
# 一旦进行合并，孤立的集合就减少
self.count-=1
python模板二（优化）：
class UnionFind:
def __init__(self,grid):
row=len(grid)
col=len(grid[0])
# 看有多少个数
self.root = [-1]*(row*col)
self.count = row*col
for i in range(row*col):
self.root[i]=i
def find(self, p):
if x == self.root[p]:
return self.root[p]
else:
# 嵌套了一个小的递归函数，进行了Quick Find的优化过程
# 这里是需要重点理解
self.root[p] = self.find(self.root[p])
return self.root[p]
def union(self, p, q):
rootP = self.find(p)
rootQ = self.find(q)
# 当两个根节点不相同的时候具体应该怎么做的问题
if rootP != rootQ:
# P的根节点的权重大于Q的根节点的权重
if self.rank[rootP]>self.rank[rootQ]:
# 将Q的根节点改为P（把Q的部分黏到P下面）
root[rootQ]=rootP
elif self.rank[rootP]<self.rank[rootQ]:
root[rootP]=rootQ
# 两者的权重相同的时候
else:
# 将Q的根节点改为P
root[rootQ]=rootP
# 此时P的权重就要在之前的基础上+1
self.rank[rootP]+=1
这里也整理几道相对简单一点的并查集相关的题目练练手：
leetcoad128-最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
分析思路：
咋一看的时候，发现之前是有一道题叫：最长连续递增序列，两道题目描述的也不太一样，那道题条件要严格一些：最长+连续+递增，在这题里面原数组是不要求连续的，但是组成的序列最后是要连续的。常规的思路的话可以直接将该无序的数组进行排序，然后按照最长连续递增的思路求出来就行了。
- 找到一个数字之后，然后找到它的左边和右边，根据它左边和右边的长度来更新当前我循环到的值（更新我自己）
- 更新左边界和右边界的值（更新两头的边界值，这里是不太好理解的）
用最暴力的解法应该也是没有问标题的，这里虽然不符合题目的要求，但是针对学习的话一定是不错的。
主要是思维能力很重要，当然代码也很重要
以下为采用哈希表的代码：
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
res=0
# 新建一个哈希表，并理解哈希表中要存放的数字
# key：每个nums中的元素，value：包含当前key的连续区间的长度
hashmap=dict()
for num in nums:
# 新进来哈希表一个数
if num not in hashmap:
# 获取当前函数最左边的连续长度，没有的话就更新为0
left=hashmap.get(num-1,0)
# 获取右边的数
right=hashmap.get(num+1,0)
# 将当前数组加入哈希表代表当前数字出现过，任意值都是可以的
hashmap[num]=1
# 更新长度
length=left +1+ right
# 更新结果值
# res=max(res,length)
if length>res:
res=length
# 只更新端点值，中间的值是不需要处理的
# 更新最左端的值，如果left=n存在，那么证明当前的数的前n个都存在哈希表中
hashmap[num-left]=length
# 更新最右端点的值，如果right=n存在，那么证明当前数的后n个都存在哈希表中
hashmap[num+right]=length
# 此时[num-left,num-right]的值都连续存在哈希表中了
return res
if __name__=='__main__':
nums=[100,4,200,1,3,2]
res=Solution().longestConsecutive(nums)
print(res)
运用动态规划的思路也是可以求解的，解这道题的时候参考了 最长连续递增序列的动态规划的思路解法，在该方法的基础上，先进行排序，然后不断地更新dp数组地值，在更新的时候存在两个状态，后面的一个值与前面值相差1，第二种状态是后面的值与前面的值相等。其实也是很好理解。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# 先将序列排序
nums.sort()
n=len(nums)
maxlength=1
if n==0:
return 0
# 然后用最长连续递增子序列的思路来做，用到动态规划
dp=[1]*n
for i in range(1,n):
# 保证后面的数比前面的数大，而且要是连续的
if i>0 and nums[i]-nums[i-1]==1:
dp[i]=dp[i-1]+1
elif nums[i]==nums[i-1]:
dp[i]=dp[i-1]
if dp[i]>maxlength:
maxlength=dp[i]
return maxlength
本着学知识的态度，自己想用并查集的思路来解决这道题
最主要的是要找连续的序列：数字的连续就是相邻的两个元素相差1，这里就很巧妙的用到了并查集的思想：将最小的元素作为根节点，对于1 2 3 4 8 9 10这些元素来说，1就是2 3 4这些元素的根节点，8 就是9 10的根节点。也即所有在一个连续区间内的元素都会在一个连通的分量中，且这些元素的根节点都为最远的右边界元素。具体的思路如下：
- 遍历所有的元素，如果num+1存在，将num加入到num+1所在的连通分量中
- 重新遍历一遍所有的元素num，通过find函数找到num所在分量的根节点，也即最远的右边界，从而求得连续区间的长度
# 这种方法真的有点不好写，而且效率有点低
from collections import defaultdict
class UnionFind:
def __init__(self,nums):
self.parent={num:num for num in nums}
self.count=collections.defaultdict(lambda:1)
print(self.parent)
def find(self,x):
while x!=self.parent[x]:
x=self.parent[x]
self.parent[x]=self.parent[self.parent[x]]
return self.parent[x]
def union(self,p,q):
if q not in self.parent:
return 1
# 调用find函数找到对应的根节点
rootP,rootQ=self.find(p),self.find(q)
# 比较根节点
if rootP==rootQ:
return self.count[rootP]
# 如果根节点不相等的话需要，将任意一个加入另一个上面去
else:
self.parent[rootP]=rootQ
# 对应的以rootQ为根节点的序列长度会增加
self.count[rootQ]+=self.count[rootP]
return self.count[rootQ]
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums)==0:
return 0
res=1
uf=UnionFind(nums)
for num in nums:
res=max(res,uf.union(num,num+1))
return res
leetcoad-130被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
输入：board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]]
输出：[[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
自己的思维过程：如果用并查集应该具体怎么做？
有几个需要注意的地方：
- 被包围的区域不会存在于边界上，边界上的O要特殊的处理(读懂题目就是其中的一环)
- 只要把边界的O特殊处理了，剩下的O替换成X就可以了
- 问题转换为如何寻找和边界连通的O
先确定解题的思路（并查集）：这个思路很棒，十分巧妙而且合理，相当于把问题转化为最大岛屿的问题 - 当判断图中的两个点之间是否存在路径的时候，根据判断他们是否在一个连通区域内，这道题的本质：求解和边界的O在一个连通区域的问题
- 把所有边界上的O看成一个连通区域，遇到O就执行并查集的合并操作，所有的O会被分为两类：
- 和边界的 O在一个连通区域的，这些O需要保留
- 和边界的O不在一个连通区域的，这些O是被包围的，需要替换成X
- 将二维坐标转化为一维坐标
如果用深度优先搜索又应该怎么做的问题
leetcoad547-省份数量
没有重视这一题，发现自己在重新做的时候，问题还是有很多，其实题目应该是不难的，如果真的已经完全弄懂了。最开始的时候每个城市都属于不同的连通分量，在遍历矩阵的过程中，如果发现两个城市有相连的关系，则它们属于同一个连通分量，对它们进行合并，在遍历完之后，计算连通分量的总数就是省份的总数
# 写UnionFind模板的时候放在原类下面的情况
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
# 特殊情况
if not isConnected:
return 0
# n为城市的数量
n=len(isConnected)
# self.parent为一个特定的数组
self.parent=[i for i in range(n)]
# print(self.parent)
# 对数组进行遍历
for i in range(n):
for j in range(n):
# 如果发现isConnected[i][j]==1
if isConnected[i][j]==1:
# 需要将i和j合并
self.union(i,j)
# 最后要统计孤立的数量就需要用到set的去重操作
res=[self.find(i) for i in range(n)]
print(res)
print(self.parent)
return len(set(res))
# 以下为标准模板部分
# 构建find函数
# 并且采用递归的方式进行了相应的路径压缩
def find(self,x):
if self.parent[x]==x:
return x
else:
self.parent[x]=self.find(self.parent[x])
return self.parent[x]
# 构建union函数
def union(self,p,q):
# 通过调用find函数来找到p q的根节点
rootP,rootQ=self.find(p),self.find(q)
# 比较两个根节点
if rootP==rootQ:
return
# 如果两个根节点不相同，就需要进行相应的合并
# 将rootP连接到rootQ上面去
self.parent[rootP]=rootQ
leetcoad399:除法求值
题目描述：
给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
示例 1：
输入：equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0],
queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
示例 2：
输入：equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
输出：[3.75000,0.40000,5.00000,0.20000]
leetcoad695-岛屿的最大面积
题目描述：
给你一个大小为** m x n** 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
自己解析：
首先这个题目肯定是既可以用并查集也可以用深度优先搜索来解题的