資訊專欄INFORMATION COLUMN
摘要：實現(xiàn)這個想法之后就發(fā)現(xiàn)，時間復(fù)雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級，還有好多已經(jīng)說爛了的題就不分享了。如果有什么意見或者想法歡迎在評論區(qū)和我交流
題目
input:
n // 代表無向圖的頂點數(shù) // 從1開始
m // 無向圖的邊數(shù)
arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點0和頂點2相連，頂點3和頂點4相連）
arr2 // 希望求得的連通情況數(shù)組，形如[[1, 3], [1, 4], ...] （代表希望知道頂點1，頂點3的連通情況，頂點1和頂點4的連通情況）
output： num，arr2中可以連通的數(shù)量
示例： input:
n = 3
m = 1
arr1 = [[1, 3]]
arr2 = [[2, 3]]
output: 0
下面是我解決這個題的時候的思路
解題思路這個題，剛拿到的時候，我最初的想法是使用無向圖的鄰接矩陣，然后在檢查點的時候通過廣度優(yōu)先遍歷查看兩個點是否連通。實現(xiàn)這個想法之后就發(fā)現(xiàn)，時間復(fù)雜度真的太高了。每一次都會產(chǎn)生許多的無用查詢。
然后我想了另外一個思路，既然只查詢兩個點是否連通，那么我們維護一個連通集合不就可以了。一開始每一個孤立的點都是一個多帶帶的連通集合，形如["1", "2", "3", "4"]，在加上一條邊之后，就是該邊的兩個頂點所在的連通集合合并成同一個連通集合，即加上邊[1, 3]后，連通集合變成["13", "2", "4"]。這樣，在查詢的時候，去尋找頂點B是否在頂點A所處的連通集合里就可以了。于是我寫出了如下的代碼。
代碼function solution(n, m, arr1, arr2) {
let hash = new Array(n + 1) // 代表每個點的所在的連通集合,undefined代表這個點還不與其他點相連,0位無效
let map = {} // 保留每個聯(lián)通集合的點集
let index = 1 // 下一個聯(lián)通集合的編號
for (let i = 0; i < m; i++) { // 依次添加邊到連通集合里
let edge = arr1[i]
let A = edge[0] // 頂點A
let B = edge[1] // 頂點B
if (hash[A] === undefined && hash[B] === undefined) { // 這兩個都是孤立的點，新建一個連通集合
hash[A] = index
hash[B] = index
map[index++] = [A, B]
} else if (hash[B] === undefined) { // 點A不是孤立的，點B是孤立的，把B加入A的連通集合里
hash[B] = hash[A]
map[hash[A]].push(B)
} else if (hash[A] === undefined) { // 點B不是孤立的，點A是孤立的，把A加入B的連通集合里
hash[A] = hash[B]
map[hash[B]].push(A)
} else if (hash[A] !== hash[B]) { // A,B均不是孤立的，把B的連通集合,加入A的連通集合里
B_list = map[hash[B]] // B所在的連通集合的頂點列表
group = hash[A]
for (let i = B_list.length - 1; i >= 0; i--) { // 每個頂點的連通集合修改為A的
hash[B_list[i]] = group
}
map[group] = map[group].concat(map[hash[B]])
delete map[hash[B]]
}
}
let result = 0 // 連通的數(shù)量
for (let i = arr2.length - 1; i >= 0; i--) {
let test = arr2[i]
let groupA = hash[test[0]]
let groupB = hash[test[1]]
if (groupA && groupB && groupA === groupB) {
result++
}
}
return result
}
也就是，用hash來存放對應(yīng)的點所在的連通集合，map存放連通集合對應(yīng)的點。
本期算法小分享就到這里咯（leetcode剛做完探索里的初級，還有好多已經(jīng)說爛了的題就不分享了。）如果有什么意見或者想法歡迎在評論區(qū)和我交流
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/94559.html
摘要：題目中的數(shù)字可以分割出來的連續(xù)數(shù)字串的所有組合，不同組合之間用一個和連接示例和和和和和和和和和和這里給同學(xué)提個醒。。解題思路利用二叉樹。說到這這個題就很容易解決了，利用二叉樹的層次遍歷，每一層遍歷的時候都基于上一層的遍歷結(jié)果生成答案。 題目 input: noutput: 1...n中的數(shù)字可以分割出來的連續(xù)數(shù)字串的所有組合，不同組合之間用一個和連接 示例：input: 3output...
摘要：樹的前序，中序遍歷的結(jié)構(gòu)如下圖可以看出，通過前序遍歷可以確定根節(jié)點，再通過中序遍歷和根節(jié)點的位置可以確定出左子樹和右子樹。另外左子樹的前序遍歷和中序遍歷的順序跟在其父樹中的順序一樣。因此可以確定有一種遞歸解法。 從前序與中序遍歷序列構(gòu)造二叉樹 今天帶來的是Leetcode上的一個經(jīng)典題：從前序與中序遍歷序列構(gòu)造二叉樹原題干： /** Definition for a binary ...
摘要：算法的確有他獨特的魅力。然后我在做這個題的時候，其實也用到了類似質(zhì)因數(shù)分解，只是其實我們可以更好的利用到因數(shù)這一個特性。判斷一個數(shù)是否是質(zhì)數(shù)質(zhì)數(shù)列表一開始我們認為每一個數(shù)都可能是自身的冪線性篩為質(zhì)數(shù)遍歷質(zhì)數(shù)列表為質(zhì)數(shù)的冪 前言 從三月份到現(xiàn)在，大大小小筆試了十幾家公司（主要是因為一直solo code，沒人內(nèi)推），然后也能感覺到自己的進步把。從編程題只能ac一題到后來的ak。今天面騰訊...
閱讀 3758·2021-10-11 10:58
閱讀 2302·2021-10-08 10:05
閱讀 2124·2021-09-27 13:34
閱讀 3641·2019-08-30 15:53
閱讀 2789·2019-08-30 14:02
閱讀 3621·2019-08-29 16:55
閱讀 699·2019-08-29 15:41
閱讀 1231·2019-08-29 15:23
