[TOC]
基礎(chǔ)知識(shí)
https://labuladong.gitee.io/algo/2/22/53/
https://leetcode.cn/circle/discuss/qmjuMW/
B站上古城算法講的也很不錯(cuò)；
并查集是一種樹形的數(shù)據(jù)結(jié)構(gòu)，用于處理不交集的合并（union）和查詢（find）問題
Find：確認(rèn)元素屬于哪一個(gè)子集，確認(rèn)兩個(gè)元素是不是同一個(gè)子集
Union：將兩個(gè)子集合并為同一個(gè)集合
找到root parent，也就是根父母
比如：
TreeNode1 := TreeNode{Val:3,Left: &TreeNode{1, nil, nil},Right: &TreeNode{2,nil, nil }}
3是root，3的parent=3，1和2的parent=3
TreeNode2 := TreeNode{Val:4,Left: &TreeNode{5, nil, nil},Right: nil}
4是root，4的parent=4，5的parent=4
union(1,5)=> 找到1的root parent=3，找到5的root parent=4, 也就是3做4的孩子，或者3做4的父母，都可以，合并兩個(gè)子集。
基礎(chǔ)模板偽代碼
初始化
func makeSet(x)
x.parent=x
查詢
func Find(x)
if x.parent==x{return x}
else return Find(x.parent)
合并（找到root parent，然后其中一個(gè)root parent做另外一個(gè)的kid）
func Union(x,y)
xRoot:=Find(x)
yRoot:=Find(y)
x.Root.parent=yRoot
基礎(chǔ)模板
type UF struct {
count int
parent []int
}
// 并查集模板
func NewUF(x int) *UF {
u := UF{
count: x,
parent: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
}
return &u
}
// 查詢,找root parent
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
// 合并普通版
func (u *UF) Union_simple(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
// (可選)判斷兩個(gè)節(jié)點(diǎn)有沒有連接
func (u *UF) Connected(a, b int) bool {
return u.Find(a) == u.Find(b)
}
//（可選），其實(shí)一般都直接是u.count
func (u *UF) Count() int {
return u.count
}
//（可選）
func (u *UF) Add() {
u.count++
}
weight優(yōu)化模板
type UF_weight struct {
count int
parent []int
weight []int
}
// 并查集模板
func NewUF_weight(x int) *UF_weight {
u := UF_weight{
count: x,
parent: make([]int, x),
weight: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
u.weight[i] = 1
}
return &u
}
// 查詢,找root parent
func (u *UF_weight) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
// 合并優(yōu)化版，利用weight
func (u *UF_weight) Union_weight(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
if u.weight[rootA] < u.weight[rootB] {
u.parent[rootA] = rootB
u.weight[rootB] += u.weight[rootA]
} else {
u.parent[rootB] = rootA
u.weight[rootA] += u.weight[rootB]
}
u.count--
}
//（可選）判斷兩個(gè)節(jié)點(diǎn)有沒有連接
func (u *UF_weight) Connected(a, b int) bool {
return u.Find(a) == u.Find(b)
}
//（可選）
func (u *UF_weight) Count() int {
return u.count
}
//（可選）
func (u *UF_weight) Add() {
u.count++
}
rank優(yōu)化模板
type UF_rank struct {
count int
parent []int
rank []int
}
// 并查集模板
func NewUF_rank(x int) *UF_rank {
u := UF_rank{
count: x,
parent: make([]int, x),
rank: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
u.rank[i] = 1
}
return &u
}
// 查詢,找root parent
func (u *UF_rank) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
// 合并優(yōu)化版，利用rank
func (u *UF_rank) Union_rank(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
if u.rank[rootA] < u.rank[rootB] {
u.parent[rootA] = rootB
} else if u.rank[rootA] > u.rank[rootB] {
u.parent[rootB] = rootA
} else { // 只有rank相等的情況下合并后才需要維護(hù)rank，rank需要+1
u.parent[rootA] = rootB
u.rank[rootB]++
}
u.count--
}
// （可選）判斷兩個(gè)節(jié)點(diǎn)有沒有連接
func (u *UF_rank) Connected(a, b int) bool {
return u.Find(a) == u.Find(b)
}
//（可選）
func (u *UF_rank) Count() int {
return u.count
}
//（可選）
func (u *UF_rank) Add() {
u.count++
}
字符串模板（可參考737題）
// ======================= 以下這個(gè)模板也比較經(jīng)典，是和string有關(guān)的（注意要記?。? =========================
type UF struct {
count int
parent map[string]string
}
func NewUF(x int, sentence1 []string, sentence2 []string) *UF {
u := UF{
count: x,
parent: make(map[string]string, x), //這個(gè)是核心
}
for i := 0; i < x; i++ {
u.parent[sentence1[i]] = sentence1[i]
u.parent[sentence2[i]] = sentence2[i]
}
return &u
}
func (u *UF) Find(x string) string {
if strings.Compare(u.parent[x], x) != 0 { // u.parent[x]==x,strings.Compare結(jié)果=0
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
func (u *UF) Union(a, b string) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
func (u *UF) Connected(a, b string) bool {
return u.Find(a) == u.Find(b)
}
Leetcode刷題
323. 無向圖中連通分量的數(shù)目（會(huì)員/中等）
你有一個(gè)包含 n 個(gè)節(jié)點(diǎn)的圖。給定一個(gè)整數(shù) n 和一個(gè)數(shù)組 edges ，其中 edges[i] = [ai, bi] 表示圖中 ai 和 bi 之間有一條邊。
返回 圖中已連接分量的數(shù)目 。
輸入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
輸出: 2
輸入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
輸出: 1
func main() {
n := 5
edges := [][]int{{0, 1}, {1, 2}, {3, 4}}
fmt.Println(countComponents(n, edges))
}
func countComponents(n int, edges [][]int) int {
obj := NewUF(n)
for _, v := range edges {
obj.Union(v[0], v[1])
}
return obj.count
}
type UF struct {
parent []int
count int
}
func NewUF(x int) *UF {
parent := make([]int, x)
for i := 0; i < x; i++ {
parent[i] = i
}
count := x
return &UF{parent: parent, count: count}
}
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
func (u *UF) Union(a, b int) {
rootA := u.Find(a)
rootB := u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
547. 省份數(shù)量（中等）
有 n 個(gè)城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。省份 是一組直接或間接相連的城市，組內(nèi)不含其他沒有相連的城市。
給你一個(gè) n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個(gè)城市和第 j 個(gè)城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。返回矩陣中 省份 的數(shù)量。
輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2
// 這一題很明顯需要用并查集來做，而不是利用200題島嶼數(shù)量的DFS來套用，雖然可以用DFS來解題，但是需要變化。
func findCircleNum(isConnected [][]int) (ans int) {
n := len(isConnected)
obj := NewUF(n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if isConnected[i][j] == 1 {
obj.Union_simple(i, j)
}
}
}
return obj.count
}
type UF struct {
count int
parent []int
}
// 并查集模板
func NewUF(x int) *UF {
u := UF{
count: x, // 與模板不一樣的地方：初始沒有島嶼(題目要求初始都是海)
parent: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
}
return &u
}
// 查詢,找root parent
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
// 合并普通版
func (u *UF) Union_simple(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
305. 島嶼數(shù)量 II(會(huì)員/困難)
給你一個(gè)大小為 m x n 的二進(jìn)制網(wǎng)格 grid 。網(wǎng)格表示一個(gè)地圖，其中，0 表示水，1 表示陸地。最初，grid 中的所有單元格都是水單元格（即，所有單元格都是 0）?？梢酝ㄟ^執(zhí)行 addLand 操作，將某個(gè)位置的水轉(zhuǎn)換成陸地。給你一個(gè)數(shù)組 positions ，其中 positions[i] = [ri, ci] 是要執(zhí)行第 i 次操作的位置 (ri, ci) 。返回一個(gè)整數(shù)數(shù)組 answer ，其中 answer[i] 是將單元格 (ri, ci) 轉(zhuǎn)換為陸地后，地圖中島嶼的數(shù)量。島嶼 的定義是被「水」包圍的「陸地」，通過水平方向或者垂直方向上相鄰的陸地連接而成。你可以假設(shè)地圖網(wǎng)格的四邊均被無邊無際的「水」所包圍。
輸入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
輸出：[1,1,2,3]
解釋：
起初，二維網(wǎng)格 grid 被全部注入「水」。（0 代表「水」，1 代表「陸地」）
- 操作 #1：addLand(0, 0) 將 grid[0][0] 的水變?yōu)殛懙?。此時(shí)存在 1 個(gè)島嶼。
- 操作 #2：addLand(0, 1) 將 grid[0][1] 的水變?yōu)殛懙?。此時(shí)存在 1 個(gè)島嶼。
- 操作 #3：addLand(1, 2) 將 grid[1][2] 的水變?yōu)殛懙?。此時(shí)存在 2 個(gè)島嶼。
- 操作 #4：addLand(2, 1) 將 grid[2][1] 的水變?yōu)殛懙?。此時(shí)存在 3 個(gè)島嶼。
[圖片上傳失敗...(image-943ace-1671479296836)]
func main() {
m := 3
n := 3
positions1 := [][]int{{0, 0}, {0, 1}, {1, 2}, {2, 1}}
fmt.Println(numIslands2_personal(m, n, positions1))
positions2 := [][]int{{0, 0}, {0, 1}, {1, 2}, {1, 2}}
fmt.Println(numIslands2_personal(m, n, positions2))
}
func numIslands2_personal(m int, n int, positions [][]int) []int {
u := NewUF(m * n) // 構(gòu)造函數(shù)
grid := make([][]int, m)
for i := 0; i < m; i++ {
grid[i] = make([]int, n)
}
var res []int
var inGrid = func(x, y int) bool {
return x >= 0 && y >= 0 && x < m && y < n
}
dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
for _, p := range positions {
x, y := p[0], p[1]
index := x*n + y // 用 index=x?n+y 表示 (x,y) 這個(gè)點(diǎn)。
// 這一段用來干嘛的，主要是判斷輸入有沒有重復(fù)的，重復(fù)的可以直接返回結(jié)果，比如 positions2 := [][]int{{0, 0}, {0, 1}, {1, 2}, {1, 2}}
if grid[x][y] == 1 {
res = append(res, u.Count())
continue
}
grid[x][y] = 1 // 填島嶼了
u.Add()
for _, v := range dirs {
newRow := x + v[0]
newCol := y + v[1]
Index := newRow*n + newCol
if inGrid(newRow, newCol) && grid[newRow][newCol] == 1 && !u.Connected(index, Index) { // 如果其中一個(gè)方向有已經(jīng)填過的島嶼，且沒有連接在一起,那么就可以將填海位置與已經(jīng)填過的島嶼連接在一起，同時(shí)孤島數(shù)量-1(在Union里面自動(dòng)做掉)
u.Union_weight(index, Index)
}
}
res = append(res, u.Count())
}
return res
}
func numIslands2(m int, n int, positions [][]int) []int {
u := NewUF(m * n) // 構(gòu)造函數(shù)
visited := make([]bool, m*n) // 二維變一維，這里最精髓的地方就是二維問題轉(zhuǎn)化為一維問題
var res []int
var inGrid = func(x, y int) bool {
return x >= 0 && y >= 0 && x < m && y < n
}
dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
for _, p := range positions {
x, y := p[0], p[1]
index := x*n + y // 用 index=x?n+y 表示 (x,y) 這個(gè)點(diǎn)。
// 這一段用來干嘛的，主要是判斷輸入有沒有重復(fù)的，重復(fù)的可以直接返回結(jié)果，比如 positions2 := [][]int{{0, 0}, {0, 1}, {1, 2}, {1, 2}}
if visited[index] {
res = append(res, u.Count())
continue
}
visited[index] = true // 填島嶼
u.Add()
for _, v := range dirs {
newRow := x + v[0]
newCol := y + v[1]
Index := newRow*n + newCol
if inGrid(newRow, newCol) && visited[Index] && !u.Connected(index, Index) { // 如果其中一個(gè)方向有已經(jīng)填過的島嶼，且沒有連接在一起,那么就可以將填海位置與已經(jīng)填過的島嶼連接在一起，同時(shí)孤島數(shù)量-1(在Union里面自動(dòng)做掉)
u.Union_weight(index, Index)
}
}
res = append(res, u.Count())
}
return res
}
// ============ 以下是并查集模板 =========================
type UF struct {
count int
parent []int
weight []int
}
// 并查集模板
func NewUF(x int) *UF {
u := UF{
count: 0, // 與模板不一樣的地方：初始沒有島嶼(題目要求初始都是海)，這里初始化需要注意下
parent: make([]int, x),
weight: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
u.weight[i] = 1 // 這里初始化的weight也要注意，是1，不是i
}
return &u
}
// 查詢,找root parent
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
// 合并優(yōu)化版，利用weight
func (u *UF) Union_weight(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
if u.weight[rootA] < u.weight[rootB] {
u.parent[rootA] = rootB
u.weight[rootB] += u.weight[rootA]
} else {
u.parent[rootB] = rootA
u.weight[rootA] += u.weight[rootB]
}
u.count--
}
// 判斷兩個(gè)節(jié)點(diǎn)有沒有連接
func (u *UF) Connected(a, b int) bool {
return u.Find(a) == u.Find(b)
}
func (u *UF) Count() int {
return u.count
}
func (u *UF) Add() {
u.count++
}
1101. 彼此熟識(shí)的最早時(shí)間（會(huì)員/中等）
在一個(gè)社交圈子當(dāng)中，有 n 個(gè)人。每個(gè)人都有一個(gè)從 0 到 n - 1 的唯一編號(hào)。我們有一份日志列表 logs，其中 logs[i] = [timestampi, xi, yi] 表示 xi 和 yi 將在同一時(shí)間 timestampi 成為朋友。友誼是相互的。也就是說，如果 a 和 b 是朋友，那么 b 和 a 也是朋友。同樣，如果 a 和 b 是朋友，或者 a 是 b 朋友的朋友 ，那么 a 和 b 是熟識(shí)友。返回圈子里所有人之間都熟識(shí)的最早時(shí)間。如果找不到最早時(shí)間，就返回 -1 。
輸入：logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
輸出：20190301
解釋：
第一次結(jié)交發(fā)生在 timestamp = 20190101，0 和 1 成為好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次結(jié)交發(fā)生在 timestamp = 20190104，3 和 4 成為好友，社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次結(jié)交發(fā)生在 timestamp = 20190107，2 和 3 成為好友，社交朋友圈如下 [0,1], [2,3,4], [5].
第四次結(jié)交發(fā)生在 timestamp = 20190211，1 和 5 成為好友，社交朋友圈如下 [0,1,5], [2,3,4].
第五次結(jié)交發(fā)生在 timestamp = 20190224，2 和 4 已經(jīng)是好友了。
第六次結(jié)交發(fā)生在 timestamp = 20190301，0 和 3 成為好友，大家都互相熟識(shí)了。
輸入: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
輸出: 3
func main() {
logs := [][]int{
{20190101, 0, 1},
{20190104, 3, 4},
{20190107, 2, 3},
{20190211, 1, 5},
{20190224, 2, 4},
{20190301, 0, 3},
{20190312, 1, 2},
{20190322, 4, 5}}
N := 6
fmt.Println(earliestAcq(logs, N))
logs1 := [][]int{{9, 3, 0}, {0, 2, 1}, {8, 0, 1}, {1, 3, 2}, {2, 2, 0}, {3, 3, 1}}
N1 := 4
fmt.Println(earliestAcq(logs1, N1))
}
func earliestAcq(logs [][]int, n int) int {
obj := NewUF(n)
sort.Slice(logs, func(i, j int) bool { // 這里按照第一列進(jìn)行排序非常重要，因?yàn)椴灰欢〞r(shí)間先的放在數(shù)組前面了
return logs[i][0] < logs[j][0]
})
fmt.Println(logs)
for _, v := range logs {
obj.Union(v[1], v[2])
if obj.count == 1 {
return v[0]
}
}
return -1
}
type UF struct {
parent []int
count int
}
func NewUF(x int) *UF {
parent := make([]int, x)
for i := 0; i < x; i++ {
parent[i] = i
}
count := x
return &UF{parent: parent, count: count}
}
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
func (u *UF) Union(a, b int) {
rootA := u.Find(a)
rootB := u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
1135. 最低成本聯(lián)通所有城市（會(huì)員/中等）
想象一下你是個(gè)城市基建規(guī)劃者，地圖上有 n 座城市，它們按以 1 到 n 的次序編號(hào)。給你整數(shù) n 和一個(gè)數(shù)組 conections，其中 connections[i] = [xi, yi, costi] 表示將城市 xi 和城市 yi 連接所要的costi（連接是雙向的）。返回連接所有城市的最低成本，每對(duì)城市之間至少有一條路徑。如果無法連接所有 n 個(gè)城市，返回 -1. 該 最小成本 應(yīng)該是所用全部連接成本的總和。
輸入：n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
輸出：6
解釋：選出任意 2 條邊都可以連接所有城市，我們從中選取成本最小的 2 條。
輸入：n = 4, conections = [[1,2,3],[3,4,4]]
輸出：-1
解釋：即使連通所有的邊，也無法連接所有城市。
func main() {
n := 3
conections := [][]int{{1, 2, 5}, {1, 3, 6}, {2, 3, 1}}
fmt.Println(minimumCost(n, conections))
}
func minimumCost(n int, connections [][]int) int {
obj := NewUF(n + 1) // 這里需要注意的是城市是從1開始的，也就是三個(gè)城市，1，2，3，必須要+1，避免panic.
sort.Slice(connections, func(i, j int) bool { // 這里按照第一列進(jìn)行排序非常重要，因?yàn)椴灰欢〞r(shí)間先的放在數(shù)組前面了
return connections[i][2] < connections[j][2]
})
fmt.Println(connections)
res := 0
for _, v := range connections {
if !obj.Connected(v[0], v[1]) { // 其實(shí)這里還有一點(diǎn)貪心算法的意思，如果不連，就連通。不能無腦連通，有可能之前已經(jīng)是連通狀態(tài)了
obj.Union(v[0], v[1])
res += v[2]
}
if obj.count == 2 { // 這里需要注意的是城市是從1開始的，也就是三個(gè)城市，1，2，3
return res
}
}
return -1
}
type UF struct {
parent []int
count int
}
func NewUF(x int) *UF {
parent := make([]int, x)
for i := 0; i < x; i++ {
parent[i] = i
}
count := x
return &UF{parent: parent, count: count}
}
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
func (u *UF) Union(a, b int) {
rootA := u.Find(a)
rootB := u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
func (uf *UF) Connected(a, b int) bool {
return uf.Find(a) == uf.Find(b)
}
1061. 按字典序排列最小的等效字符串（會(huì)員/中等）
給出長(zhǎng)度相同的兩個(gè)字符串s1 和 s2 ，還有一個(gè)字符串 baseStr 。其中 s1[i] 和 s2[i] 是一組等價(jià)字符。舉個(gè)例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。
等價(jià)字符遵循任何等價(jià)關(guān)系的一般規(guī)則：
自反性 ：'a' == 'a'
對(duì)稱性 ：'a' == 'b' 則必定有 'b' == 'a'
傳遞性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
例如， s1 = "abc" 和 s2 = "cde" 的等價(jià)信息和之前的例子一樣，那么 baseStr = "eed" , "acd" 或 "aab"，這三個(gè)字符串都是等價(jià)的，而 "aab" 是 baseStr 的按字典序最小的等價(jià)字符串. 利用 s1 和 s2 的等價(jià)信息，找出并返回 baseStr 的按字典序排列最小的等價(jià)字符串。
輸入：s1 = "parker", s2 = "morris", baseStr = "parser"
輸出："makkek"
解釋：根據(jù) A 和 B 中的等價(jià)信息，我們可以將這些字符分為 [m,p], [a,o], [k,r,s], [e,i] 共 4 組。每組中的字符都是等價(jià)的，并按字典序排列。所以答案是 "makkek"。
輸入：s1 = "hello", s2 = "world", baseStr = "hold"
輸出："hdld"
解釋：根據(jù) A 和 B 中的等價(jià)信息，我們可以將這些字符分為 [h,w], [d,e,o], [l,r] 共 3 組。所以只有 S 中的第二個(gè)字符 'o' 變成 'd'，最后答案為 "hdld"。
輸入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
輸出："aauaaaaada"
解釋：我們可以把 A 和 B 中的等價(jià)字符分為 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 組，因此 S 中除了 'u' 和 'd' 之外的所有字母都轉(zhuǎn)化成了 'a'，最后答案為 "aauaaaaada"。
func main() {
s1 := "parker"
s2 := "morris"
baseStr := "parser"
fmt.Println(smallestEquivalentString(s1, s2, baseStr))
}
// 這個(gè)思路有點(diǎn)絕啊，將字符轉(zhuǎn)化為數(shù)字
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
s1Len := len(s1)
obj := NewUF(26) // 這里非常關(guān)鍵，為什么是26呢。因?yàn)槭亲帜?，最?6個(gè)需要找父節(jié)點(diǎn)
for i := 0; i < s1Len; i++ {
obj.Union(int(s1[i]-'a'), int(s2[i]-'a'))
}
res := []byte{}
for i := range baseStr {
res = append(res, byte('a'+obj.Find(int(baseStr[i]-'a'))))
}
return string(res)
}
// 模板
type UF struct {
count int
parent []int
}
func NewUF(x int) *UF {
u := UF{
count: x,
parent: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
}
return &u
}
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
// 此題在這里最基礎(chǔ)的模板針對(duì)題目進(jìn)行了優(yōu)化，也就是要找最小的parent
func (u *UF) Union(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
if rootA < rootB { // 為了找最小的parent
u.parent[rootB] = rootA
} else {
u.parent[rootA] = rootB
}
u.count--
}
func (u *UF) Connected(a, b int) bool {
return u.Find(a) == u.Find(b)
}
1102. 得分最高的路徑（會(huì)員/中等）
給定一個(gè) m x n 的整數(shù)矩陣 grid，返回從 (0,0) 開始到 (m - 1, n - 1) 在四個(gè)基本方向上移動(dòng)的路徑的最大 分?jǐn)?shù) 。一條路徑的 分?jǐn)?shù) 是該路徑上的最小值。例如，路徑 8 → 4 → 5 → 9 的得分為 4 。
輸入：grid = [[5,4,5],[1,2,6],[7,4,6]]
輸出：4
解釋：得分最高的路徑用黃色突出顯示。
輸入：grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
輸出：2
輸入：grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
輸出：3
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/path-with-maximum-minimum-value
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
[圖片上傳失敗...(image-388dda-1671479296836)]
// ================== 解法一： 并查集 =====================
// 這里其實(shí)很關(guān)鍵，就相當(dāng)于從大到小挨個(gè)中，后來看是不是能連通
// 1. 把節(jié)點(diǎn)值 從大到小 逐個(gè)嘗試，直到最后拼出來grid[0,0]到grid[row-1, col-1](從左上角到右下角)的通路。
// 2. 進(jìn)行UF，期間記錄最小值
// 2. 如果最后通了，那么返回res
func maximumMinimumPath(grid [][]int) int {
row, col := len(grid), len(grid[0])
array := make([][]int, 0)
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
temp := []int{i, j, grid[i][j]}
array = append(array, temp)
}
}
fmt.Println(array)
sort.Slice(array, func(i, j int) bool { // 按照二維數(shù)組的值從大到小排列
return array[i][2] > array[j][2]
})
obj := NewUF(row * col)
visited := make([]bool, row*col)
visited[0] = true
visited[row*col-1] = true
res := min(grid[0][0], grid[row-1][col-1])
directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for _, node := range array {
x, y := node[0], node[1]
index := x*col + y
res = min(res, node[2])
visited[index] = true
for _, dir := range directions {
newX := x + dir[0]
newY := y + dir[1]
newIndex := newX*col + newY
if newX >= 0 && newX < row && newY >= 0 && newY < col && visited[newIndex] {
obj.Union(index, newIndex)
}
if obj.Connected(0, row*col-1) { // 左上和右下連通了,退出
return res
}
}
}
return res
}
// 模板
type UF struct {
count int
parent []int
}
func NewUF(x int) *UF {
u := UF{
count: x,
parent: make([]int, x),
}
for i := 0; i < x; i++ {
u.parent[i] = i
}
return &u
}
func (u *UF) Find(x int) int {
if u.parent[x] != x {
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
func (u *UF) Union(a, b int) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
func (u *UF) Connected(a, b int) bool {
return u.Find(a) == u.Find(b)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
==================== 上述是利用數(shù)組的，也可以轉(zhuǎn)化為node結(jié)構(gòu)體來 ====================
type node struct {
value int
row int
col int
}
func maximumMinimumPath(grid [][]int) int {
row, col := len(grid), len(grid[0])
obj := NewUF(row * col)
var nodes []node
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
nodes = append(nodes, node{value: grid[i][j], row: i, col: j})
}
}
sort.Slice(nodes, func(i, j int) bool { // 按照二維數(shù)組的值從大到小排列
return nodes[i].value > nodes[j].value
})
fmt.Println(nodes)
visited := make([]bool, row*col)
visited[0] = true
visited[row*col-1] = true
res := min(grid[0][0], grid[row-1][col-1])
directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for _, node := range nodes {
x, y := node.row, node.col
index := x*col + y
res = min(res, node.value)
visited[index] = true
for _, dir := range directions {
newX := x + dir[0]
newY := y + dir[1]
newIndex := newX*col + newY
if newX >= 0 && newX < row && newY >= 0 && newY < col && visited[newIndex] {
obj.Union(index, newIndex)
}
if obj.Connected(0, row*col-1) { // 左上和右下連通了,退出
return res
}
}
}
return res
}
261. 以圖判樹（會(huì)員/中等）
給定編號(hào)從 0 到 n - 1 的 n 個(gè)結(jié)點(diǎn)。給定一個(gè)整數(shù) n 和一個(gè) edges 列表，其中 edges[i] = [ai, bi] 表示圖中節(jié)點(diǎn) ai 和 bi 之間存在一條無向邊。如果這些邊能夠形成一個(gè)合法有效的樹結(jié)構(gòu)，則返回 true ，否則返回 false 。
輸入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
輸出: true
輸入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
輸出: false
func main() {
n := 5
edges := [][]int{{0, 1}, {0, 2}, {0, 3}, {1, 4}}
fmt.Println(validTree(n, edges))
edge2 := [][]int{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}} // 1,2,3形成了一個(gè)環(huán)，所以會(huì)掛。
fmt.Println(validTree(n, edge2))
}
func validTree(n int, edges [][]int) bool {
obj := NewUF(n)
for _, v := range edges {
if obj.Connected(v[0], v[1]) { // 如何判斷沒有環(huán)，就是判斷有沒有連通，比如一開始有[0 1] [0 2], 此時(shí)如果來[1 2]，12已經(jīng)是連通的，那就成環(huán)了。
return false
}
obj.Union(v[0], v[1])
}
return obj.count==1
}
734. 句子相似性（會(huì)員/簡(jiǎn)單）
我們可以將一個(gè)句子表示為一個(gè)單詞數(shù)組，例如，句子 "I am happy with leetcode" 可以表示為 arr = ["I","am",happy","with","leetcode"]. 給定兩個(gè)句子 sentence1 和 sentence2 分別表示為一個(gè)字符串?dāng)?shù)組，并給定一個(gè)字符串對(duì) similarPairs ，其中 similarPairs[i] = [xi, yi] 表示兩個(gè)單詞 xi and yi 是相似的。如果 sentence1 和 sentence2 相似則返回 true ，如果不相似則返回 false 。
兩個(gè)句子是相似的，如果:它們具有 相同的長(zhǎng)度 (即相同的字?jǐn)?shù))sentence1[i] 和 sentence2[i] 是相似的. 請(qǐng)注意，一個(gè)詞總是與它自己相似，也請(qǐng)注意，相似關(guān)系是不可傳遞的。例如，如果單詞 a 和 b 是相似的，單詞 b 和 c 也是相似的，那么 a 和 c 不一定相似 。
輸入: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
輸出: true
解釋: 這兩個(gè)句子長(zhǎng)度相同，每個(gè)單詞都相似。
輸入: sentence1 = ["great"], sentence2 = ["great"], similarPairs = []
輸出: true
解釋: 一個(gè)單詞和它本身相似。
輸入: sentence1 = ["great"], sentence2 = ["doubleplus","good"], similarPairs = [["great","doubleplus"]]
輸出: false
解釋: 因?yàn)樗鼈冮L(zhǎng)度不同，所以返回false。
// 此題需要注意，不是一對(duì)一的關(guān)系，是多對(duì)多，比如：["brunch","meal"],["breakfast","meal"],["food","meal"]，多對(duì)多，其實(shí)就不方便用map[string]string{}了。最簡(jiǎn)單的場(chǎng)景，沒用到任何算法。
func areSentencesSimilar(sentence1 []string, sentence2 []string, similarPairs [][]string) bool {
if len(sentence1) != len(sentence2){
return false
}
wordSet := map[string]int{}
for _, v := range similarPairs{
str := v[0]+"#"+v[1] // 中間加一個(gè)#，真的是很機(jī)智了。
wordSet[str]++
}
for i, v1 := range sentence1{
v2 :=sentence2[i]
if v1 != v2 && wordSet[v1+"#"+v2] == 0 && wordSet[v2+"#"+v1] == 0 {
return false
}
}
return true
}
737. 句子相似性 II（會(huì)員/中等）
我們可以將一個(gè)句子表示為一個(gè)單詞數(shù)組，例如，句子 I am happy with leetcode"可以表示為 arr = ["I","am",happy","with","leetcode"]
給定兩個(gè)句子 sentence1 和 sentence2 分別表示為一個(gè)字符串?dāng)?shù)組，并給定一個(gè)字符串對(duì) similarPairs ，其中 similarPairs[i] = [xi, yi] 表示兩個(gè)單詞 xi 和 yi 是相似的。
如果 sentence1 和 sentence2 相似則返回 true ，如果不相似則返回 false 。
兩個(gè)句子是相似的，如果:
它們具有 相同的長(zhǎng)度 (即相同的字?jǐn)?shù))
sentence1[i] 和 sentence2[i] 是相似的
請(qǐng)注意，一個(gè)詞總是與它自己相似，也請(qǐng)注意，相似關(guān)系是可傳遞的。例如，如果單詞 a 和 b 是相似的，單詞 b 和 c 也是相似的，那么 a 和 c 也是 相似 的。
輸入: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
輸出: true
解釋: 這兩個(gè)句子長(zhǎng)度相同，每個(gè)單詞都相似。
輸入: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
輸出: true
解釋: "leetcode" --> "platform" --> "anime" --> "manga" --> "onepiece".
因?yàn)椤發(fā)eetcode”和“onepiece”相似，而且前兩個(gè)單詞是相同的，所以這兩句話是相似的。
輸入: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
輸出: false
解釋: “l(fā)eetcode”和“onepiece”不相似。
func main() {
sentence1 := []string{"great", "acting", "skills"}
sentence2 := []string{"fine", "drama", "talent"}
similarPairs := [][]string{{"great", "fine"}, {"drama", "acting"}, {"skills", "talent"}}
fmt.Println(areSentencesSimilarTwo(sentence1, sentence2, similarPairs))
sentence11 := []string{"I", "love", "leetcode"}
sentence22 := []string{"I", "love", "onepiece"}
similarPairs2 := [][]string{{"manga", "onepiece"}, {"platform", "anime"}, {"leetcode", "platform"}, {"anime", "manga"}}
fmt.Println(areSentencesSimilarTwo(sentence11, sentence22, similarPairs2))
}
func areSentencesSimilarTwo(sentence1 []string, sentence2 []string, similarPairs [][]string) bool {
sen1Len, sen2Len := len(sentence1), len(sentence2)
if sen1Len != sen2Len {
return false
}
obj := NewUF(sen1Len, sentence1, sentence2)
for _, v := range similarPairs {
obj.Union(v[0], v[1])
}
flag := true
//word1 和 word2一一對(duì)應(yīng)查并查集， 如果有一個(gè)不是相似的，則flag = false
for i := 0; i < sen1Len; i++ {
if obj.Find(sentence1[i]) != obj.Find(sentence2[i]) {
flag = false
}
}
return flag
}
// ======================= 以下這個(gè)模板也比較經(jīng)典，是和string有關(guān)的（注意要記?。? =========================
type UF struct {
count int
parent map[string]string
}
func NewUF(x int, sentence1 []string, sentence2 []string) *UF {
u := UF{
count: x,
parent: make(map[string]string, x), //這個(gè)是核心
}
for i := 0; i < x; i++ {
u.parent[sentence1[i]] = sentence1[i]
u.parent[sentence2[i]] = sentence2[i]
}
return &u
}
func (u *UF) Find(x string) string {
if strings.Compare(u.parent[x], x) != 0 { // u.parent[x]==x,strings.Compare結(jié)果=0
u.parent[x] = u.Find(u.parent[x])
}
return u.parent[x]
}
func (u *UF) Union(a, b string) {
rootA, rootB := u.Find(a), u.Find(b)
if rootA == rootB {
return
}
u.parent[rootA] = rootB
u.count--
}
func (u *UF) Connected(a, b string) bool {
return u.Find(a) == u.Find(b)
}
934. 最短的橋（中等）
給你一個(gè)大小為 n x n 的二元矩陣 grid ，其中 1 表示陸地，0 表示水域。島 是由四面相連的 1 形成的一個(gè)最大組，即不會(huì)與非組內(nèi)的任何其他 1 相連。grid 中 恰好存在兩座島 。你可以將任意數(shù)量的 0 變?yōu)?1 ，以使兩座島連接起來，變成 一座島 。返回必須翻轉(zhuǎn)的 0 的最小數(shù)目。
輸入：grid = [[0,1],[1,0]]
輸出：1
輸入：grid = [[0,1,0],[0,0,0],[0,0,1]]
輸出：2
輸入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
輸出：1
827. 最大人工島（困難）
給你一個(gè)大小為 n x n 二進(jìn)制矩陣 grid 。最多 只能將一格 0 變成 1 。返回執(zhí)行此操作后，grid 中最大的島嶼面積是多少？島嶼 由一組上、下、左、右四個(gè)方向相連的 1 形成。
輸入: grid = [[1, 0], [0, 1]]
輸出: 3
解釋: 將一格0變成1，最終連通兩個(gè)小島得到面積為 3 的島嶼。
輸入: grid = [[1, 1], [1, 0]]
輸出: 4
解釋: 將一格0變成1，島嶼的面積擴(kuò)大為 4。
輸入: grid = [[1, 1], [1, 1]]
輸出: 4
解釋: 沒有0可以讓我們變成1，面積依然為 4。
684. 冗余連接（中等）
樹可以看成是一個(gè)連通且 無環(huán) 的 無向 圖。給定往一棵 n 個(gè)節(jié)點(diǎn) (節(jié)點(diǎn)值 1～n) 的樹中添加一條邊后的圖。添加的邊的兩個(gè)頂點(diǎn)包含在 1 到 n 中間，且這條附加的邊不屬于樹中已存在的邊。圖的信息記錄于長(zhǎng)度為 n 的二維數(shù)組 edges ，edges[i] = [ai, bi] 表示圖中在 ai 和 bi 之間存在一條邊。請(qǐng)找出一條可以刪去的邊，刪除后可使得剩余部分是一個(gè)有著 n 個(gè)節(jié)點(diǎn)的樹。如果有多個(gè)答案，則返回?cái)?shù)組 edges 中最后出現(xiàn)的邊。
輸入: edges = [[1,2], [1,3], [2,3]]
輸出: [2,3]
輸入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
輸出: [1,4]
463. 島嶼的周長(zhǎng)（簡(jiǎn)單）
給定一個(gè) row x col 的二維網(wǎng)格地圖 grid ，其中：grid[i][j] = 1 表示陸地， grid[i][j] = 0 表示水域。網(wǎng)格中的格子 水平和垂直 方向相連（對(duì)角線方向不相連）。整個(gè)網(wǎng)格被水完全包圍，但其中恰好有一個(gè)島嶼（或者說，一個(gè)或多個(gè)表示陸地的格子相連組成的島嶼）。島嶼中沒有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）。格子是邊長(zhǎng)為 1 的正方形。網(wǎng)格為長(zhǎng)方形，且寬度和高度均不超過 100 。計(jì)算這個(gè)島嶼的周長(zhǎng)。
輸入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
輸出：16
解釋：它的周長(zhǎng)是上面圖片中的 16 個(gè)黃色的邊
694. 不同島嶼的數(shù)量（會(huì)員/中等/有點(diǎn)難）
給定一個(gè)非空 01 二維數(shù)組表示的網(wǎng)格，一個(gè)島嶼由四連通（上、下、左、右四個(gè)方向）的 1 組成，你可以認(rèn)為網(wǎng)格的四周被海水包圍。請(qǐng)你計(jì)算這個(gè)網(wǎng)格中共有多少個(gè)形狀不同的島嶼。兩個(gè)島嶼被認(rèn)為是相同的，當(dāng)且僅當(dāng)一個(gè)島嶼可以通過平移變換（不可以旋轉(zhuǎn)、翻轉(zhuǎn)）和另一個(gè)島嶼重合。
輸入: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
輸出：1
輸入: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
輸出: 3
[圖片上傳失敗...(image-40f795-1671479296836)]
924. 盡量減少惡意軟件的傳播（困難）
給出了一個(gè)由 n 個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)，用 n × n 個(gè)鄰接矩陣圖 graph 表示。在節(jié)點(diǎn)網(wǎng)絡(luò)中，當(dāng) graph[i][j] = 1 時(shí)，表示節(jié)點(diǎn) i 能夠直接連接到另一個(gè)節(jié)點(diǎn) j。 一些節(jié)點(diǎn) initial 最初被惡意軟件感染。只要兩個(gè)節(jié)點(diǎn)直接連接，且其中至少一個(gè)節(jié)點(diǎn)受到惡意軟件的感染，那么兩個(gè)節(jié)點(diǎn)都將被惡意軟件感染。這種惡意軟件的傳播將繼續(xù)，直到?jīng)]有更多的節(jié)點(diǎn)可以被這種方式感染。假設(shè) M(initial) 是在惡意軟件停止傳播之后，整個(gè)網(wǎng)絡(luò)中感染惡意軟件的最終節(jié)點(diǎn)數(shù)。如果從 initial 中移除某一節(jié)點(diǎn)能夠最小化 M(initial)， 返回該節(jié)點(diǎn)。如果有多個(gè)節(jié)點(diǎn)滿足條件，就返回索引最小的節(jié)點(diǎn)。請(qǐng)注意，如果某個(gè)節(jié)點(diǎn)已從受感染節(jié)點(diǎn)的列表 initial 中刪除，它以后仍有可能因惡意軟件傳播而受到感染。
輸入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
輸出：0
輸入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
輸出：0
輸入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
輸出：1
