Re: [閒聊] 每日LeetCode
※ 引述《pandix (麵包屌)》之銘言：
: 990. Satisfiability of Equality Equations
這題我今天上班的時候有解
看到的時候沒想到可以用併查集來解
而且我併查集忘光光了還複習了一下實現方法
一開始是想用無向圖
我參考你的概念然後做一點點改良：
1.不排序整個陣列，遍歷兩次陣列，第一次遍歷 == 的 第二次遍歷 != 的
2.時間複雜度比排序好一些，排序複雜度 O(nlogn) 遍歷兩次複雜度 O(2n)
Java Code：
class Solution {
public boolean equationsPossible(String[] equations) {
int[] root = new int[26];
for(int i = 0; i < 26; i++) root[i] = i;
for(String eq : equations) {
if(eq.charAt(1) == '!') continue;;
int a = eq.charAt(0), b = eq.charAt(3);
root[find(root, a - 'a')] = find(root, b - 'a');
}
for(String eq : equations) {
if(eq.charAt(1) == '=') continue;;
int a = eq.charAt(0), b = eq.charAt(3);
if(root[find(root, a - 'a')] == find(root, b - 'a'))
return false;
}
return true;
}
private int find(int[] root, int x) {
return root[x] == x ? x : find(root, root[x]);
}
}
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.165.253.177 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664293704.A.76D.html
※ 編輯: Rushia (115.165.253.177 臺灣), 09/27/2022 23:51:47
推
09/27 23:58,
1年前
, 1F
09/27 23:58, 1F
推
09/28 00:03,
1年前
, 2F
09/28 00:03, 2F
→
09/28 00:03,
1年前
, 3F
09/28 00:03, 3F
→
09/28 00:03,
1年前
, 4F
09/28 00:03, 4F
→
09/28 00:04,
1年前
, 5F
09/28 00:04, 5F
幹不對可以一行欸
return root[x] == x ? x : (root[x] = find(root, root[x]));
我好爛 我之前都這樣寫
if(root[x] == x) return x;
return root[x] = find(root, root[x]);
※ 編輯: Rushia (115.165.253.177 臺灣), 09/28/2022 00:07:33
討論串 (同標題文章)