# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS11ooE4Rh)」作業 1

> 鮪魚-maguro
> 問：interviewer
> 答：interviewee

[模擬面試錄影(漢)](https://youtu.be/7UiKbdY9Ec8)
[模擬面試錄影(漢)](https://youtu.be/kaG1H4g7gfA)
[模擬面試錄影(英)](https://youtu.be/DOMedVmz7b0)
### 改進方案&初步檢討
* Repeat: 重複提問，確認自己理解原本的要求
* 重複提問的部分我只有用類似自言自語的方式，應該向面試官盡量去詢問，避免理解錯誤。
* Examples: 針對題目條件，舉出符合的案例，不限於特例
* 這部分沒有做到，應該要在一開始就先考慮幾個範例，並且試著提出edge case
* Approach: 說明自己打算採用的方案
* 說明後可以和 interviewer 討論
* Code: 撰寫程式
* 在寫程式時應盡量精簡講重點，避免冗言贅字，
* Test: 若不能實際測試，那說明驗證程式的方案
* 如同Examples
## [1046. Last Stone Weight](https://leetcode.com/problems/last-stone-weight/)
### 過程的討論
*問：
挑選出這串石頭裡面最重的兩顆
讓兩顆石頭去互相的撞擊
如果這兩顆石頭重量一樣的話
那兩顆石頭都會消失
不是的話大的會留下來小的會消失
一路進行下去直到最後只剩下一顆或者是沒有石頭為止*

答：
maximum他就是負責去找出這個array裡面最大跟第二大的
所以我的參數要給他我這個array
那因為是c語言
所以同時也要給它這個array這size
然後我這邊定了兩個變數
這邊跟正常的想法比較不一樣的是
它其實代表的不是最大值的那個值
而是它會在這個array的第幾個位置
我會從最開頭一路找找到這個正列的最結束
那一旦發現有人比IMAX還要大那這個時候他就會去取代IMAX
根據c語言的特性
array帶進來之後裡面的值做的變動
他的參數也是會跟著改變的
最開始的這個數時值陣列stones它的
裡面的數值會會有越來越多的0
那一旦最後剩只剩下一個數值
其他都是0或全部都是0的時候
這個就是我們的終點

*問：
好你說用C++ 寫的方式會比較快
那能不能請你一樣
的題目用C++的方式再寫一次呢*

答：
主要原因是因為他用的是C++能使用到的一些
function功能會比c來得多
那這邊想要用到priority queue
它的top就會是裡面的最大值
把它拿掉之後
這時候就可以找出第二大的紙

大的最大值跟第二大的值他們會相撞得到一個新的值
有可能是0那也有可能是有實際的值
那不管怎麼樣我們都可以把它加進去
直接做push就好了

然後就會一路去做兩顆石頭的相撞
那我們這邊是砍掉兩個加了一個
所以他的size會越來越小
我必須確保說這個priority queue裡面是還有東西的
當他等於一剩下最後一個的時候
或者是說等於0的時候
他就會離開這個迴圈

*問：
c以及C++兩個回答的方式
出來的結果
可以請你分析這兩個結果
有什麼差異*

答:
時間複雜度會是一樣的
它的時間複雜就是一個單純的常數
空間複雜度的話
在C++ 這邊我們額外新增一個priority queue
所以這邊的空間複雜度會大一點
不過它的差異也都是只有常數的差異而已
所以這兩個做法我覺得在這個地方是C++略勝一籌
### 程式碼

int lastStoneWeight(int *stones, int stonesSize)
{
    while (true)
    {
        int num = 0, idx;
        for (int i = 0; i < stonesSize; i++)
        {
            if (stones[i] > 0)
            {
                num++;
                idx = i;
            }
            if (num == 2)
                break;
        }
        if (num == 1)
        {
            return stones[idx];
        }
        else if (num == 0)
        {
            return 0;
        }
    }
}

void maximum(int *arr, int arrSize)
{
    int i_max1 = 0, i_max2 = 1;
    for (int i = 0; i < arrSize; i++)
    {
        if (arr[i] > arr[i_max1])
        {
            i_max2 = i_max1;
            i_max1 = i;
        }
        else if (arr[i] > arr[i_max2])
        {
            i_max2 = i;
        }
    }
    arr[i_max1] = arr[i_max1] - arr[i_max2];
    arr[i_max2] = 0;
}

class Solution
{
public:
    int lastStoneWeight(vector<int> &stones)
    {
        priority_queue<int> pq(begin(stones), end(stones));
        int ans = 0;
        while (pq.size() > 1)
        {
            int max1 = pq.top();
            pq.pop();
            int max2 = pq.top();
            pq.pop();
            pq.push(max1 - max2);
        }
        return pq.empty() ? 0 : pq.top();
    }
};

## [1282. Group the People Given the Group Size They Belong To](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/)
### 過程的討論
*問：
陣列代表著每一位運動員他在這項競技所獲得的分數
那請你回傳他的結果
分別是所有運動員裡面的第幾名*

答：
題目既要我們把每位運動員的名次給決定出來
同時又要求說必須要保留原本運動員的順序

這邊用priority queue去做
那其實c的二維陣列也可以做
我這邊做的做法是
就單純沒有按照大小去存
但是我在取的時候有照大小去取
因為priority queue在取的時候
我們就可以很輕易的用top的函式去呼叫它的最大

### 程式碼

class Solution
{
public:
    vector<int> findRelativeRanks(vector<int> &score)
    {
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < score.size(); i++)
        {
            pq.push({score[i], i});
        }
        vector<int> ans(pq.size());
        for (int i = 1; i < size(score); i++)
        {
            ans[pq.top().second] = i;
            pq.pop();
        }
        return ans;
    }
};

## [338. Counting Bits](https://leetcode.com/problems/counting-bits/)
### 程式碼

int *countBits(int n, int *returnSize)
{
    int *ans = (int *)malloc((n + 1) * sizeof(n + 1));
    *returnSize = n + 1;

    ans[0] = 0;
    for (int i = 0; i < n + 1; i++)
    {
        ans[i] = ans[i] / 2 + i % 2;
    }

    return ans;
}