---
###### tags: `資訊科技產業專案設計`
---
# info2022-homework2

> 貢獻者: 霸佛羅｜Buffalo

:man:： interviewer :baby:：interviewee

## [LeetCode#198 House Robber](https://leetcode.com/problems/house-robber/)
> 影片連結：[第二次作業(漢)](https://youtu.be/ZzLqaPX529k)
#### 模擬面試過程的討論

:man:：你好，今天由我來主持這場面試。在這一輪的題目中，會給你一個裝整數型態的 vector，在這個 vector 裡面我們想要加總不相鄰的數字和是最大的，以舉例講解會更清楚

example 1
// Input: nums = [1, 2, 3, 1]
// Output: 4 (因為 1 + 3 = 4)

example 2
// Input: nums = [2, 7, 9, 3, 1]
// Output: 12 (因為 2 + 9 + 1 = 12)

:baby:：好，大致上了解，我想請問一下如果是

// Input: nums = [2, 1, 1, 5]
// Output: 7？

:man:：是的，沒有錯
:baby:：那目前我的想法是如果我們以第一個範例做舉例，我們可以選擇選 1 或不選 1，如果選 1 的話，因為我們不能選 2，所以我們會選 3 或是後面的 1，那如果我們不選 1 的話，因為後面的 3 跟他相鄰，所以我們只能選最後面的 1，不過因為這只有 4 個數字，如果今天數字變多，這個方法會變得複雜並且有許多重複的

   / \ 
  1   2
 / \   \
3   1   1

:baby:：所以目前我的想法是說他可以選擇要選或不選，如果是選的話，那我們就會是以選 `max((arr[0] + arr[2:]), a[1:])`
:man:：那可以請你實作看看嗎

class Solution{
public:
    int rob(vector<int>& nums){
        if (nums.empty()) return 0;
        if (nums.size() <= 1) return num[0];
        // 創建 dp 所需要的陣列
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0]; 
        dp[1] = max(dp[0], nums[1]);
        for (int i = 2; i < nums.size(); ++i) {
            // 選取前一項或自己跟前兩項相加之較大者
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp.back();
    }
};

:baby:：由於我們只需要前兩項的數字，不需要用 vector 將其他群部儲存取來，因此可以以兩個變數代替

class Solution{
public:
    int rob(vector<int>& nums){
        if (nums.empty()) return 0;
        if (nums.size() <= 1) return num[0];
        
        int a = nums[0];
        int b = max(a, nums[1]);
        for (int i = 2; i < nums.size(); ++i) {
            int temp = b;
            b = max(a + nums[i], b);
            a = temp
        }
        return b;
    }
};

:baby:：這樣的話我們可以降低我們空間的利用，從 _O(n)_ 到 _O(1)_
:man:：那如果我們現在將題目改成有 cycle，像是 _[1, 2, 3, 1]_ 為

graph LR

1. --> 2 --> 3 --> 1 --> 1. 

:man:：那你覺得你該怎麼做呢?
:baby:：如果這樣的話我會分成兩個方面討論，分別是有選第一個和沒有第一個，也就是第一個到倒數第二的的陣列比第二個到最後一個的陣列

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];
        
        // with the first one
        int a = nums[0];
        int b = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size() - 1; ++i){
            int temp = b;
            b = max(a + nums[i], b);
            a = temp
        }

	// without the first one

        int c = 0;
        int d = num[1];
        
        for (int i = 2; i < nums.size(); ++i) {
            int temp = d;
            d = max(a + nums[i], d);
            c = temp
        }
        // 比較兩個陣列並回傳較大者
        return max(b, d);
    }
}

:baby:：以這個來說，時間複雜度一樣是 _O(n)_，空間複雜度為 _O(1)_
:man:：那我們今天的面試就到這邊，謝謝

### 延伸閱讀
[213. House Robber II](https://leetcode.com/problems/house-robber-ii/)
[337. House Robber III](https://leetcode.com/problems/house-robber-iii/)

---

## 共筆
### 對其他同學的批評

[時光-Bryan](https://hackmd.io/@sysprog/BJhz9Ylfs)
[西尼-Ssini](https://hackmd.io/@sysprog/HJ1oYFlzi)
[雜菜煲-Vegetable HotPot(V.H.P.)](https://hackmd.io/@sysprog/BJpBqFgGj)
[達摩-Daruma](https://hackmd.io/@sysprog/SyyDRMZfi)
[咕咕雞-Chicken](https://hackmd.io/@sysprog/HkzGaFxzj)

### 從中學到什麼

- 面試真的需要練習，很多時候會發現生活中覺得沒什麼的話在面試時就會變的可能不尊重，像是建議將「我是你今天的面試官」改成「今天由我來主持這場面試」，如果沒經過這些練習不會注意到的細節，並且確實一邊講一邊打沒想像中容易
- 題目的演算法會發現有不同解法，經過這幾周也看了一些之前沒看過的題目
- 經過上課有別於以往認為就只是把題目練好，演算法到最佳解，現在會開始思考題目的應用與相關延伸
- 更有危機意識

### 對授課教師許願

由於上課可以給一點壓力，或許可以要求同學完成像是 Linkedin 或是履歷，讓大家有初版履歷並且知道之後要加強哪部分的能力或經驗。