# 2025 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2025)」課程作業 2
>Partner
>鱸梭-Matthew
>:fire:: Interviewer

>Me
>包拯-Moon
>:ice_cube: : Interviewee

## [191. Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/description/?envType=problem-list-v2&envId=oizxjoit)
>[影片連結](https://youtu.be/SSSOuE8ylDQ)

:fire: : 你好，我是你今天的面試官，我姓鱸。
那麼今天的題目給你一個32-bit的unsigned integer。
你要寫出一個function，可以回傳它的二進位表示中有多少個1。

:ice_cube: : 好，那我想先確認一下我對題目的理解是正確的。
我現在輸入一個32-bit的unsigned integer n，然後我需要寫出一個函式去回傳它在二進位表示中有幾個1。
那舉例來說如果n等於17，那麼它的二進位就是10001，所以輸出就會是2，因為有兩個1。
請問我有理解正確嗎?

:fire: : 沒錯，你要分享一下你要怎麼解這題嗎?

:ice_cube: : 好的，那我想到最直覺的方法就是利用bitwise operation，每次檢查最低位元是不是1。
先將輸入n和1做and operation，再利用一個初始化為0的計數器count，來計算有幾個1，如果and operation的結果是1，代表當前的最低位元是1，就讓count加一，接著將n右移一個bit，重複上面的動作直到n變成0為止。

:fire: : Ok. 這個方法確實很好理解。那麼請你用程式來實現這個Solution。

:ice_cube: : 那首先我就是定義一個function called countones，他的輸入是一個整數n，再來是前面提到用來計算有幾個1的計數器，我將它命名為count然後初始化為0。
接下來我會用到一個while迴圈，迴圈內的動作會持續執行，直到n變成0才結束。
那麼迴圈內在做的事情就是依序檢查最右邊的bit，是1的話count就會加1，是0，count就加0等於不會變，接著將n往右移動一個bit。
當迴圈結束後回傳count就是代表輸入的整數n的二進位表示有幾個1，這樣就完成了這個題目。

int countones(int n) {
    int count = 0;
    while(n != 0){
        count += n & 1;
        n >>= 1;
    }
    return count;
}

:fire: : 看起來你的方法是正確的沒錯。
但我發現他有個問題是，如果這一串bit的1幾乎都出現在高位元，這樣最糟的情況要跑32次迴圈，效率太差了。
你覺得還有甚麼方法可以讓他更快?

:ice_cube: : 對這確實是個很嚴重的問題。
如果有很多0的話前面就都是在做無效的檢查。
所以意思是應該要跳過這些0，直接把最右邊的1消除，就可以少做幾次迴圈。
我思考一下，要怎麼把1消除。

:fire: : 好，沒關係。因為我們今天面試時間比較緊迫，如果你一時想不到也不要緊。

:ice_cube: : 嗯不好意思，我想再確認一下我的想法。
假設n是24，換成二進位是11000，那我如果要把最右邊的1消除，我將那個1和0做and應該就可以消除。
喔我想到了，我把n減1之後會得到10111，再去和原本的n做and operation，這樣就可以把右邊的1消除，不用去檢查每個bit，反而是去計算我消除了幾次1，就可以得到題目要求的結果了。

:fire: : 聽起來是個非常不錯的方法。我們只剩下幾分鐘的時間，請你快速的用程式實現，然後告訴我他的時間複雜度和空間複雜度。

:ice_cube: : 好的，這個方法只需要改動while迴圈裡面的部份，迴圈裡第一行我們要將n和n-1做and operation，然後賦值給n。
這樣n最右邊的1就會被消除，然後每消除一個1，count就加1，直到n的1全被消除，變成0跳出迴圈然後回傳count的值，就完成了這個方法。
而且他時間複雜度是根據二進位表示中1的數量，所以當1很少的時候，雖然兩個方法的時間複雜度都是O(1)，但就會比第一個方法快。
那空間複雜度的部分就和前一個方法一樣是O(1)。

int countones(int n) {
    int count = 0;
    while(n != 0){
        n = n & (n - 1);
        count++;
    }
    return count;
}

:fire: : 很好，這個方法有達到我想看到的結果。
那麼恭喜你完成了今天的面試，我們會根據今天的整體表現進行評估，之後會再透過mail通知你結果，祝你後續一切順利 !

---
>Me
>包拯-Moon
>:hammer: : Interviewer

>Partner
>鱸梭-Matthew
>:fish:: Interviewee

## [283. Move Zeroes](https://leetcode.com/problems/move-zeroes/description/)
>[影片連結](https://youtu.be/bw29pLj9Wc0)

:hammer: : 你好，我是北宋公司的包拯，今天就由我來面試你，剛好一直有一個問題，擺在旁邊都沒去解決。
我們公司倉儲的貨物箱狀態會用一個數字表示，如果是空箱，就顯示 0；如果有貨，就顯示箱子編號，但是他是都是穿插的，倉儲人員很難一眼看出哪些箱子有貨、哪些是空的，有沒有一個方法讓她空箱都排去後面，還有就是不能改變貨物原本的順序，因為他們的排列代表實際出貨順序，打亂會搞錯發貨順序，然後因為我們倉儲光是存這些箱子的狀態就很吃緊了，所以你要直接對那個貨物箱狀態最修改。

:fish: : 我先確認一下你現在的問題，就是要在不改變箱子編號的順序下，把空箱 也就是顯示的 0 移到最後，然後不能使用額外的空間去複製目前的狀態。
如果現在
倉儲箱子狀態是: [0,1,0,3,12]
那希望能顯示成
Output: [1,3,12,0,0]

或者現在是
Input: [0,0,1,3,12]
希望能顯示成
Output: [1,3,12,0,0]

或者是
Input: [1,3,12,0,0]
就要顯示成
Output: [1,3,12,0,0]

那如果現在只有空箱
Input: [0]
就顯示
Output: [0]

最後如果都沒有空箱
Input: [1,2,4,12,5,8]
就
Output: [1,2,4,12,5,8]

這樣理解應該沒有錯吧?

:hammer: : 沒錯，我就是想要這樣

:fish: : 那箱子編號有範圍嗎?還有箱子大概有幾個?

:hammer: : 編號從(-2)的31次方到 2 的 31次方，然後箱子最多不超過10000個

:fish: : 那這個問題最直覺的想法就是我要把 0 跟他之後遇到的第一個 非 0 做交換，這樣就可以再不改變非 0 數字的順序下把 0 往後丟。
例如輸入 [0, -1, 0, 3, 12]：
一開始第一個是 0，我就往後找，找到 -1，交換 → [-1, 0, 0, 3, 12]
接著再繼續掃，遇到第二個 0，往後找 3，交換 → [-1, 3, 0, 0, 12]
最後遇到第三個 0，往後找 12，交換 → [-1, 3, 12, 0, 0]
結果就完成了。

但是這樣其實沒什麼效率，他的時間複雜度會是O(n^2)

:hammer: : 沒關係，你先把它實做出來，再看看如何。

:fish: : 那我會使用兩個for迴圈，第一個for去跑每個input數字，也就是0 -1 0 3 12, 然後第二個for迴圈就是去檢查第一個for當下後面的數字，如果第一個for是 0 就是 -1 0 3 12。
但只有當我找到 0 的時候才要跑，然後當我現在找到一個 非0 的箱子才要換，換完就可以直接找下一個箱子。

對，這樣就完成我剛剛說的方法了。

void moveZeroes(int* nums, int numsSize) {
    for (int i=0; i < numsSize; i++) {
        if (nums[i] == 0) {
            for ( int x = i + 1; x < numsSize; x++) {
                if ( nums[x] != 0) {
                    int temp = nums[i];
                    nums[i] = nums[x];
                    nums[x] = temp;
                    break;
                }

            }
        }
    }
}

:hammer: : 看起來沒有錯誤，但是就像你說的，這效率太慢了。時間就是金錢，如果我貨有1000個，你光排好就不知道多久了，有沒有更快的方式?

:fish: : 有，剛有想到，這其實是一個two pointer的問題。
就是說，我只要紀錄目前有貨物箱子要放在哪，跟我目前要處理的箱子是哪個，就可以完成這件事。

當我在掃描整個陣列時，
如果遇到的是有貨的箱子，
就把它放到「應該放的位置」上，然後更新下一次有貨箱放哪。
如果遇到的是空箱（0），那就先不理它，繼續往後掃。

例如輸入 [0, -1, 0, 3, 12]：
一開始第 1 個是 0，不動。
掃到 -1，把它跟前面的 0 交換，變成 [-1, 0, 0, 3, 12]。
繼續往後掃，遇到第二個 0 不動。
掃到 3，跟前面的 0 交換，變成 [-1, 3, 0, 0, 12]。
掃到 12，跟前面的 0 交換，變成 [-1, 3, 12, 0, 0]。
這樣就成功了

:hammer: : 感覺會比你原本的方法快很多，那你會如何實作?

:fish: : 首先我需要一個變數去紀錄我下次有貨物的箱子要放在哪
然後用一個for迴圈去檢查每個箱子要排在哪
當我檢查到有貨物的箱子，我就把箱子所有東西跟號碼都換到新位置
舊的箱子就會變成空箱子
然後更新下一次有貨箱要去的位置。
這樣就實作完成。

那這樣他的時間複雜度就會下降為O(n)

void moveZeroes(int* nums, int numsSize) {
    int j = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 0) {

            if (i != j) {
                nums[j] = nums[i];
                nums[i] = 0;
            }
            j++;
        }
    }
}

另外，如果是「全部都是空箱」或「完全沒有空箱」的情況，
也會正確處理：
Input: [0]
只有一個空箱，不動
Output: [0]

或者
Input: [1, 2, 4, 12, 5, 8]
箱子1要去第一個位置 [1,2,4,12,5,8], 更新下一次箱子要去的位置，也就是排在下一個
現在換箱子2，箱子2要去第二位置，再更新下一次箱子要去的位置
依此類推，就像拿起來再放下去。
最後就會是
Output: [1, 2, 4, 12, 5, 8]

:hammer: : 你這方法有符合需求又有效率，感覺可以順利解決目前遇到這問題。
那今天面試也到一個段落，感謝你的參與，有甚麼後續消息，會再通知你的，再見。