###### Agenda:
###### 10/05 10:00(UTC+8) 10/04 19:00(UTC-7)
###### 公布這次live session題目
###### 10/05 10:45(UTC+8) 10/04 19:45(UTC-7)
###### 開始逐步給hint
###### 10/05 11:30(UTC+8) 10/04 20:30(UTC-7)
###### 題解 + Q&A
###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3
---
## 本周題目
## Leetcode weekly contest 324
## https://leetcode.com/contest/weekly-contest-324/
---
### Hint
- Q1 :
- hint 1: 如何判斷兩個字串similar
----
### Hint
- Q1
- hint 1: 如何判斷兩個字串similar
- hint 2: 去除重複的元素
----
### Hint
- Q1
- hint 1: 如何判斷兩個字串similar
- hint 2: 去除重複的元素
- hint 3: 讓剩下的元素的排列組合獨一無二
---
### Hint
- Q2:
- hint 1: 先不要考慮複雜度
----
### Hint
- Q2:
- hint 1: 先不要考慮複雜度
- hint 2: 如何判斷一個數字是質數
----
### Hint
- Q2:
- hint 1: 先不要考慮複雜度
- hint 2: 如何判斷一個數字是質數
- hint 3: 1不是質數，如果當下的數字是質數會發生什麼事
----
### Hint
- Q2:
- hint 1: 先不要考慮複雜度
- hint 2: 如何判斷一個數字是質數
- hint 3: 1不是質數，如果當下的數字是質數會發生什麼事
- hint 4: 做完操作後其實數字不會變大
---
### Hint
- Q3
- hint 1: degree代表每個點被幾個點連到，如何去計算degree呢
----
### Hint
- Q3
- hint 1: degree代表每個點被幾個點連到，如何去計算degree呢
- hint 2: Degree為奇數的點數只會有偶數個
----
### Hint
- Q3
- hint 1: degree代表每個點被幾個點連到，如何去計算degree呢
- hint 2: Degree為奇數的點數只會有偶數個
- hint 3: 每加一條邊會有兩個點的degree被影響
----
### Hint
- Q3
- hint 1: degree代表每個點被幾個點連到，如何去計算degree呢
- hint 2: Degree為奇數的點數只會有偶數個
- hint 3: 每加一條邊會有兩個點的degree被影響
- hint 4: 這題的case會需要分開討論，所以一個比較不乾淨的寫法是可以接受的
----
### Hint
- Q3
- hint 1: degree代表每個點被幾個點連到，如何去計算degree呢
- hint 2: Degree為奇數的點數只會有偶數個
- hint 3: 每加一條邊會有兩個點的degree被影響
- hint 4: 這題的case會需要分開討論，所以一個比較不乾淨的寫法是可以接受的
- hint 5: 若你想加一條邊但已經存在在graph上了，有沒有辦法多用多一點邊去達到一樣的效果
---
### Hint
- Q4
- hint 1: 每個點index/2會得到他的parent
----
### Hint
- Q4
- hint 1: 每個點index/2會得到他的parent
- hint 2: 一個數字x被除O(logx)次2後就會變成0
----
### Hint
- Q4
- hint 1: 每個點index/2會得到他的parent
- hint 2: 一個數字x被除O(logx)次2後就會變成0
- hint 3: 考慮每次詢問的兩個點都往同一個點走
----
### Hint
- Q4
- hint 1: 每個點index/2會得到他的parent
- hint 2: 一個數字x被除O(logx)次2後就會變成0
- hint 3: 考慮每次詢問的兩個點都往同一個點走
- hint 4: 紀錄一下走過的點
---
### 題解
----
### Q1
- 這題有很多種方法可以記錄，譬如說最多只有26個字母就開一個26大小的array紀錄
- 依序從a到z把有出現過的字母拿出來並串成一個字串
- 由於最多只有100個所以強制判斷一下就可以了
- 複雜度$O(n^2+\sum字串長度)$
----
### Q1 c++ code
```c++
int similarPairs(vector<string>& words) {
for(auto &it:words){
int cnt[26];
fill(cnt, cnt+26, 0);
for(char c:it) {
cnt[c-'a']=1;
}
it="";
for(int i = 0;i<26;i++){
if(cnt[i]) {
it = it + (char)('a'+i);
}
}
}
int ans=0;
for(int i= 0;i<words.size();i++){
for(int j = i+1;j<words.size();j++)ans+=(words[i]==words[j]);
}
return ans;
}
```
----
### Test case
- similar
- 兩個字串只是不同的排序
- "ab" and "ba"
- 兩個字串字母出現次數不同
- "aab" and "bba"
- non similar
----
### Follow up
能不能做的更快呢
$O(n+\sum字串長度)$
----
### Q2
- 當數字是質數的時候，只有他自己一個質因數
- 當數字不是質數的時候，每次做完題目所說的操作至少會變小接近一半
- 所以最多只會執行 $O(log n)$ 次操作
----
```c++
int smallestValue(int n) {
while(true) {
int tmp = n;
int sum = 0;
for(int i = 2 ; i * i <= tmp ; i++){
if(tmp % i == 0){
while(tmp % i == 0) {
tmp /= i;
sum += i;
}
}
}
if(tmp != 1) {
sum += tmp;
}
if(sum == n) {
return sum;
}
n=sum;
}
return 0;
}
```
----
### Test case
- 質數
- 2, 3, 5
- 合數
- 6, 10
- 答案會停在合數
- 4
----
### Q3
- 分成幾種case
- 所有點的 degree 皆為偶數
- return true
----
### Q3
- 分成幾種case
- 有兩個點的 degree 為奇數
- 若兩個點沒有邊
- return true
- 若兩個點有邊
- 去找一個額外點的點繞過去找得到的話就return true
- (1,2) -> (1,3) (3,2)
- 有四個點的 degree 為奇數
- 兩兩配對判斷有沒有邊
- 可以用Hash table之類的資料結構判斷有沒有邊
----
```c++
bool isPossible(int n, vector<vector<int>>& edges) {
vector<int> degree(n+1);
set<vector<int> > s;
for(auto it:edges){
degree[it[0]]++;
degree[it[1]]++;
s.insert(it);
swap(it[0], it[1]);
s.insert(it);
}
int cnt=0;
vector<int> v;
for(int i = 1;i <= n;i++){
if(degree[i] % 2 == 1) {
v.push_back(i);
}
}
if(v.empty()) {
return true;
}
if(v.size()==2){
if(s.find(vector<int>{v[0], v[1]}) == s.end()) {
return true;
}
for(int i = 1;i<=n;i++){
if(i != v[0] && i != v[1]){
if(s.find(vector<int>{v[0], i})==s.end()
&& s.find(vector<int>{v[1], i})==s.end()) {
return true;
}
}
}
return false;
}
if(v.size() == 4){
if(s.find(vector<int>{v[0], v[1]}) == s.end() && s.find(vector<int>{v[2], v[3]}) == s.end()) {
return true;
}
if(s.find(vector<int>{v[0], v[2]}) == s.end() && s.find(vector<int>{v[1], v[3]}) == s.end()) {
return true;
}
if(s.find(vector<int>{v[0], v[3]}) == s.end() && s.find(vector<int>{v[1], v[2]}) == s.end()) {
return true;
}
}
return false;
}
```
----
### Test case
- 全部degree都是偶數
- 有兩個點degree為奇數
- 兩個點沒有邊
- 兩個點有邊
- true -> n=3 (1,3)
- false -> n=4 (1,2)(2,3)(1,4)(4,3)(1,3)
- 有四個點degree為奇數
- 任兩點沒有邊
- 只有唯一一種組合可以成功
- false case
----
### Q4
- 每個詢問的兩個點同時往上走，直到遇到同一個人
- 因為往上會一直邊小，可以讓大的先走這樣保證他們會同時停在共同的parent上
- 中間經過的點數數量就是答案
----
```c++
vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
vector<int> res;
for(auto it:queries){
int ans = 1;
while(it[0] != it[1]) {
if(it[0] > it[1]) {
it[0] /= 2;
} else{
it[1] /= 2;
}
ans++;
}
res.push_back(ans);
}
return res;
}
```
----
### Test case
- 一般的case
- [4,7]
- 一個點為另一個點的parent的case
- [1,7]
{"title":"1005 live session","description":"Leetcode 1952 :","contributors":"[{\"id\":\"214a576a-9d94-453a-a11d-248251d46d4e\",\"add\":8763,\"del\":2488,\"latestUpdatedAt\":1759646794512}]"}