并查集是合并集合的方式,对于一些关联性的集合,合并查询的方式可以使得题目分类处理,是一种题型的解决方案,这里最关键是构思好集合之间的关联关系;
在这一 part 中,仅仅只是对部分题做了了解学习,远远没有达到可以手撕的程度,但是面试过程中遇到的并不算特别多,所以属于一个了解补充的 part,大家可以学习学习,还是挺有意思的;
下一 part 做分治法
这是一篇水文,国庆回家也就坚持每天做一丢丢题目,然后保持一下手感,而并查集确实比较好的锻炼一下脑子,脑子不够转不过来,所以可以尝试学习并做一下,他的基本模板不会很复杂,基本如下:
class UnionFind {
constructor(n){
// 缓存两个数组,父节点数组和当前节点的子节点数量数组
// 1. 初始化的父节点数组都是指向自己当前的下标的; -- 其中下标是唯一值
this.parents = new Array(n).fill(1).map((_,index) => index)
// 2. 初始化的子节点数量数组都是只有一个;-- 其中下标是唯一值
this.sizes = new Array(n).fill(1) //
}
// 寻找 x 的根节点
find(x){
if(this.parents[x] === x) return x
return this.find(this.parents[x])
}
// 合并两个并查集
connect(x,y){
const px = this.find(x)
const py = this.find(y)
if(px === py) return // 如果他们是一个集合,则直接返回
if(this.sizes[px]>this.sizes[py]){
// px 挂的节点更多,所以将 py 也挂过来
this.parents[py] =px
this.sizes[px]++
}else{
this.parents[px] =py
this.sizes[py]++
}
}
}
当然,具体问题上,可能可以简化或者强化 connect 方法,来解决具体的问题,这就需要同学自己去学习探讨了;
最后将几道例题奉上,节日结束,继续搬砖吧;
参考视频:传送门
分析
var findCircleNum = function(isConnected) {
const len = isConnected.length
const parents = Array.from(isConnected).map((_,index) => index) // 指向自己
for(let i = 0;i<len;i++){
for(let j=0;j<len;j++){
if(isConnected[i][j] === 1){
_connect(i,j) // 将 i, j 合并
}
}
}
return parents.filter((item,index) => item === index).length //筛选出根节点
function _connect(x,y) {
parents[_find(x)] = _find(y)
}
function _find(x){
if(parents[x] ===x) return x
return _find(parents[x])
}
}
// 标准类写法
class UnionFind {
constructor(n){
// 缓存两个数组,父节点数组和当前节点的子节点数量数组
// 1. 初始化的父节点数组都是指向自己当前的下标的; -- 其中下标是唯一值
this.parents = new Array(n).fill(1).map((_,index) => index)
// 2. 初始化的子节点数量数组都是只有一个;-- 其中下标是唯一值
this.sizes = new Array(n).fill(1) //
}
// 寻找 x 的根节点
find(x){
if(this.parents[x] === x) return x
return this.find(this.parents[x])
}
// 合并两个并查集
connect(x,y){
const px = this.find(x)
const py = this.find(y)
if(px === py) return // 如果他们是一个集合,则直接返回
if(this.sizes[px]>this.sizes[py]){
// px 挂的节点更多,所以将 py 也挂过来
this.parents[py] =px
this.sizes[px]++
}else{
this.parents[px] =py
this.sizes[py]++
}
}
}
var findCircleNum = function(isConnected) {
const len = isConnected.length
const unions = new UnionFind(isConnected.length)
for(let i = 0;i<len;i++){
for(let j=0;j<len;j++){
if(isConnected[i][j] === 1){
unions.connect(i,j) // 将 i, j 合并
}
}
}
console.log(unions)
return new Set(unions.parents).size
}
分析
var accountsMerge = function(accounts) {
const email_index_map=new Map()
const email_name_map=new Map()
let emailIndex = 0 // 设置下标,作为唯一标识 -- 也代表了 emails 的数量
for (let i = 0; i < accounts.length; i++) {
const account = accounts[i];
const name = account[0]
for(let i = 1;i<account.length;i++){
const email = account[i]
if(!email_index_map.has(email)){
email_index_map.set(email,emailIndex)
email_name_map.set(email,name)
emailIndex++
}
}
}
const parents = Array.from({length:emailIndex}).map((_,index) => index)
function _find(x){
if(parents[x]=== x) return x
return _find(parents[x])
}
function _connect(x,y) {
const px = _find(x)
const py = _find(y)
parents[py] = px // 让 py 指向 py
}
// 开始使用并查集,将同一个用户下 email 连接起来
for (let i = 0; i < accounts.length; i++) {
const firstEmail = accounts[i][1];
const firstIndex = email_index_map.get(firstEmail);
for(let j = 2;j<accounts[i].length;j++){
const secondEmail = accounts[i][j];
const secondIndex = email_index_map.get(secondEmail);
_connect(firstIndex,secondIndex)
}
}
// 现在每一个 email 的关联关系都通过 index 连接好了,现在需要用一个数据结构将他们取出来
// 这 key 值是根 emailIndex, values 就是这个集合的 emails
const index_email_map = new Map()
for(let email of email_index_map.keys()) {
const emailIndex = email_index_map.get(email)
const root = _find(emailIndex)
index_email_map.set(root,index_email_map.has(root)? [...index_email_map.get(root),email]:[email])
}
const merge = []
for(let emailsArr of index_email_map.values()){
emailsArr.sort();
const name = email_name_map.get(emailsArr[0])
merge.push([name,...emailsArr])
}
return merge
}
分析
var minMalwareSpread = function (graph, initial) {
const len = graph.length;
const union = new UnionFind(len);
for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
if (graph[i][j] === 1) {
union.connect(i, j);
}
}
}
// 感染源触发的根节点状态map,key 是感染源的根节点,value 是出现次数
const injectedMap = new Map();
initial.forEach(node=> {
const root = union.find(node)
injectedMap.set(root,injectedMap.get(root)?injectedMap.get(root)+1:1)
})
let maxSize = 0; // 符合要求的的集合的数量
let ret = -1
initial.forEach(node => {
// 找出感染源的根节点
const root = union.find(node)
// 找出感染源的根节点出现次数, -- 超出2个源头,就没有删除的效果了
const count = injectedMap.get(root)
if(count === 1){
const size = union.sizes[root] // 看一下子节点有多少个
if(size>maxSize || (size === maxSize && node<ret)){
ret = node
maxSize = size
}
}
})
// 如果 ret === -1, 则随便删除一个节点,结果都是一样的,那么就删除其中最小的那个就好了
if(ret === -1) return Math.min(...initial)
return ret
};
class UnionFind {
constructor(len) {
this.parents = Array.from({ length: len }).map((_, index) => index);
this.sizes = new Array(len).fill(1);
}
find(x) {
if (x === this.parents[x]) return x;
return this.find(this.parents[x]);
}
connect(x, y) {
const px = this.find(x);
const py = this.find(y);
if (px === py) return;
if (this.sizes[px] > this.sizes[py]) {
this.parents[py] = px;
this.sizes[px] += this.sizes[py];
} else {
this.parents[px] = py;
this.sizes[py] += this.sizes[px];
}
}
}
分析
var makeConnected = function (n, connections) {
const len = connections.length // 网络连接数
if(len <n -1) return -1 // 如果len 小于 n-1
const parents = Array.from({length:n}).map((_,index) => index)
const _find= (x) => {
if( x !== parents[x]){
parents[x] = _find(parents[x])
}
return parents[x]
}
let sizes = n
const _connect = (x,y) => {
const px= _find(x)
const py= _find(y)
if(px===py) return
parents[px] = py
sizes--
}
for(let con of connections){
_connect(con[0],con[1]) // 连接起来
}
return sizes-1
}
分析 -- 超时了
var smallestStringWithSwaps = function (s, pairs) {
const parents = Array.from({ length: s.length }).map((_, index) => index);
const root_strArr = Array.from({ length: s.length }).map((_, index) => [s[index].charCodeAt()]);
const _find = (x) => {
if (x !== parents[x]) {
parents[x] = _find(parents[x]);
}
return parents[x];
};
const _connect = (x, y) => {
const px = _find(x);
const py = _find(y);
if (px === py) return;
if (root_strArr[px].length > root_strArr[py].length) {
parents[py] = px;
root_strArr[px] = _connectTwoArr(root_strArr[px],root_strArr[py])
} else {
parents[px] = py;
root_strArr[py]=_connectTwoArr(root_strArr[px],root_strArr[py])
}
};
// 合并两个有序数组
const _connectTwoArr = (xArr,yArr) => {
const xLen = xArr.length
const yLen = yArr.length
let x = y = 0
const ret = []
while(x<xLen && y<yLen){
if(xArr[x]>yArr[y]){
ret.push(yArr[y])
y++
}else{
ret.push(xArr[x])
x++
}
}
while(x<xLen) {
ret.push(xArr[x])
x++
}
while(y<yLen) {
ret.push(yArr[y])
y++
}
return ret
}
for (let p of pairs) {
_connect(p[0], p[1]);
}
let ret = "";
for (let i = 0; i < s.length; i++) {
const root = _find(i); // 看一下根节点
const arr = root_strArr[root]; // 找出这个根节点下的集合,并找出 字典下的最小字符
const minStr = String.fromCharCode(arr.shift());
ret += minStr;
}
return ret;
};
分析
var smallestStringWithSwaps = function (s, pairs) {
const parents = Array.from({ length: s.length }).map((_, index) => index);
const root_strArr = Array.from({ length: s.length }).map((_, index) => [s[index]]);
const _find = (x) => {
if (x !== parents[x]) {
parents[x] = _find(parents[x]);
}
return parents[x];
};
const _connect = (x, y) => {
const px = _find(x);
const py = _find(y);
if (px === py) return;
if (root_strArr[px].length > root_strArr[py].length) {
parents[py] = px;
root_strArr[px].push(...root_strArr[py])
} else {
parents[px] = py;
root_strArr[py].push(...root_strArr[px])
}
};
// 连接
for (let p of pairs) {
_connect(p[0], p[1]);
}
// 各个模块排序
root_strArr.map(arr => arr.sort());
let ret = "";
for (let i = 0; i < s.length; i++) {
const root = _find(i); // 看一下根节点
const arr = root_strArr[root]; // 找出这个根节点下的集合,并找出 字典下的最小字符
const minStr = arr.shift()
ret += minStr;
}
return ret;
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。