# info2023-homework2
## Video
> * [**影片連結(漢語)**](https://youtu.be/bPzMEATxAXs)
## Leetcode
> ==😎:interviewer==, ==🤪:interviewee==
* ## [1791. Find Center of Star Graph](https://leetcode.com/problems/find-center-of-star-graph/)
:::success
:::
### 問題描述
**有一個無向星圖，由標記為 1 到 n 的 n 個節點組成。**
**其中有一個中心節點，並且恰好有 n - 1 條邊將中心節點與每個其他節點連接起來。**
**給定一個2維整數陣列 Edges，其中每個 Edges[i] = [ui, vi] 表示節點 ui 和 vi 之間有一條邊。 返回星圖的中心節點。**
### 原始解法
😎: 你好，感謝撥空參與，我是主持這次面試的人員。我們目前正在開發社交網絡平台，想請問同學對這個有任何基礎的了解嗎?
🤪: 可以透過網絡平台找到某個用戶，也可以查他的好友或粉絲數量。
😎: 那你可以將這種關係圖形化並大致說明一下它的概念嗎?
🤪: 可以把每位使用者當作一個點，使用者與其他任一用戶可以用邊連結，代表他們之間的關聯。
🤪: 所以某個用戶與他的好友/粉絲之間的關係圖可以畫成一個星狀圖，中間的節點就是那個用戶本人，每連接一條邊到另一個節點，代表一位好友/粉絲。
😎: 感謝你的說明。接下來關於你所描述的關係與圖形，可以用一些簡單的程式來描述嗎?例如求出一個無向星狀圖的中心點。
🤪: 好的。是要先給數個節點(用戶)，並且有其中一個節點(中心)與其他節點都有邊連接嗎?
😎: 是的，例如求出一個無向星狀圖的中心點，可以使用C寫個簡易的副程式。
🤪: 我先用一個2維陣列儲存所有有邊連結的節點，然後設個變數代表中心節點，再一一掃描陣列中是否有重複的節點，它就是中心點。

int findCenter(int** edges, int edgesSize, int* edgesColSize){
    int center;
    // 判斷第一個節點有無等於下一列的任一節點(此節點是否為圖形中心)
    for(int i=0; i<edgesSize-1; i++){
        if(edges[i][0]==edges[i+1][0] || edges[i][0]==edges[i+1][1]){
            center=edges[i][0];
        }
        else{    // 若沒有，中心點為另一節點
            center=edges[i][1];
        }
    }
    return center;
}

🤪: 2維陣列 edges 中每組 [ui, vi] 代表節點 ui 和 vi 之間有邊連結，整數 center 代表儲存中心節點的變數。用for迴圈掃描陣列 edges，索引的範圍為0~edgesSize(陣列大小)-1，不然迴圈的最終次迭代會超出陣列邊界。
🤪: 若每列的第一個節點與下一列的任一節點重複，則該節點為中心點；否則中心點為第二個節點。
### 優化解法
😎: 這樣時間複雜度多少?
🤪: 迴圈只需遍歷邊的列表一次，所以為。
😎: 有沒有更簡化的方式?因為只是要求出中心節點，需要遍歷列表全部嗎?

int findCenter(int** edges, int edgesSize, int* edgesColSize){
    // 將判斷部分的for迴圈簡化為單行布林條件式，中心位置只要判斷一次即可，不用全部掃描
    return edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1]? edges[0][0] : edges[0][1];
}

🤪: 中心節點的判斷部分只需一次即可，因為列表內每一組 [ui, vi] 都是有邊連接，而它們一定有其中一個節點是中心點，中心節點在每列(組)都會出現，所以只要挑選任2列檢查有重複的節點就行。
🤪: 可化簡為一行判斷式回傳，時間複雜度優化為。
* #### 題目延伸
😎: OK。那接下來題目稍微變化一下，你能除了求出中心節點外，再求出它到其他節點的最短距離嗎?
==*加上求中心點到其他節點的最短距離*==

struct CenterMinDistance {  //儲存中心節點與最短距離
    int center;
    int min_dis;
};
// 函數接收邊的資訊，回傳到CenterMinDistance
struct CenterMinDistance CMD(int** edges, int edgesSize, int* edgesColSize) {
    struct CMD G;   //宣告變數G
    // 找出中心節點
    G.center=edges[0][0] == edges[1][0] || edges[0][0] == edges[1][1]? edges[0][0] : edges[0][1];
    // 求其他節點到中心點的最短距離
    G.min_dis=999;
    for(int i=0; i<edgesSize-1; i++) {
        if(edges[i][2]>min_dis){
            G.min_dis=edges[i][2];
        }
    }
    return G;
}

🤪: 我新增一個變數 min_dis，代表最短距離，先初始化為一極大數。原先的列表 edges 每列只有第0、1欄有儲存資料，分別為有邊相連的2個節點。這次新儲存每條邊的長度在每列第二欄。
🤪: 用迴圈比較每條邊長，每次更新為最小值，最後回傳到變數名為G的struct內

---
## 第四次作業-他人評論-01
- Interviewer：
- 優點：
- 口條清晰，引導interviewee實作時會遇到的問題
- 題目有做適當的延伸
- 缺點：
- [這邊](https://youtu.be/bPzMEATxAXs?si=q0OkgWQQng4A111s&t=429)不要直接告訴對方:「因為只是要求出中心節點，需要遍歷列表全部嗎?」，等interviewee真的想不到在進行提示
- Interviewee：
- 優點：
- 很猛，用虛擬主播來演示(放錯重點
- 解題思路說明得很詳細

- 缺點：
- 缺少了example和interviewer確認題意
- 適當加上註解，增加interviewer的可讀性

- 其他意見：
- 避免使用三元運算子，雖然可以讓原始碼變得更簡潔，但會降低之後維護的人的可閱讀性

---