推 sustainer123: 大師 02/25 16:14
推 oin1104: 嗚嗚嗚哇哇哇 我去台北都沒做每日 我要花錢了 02/25 16:19
推 sustainer123: 我這個月重刷75 每日好像做不到5題:000 02/25 16:23
→ wu10200512: 我現在還沒寫出來 一直超時 02/25 18:23
https://leetcode.com/problems/greatest-common-divisor-traversal/description
2709. Greatest Common Divisor Traversal
給你一個陣列 nums，如果 GCD(nums[i], nums[j]) > 1 表示 i 可以走到 j，求出是否
可以從任意 i 做為起點走到所有 nums。
思路：
1.要判斷 i 是不是可以走到所有 j 就是判斷 i 和 j 做為點是否連通，可以用併查集去
判斷。
2.一開始只能想到O(n^2)的解法（遍歷所有 (i, j) 檢查GCD，然後併查集的點 merge
），但是測資超大很明顯會TLE，果斷看hint。
3.hint建議我們把 nums 裡面的數字的質數都找出來，如果 GCD(nums[i], nums[j]) > 1
表示他們存在共同質數，我們可以先遍歷一次 nums 找出最大數字，然後建質數表。
4.有兩個 corner case可以先處理，一個是 n == 1 一定連通，另一個是 nums[i] = 1 一
定不連通（GCD一定 <= 1）。
5.建立一個併查集和一個SET，SET用來記錄質數表哪些數字在 nums 裡面。
6.遍歷質數表，如果遇到當前數字在 nums 裡面，就把 nums[i] 的質數 merge 起來。
7.檢查所有 nums[i] 的質數是不是彼此都連通，是的話 true 否則 false。
Java Code：
------------------------------------------------
class Solution {
public boolean canTraverseAllPairs(int[] nums) {
int n = nums.length;
if (n == 1) {
return true;
}
int max = 0;
for (int x : nums) {
if (x == 1) return false;
max = Math.max(max, x);
}
int[] parent = new int[max + 1];
boolean[] has = new boolean[max + 1];
for (int i = 1; i <= max; i++) {
parent[i] = i;
}
for (int x : nums) {
has[x] = true;
}
boolean[] visited = new boolean[max + 1];
for (int i = 2; i * 2 <= max; i++){
if (visited[i]) continue;
for (int j = i + i; j <= max; j += i) {
visited[j] = true;
if (has[j]) {
union(parent, i, j);
}
}
}
int p = find(parent, nums[0]);
for (int i = 1; i < n; i++) {
if (find(parent, nums[i]) != p) return false;
}
return true;
}
private int find(int[] parent, int x) {
return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
private void union(int[] parent, int x, int y) {
x = find(parent, x);
y = find(parent, y);
if (x == y) return;
parent[y] = x;
}
}
------------------------------------------------
--
https://i.imgur.com/4nfnn6f.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708848482.A.AFD.html
※ 編輯: Rushia (122.100.73.13 臺灣), 02/25/2024 16:08:29