2709. Greatest Common Divisor Traversal
干你老师，编辑到一半跳掉，害我要重打一次
怎么连续2天都是hard
思路 :
这题解法其实很简单，就是当两个数字有大于1的公因子，就把它们连接在一起
最后看是不是所有点都在同一个graph上
不过要怎么实现就想得有点久了
一开始是将所有组合都跑过一次
不过这样是o(n^2)，结果就是超时
最后看了一下提示
先找出最大的数字maxnum，并建立一个长度为maxnum+1的array:factor
factor里面是放1~maxnum所有数字的最小质因子
并建立一个parent array，一开始的值跟factor是一样的
接着将parent[nums[i]]、nums[i]所有质因子p的parent[p]的值
改成最小的parent值
最后去看parent[nums[i]]的是不是都一样就好了
golang code
func canTraverseAllPairs(nums []int) bool {
if len(nums) == 1 {
return true
}
maxnum := nums[0]
minnum := nums[0]
for _, val := range nums[1:] {
maxnum = max(maxnum, val)
minnum = min(minnum, val)
}
if minnum == 1 {
return false
}
factor := make([]int, maxnum+1)
parent := make([]int, maxnum+1)
n := len(factor)
for i := 1; i < n; i++ {
factor[i] = i
}
for i := 2; i < n; i++ {
if factor[i] == i {
for j := i * 2; j < n; j += i {
if factor[j] == j {
factor[j] = i
}
}
}
}
copy(parent, factor)
for _, val := range nums {
temp := val
for temp > 1 {
p := factor[temp]
g1 := find(parent, val)
g2 := find(parent, temp)
if g1 != g2 {
parent[max(g1, g2)] = min(g1, g2)
}
for temp%p == 0 {
temp /= p
}
}
}
p := find(parent, parent[nums[0]])
for _, val := range nums {
if find(parent, parent[val]) != p {
return false
}
}
return true
}
func find(arr []int, i int) int {
for arr[i] != i {
i = arr[i]
}
return i
}

你好强

我想很久：（

大师