> 貢獻者: 阿泥 potato 🐇：interviewer 🤖：interviewee ## [Leetcode 136. Single Number (Easy)](https://leetcode.com/problems/single-number/) [影片(漢)](https://www.youtube.com/watch?v=btn_YvpLlaY) ### 測驗說明與問答 🐇: 哈囉，我是你這次的面試官。以下是你的白板題，講解一下題目 > Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. 🤖: 謝謝你的講解，我快速確認，題目要求我在陣列裡面找出只出現一次的元素，這樣對嗎? 🐇: 對的。那還有其他問題嗎? 🤖: 我想確定值的大小限制，還有陣列長度的限制? 🐇: > 1 <= nums.length <= 3 * 104 > -3 * 104 <= nums[i] <= 3 * 104 🤖: 好的我沒有其他問題了。那我想講一下我對這題的想法。先用陣列用遞增方式做排序。以步伐為2的方式做迭代。接著兩兩元素比較，藉此找到指出一次的元素。 然後我這作法的時間複雜度，應該主要卡在排序，排序的時間複雜度是 NlogN，所以這題解題是 NlogN 🐇: 那聽起來沒問題，你可以寫寫看 🤖: 那麼現在先做排序，接著用 for迴圈迭代看兩兩元素是否相同。我迴圈裡的i這變數，是兩兩比較的元素裡的第一個元素。i 變數的中止條件我社 size-2，因為陣列長度該是奇數，i 最後會跑到陣列裡的倒數第三個。 接著寫迴圈內內容 ...。在迴圈內都找不到，那麼只出現一次的元素就會是最後一個。 🤖: 接著以上面的測資檢查我的程式是否正確.. version 1 ```cpp class Solution { public: int singleNumber(vector<int> nums) { sort(nums.begin(), nums.end()); for (int i = 0; I < num.size()-2; i+= 2) { if (nums[i] != nums[i+1]) nums[i]; } return nums[nums.size()-1]; } } }; ``` 🐇: 那聽起來沒問題，那麼想問你，有沒有更快的寫法，因為你剛剛有提到時間複雜度是 NlogN。 🤖: 有的。我有另一個想法是用 XOR。XOR 的特性是兩兩元素相同，就會抵消成0。這樣的程式碼的時間複雜度就會降到 O(N)。 🐇: 那麼你寫寫看。 🤖: 會有個變數存最終解答。然後迭代這個數組，for 迴圈外，就能得知只出現一次的元素。 🤖: 接著用題目提供的測資去看看我的程式是否正確 ... version 2 ```cpp class Solution { public: int singleNumber(vector<int> nums) { int ans = 0; for (int n: nums) { ans ^= n; } return ans; } }; ``` 🤖: 這一版本的空間複雜度是 O(1)，就多用一個變數。 🐇: 謝謝你的解題，解法看起來都沒有問題。 ## [leetcode 207. Course Schedule (Medium)](https://leetcode.com/problems/course-schedule/description/) [影片 (漢)](https://www.youtube.com/watch?v=vRrdyJYz-dw) ### 測驗說明與問答 🐇:你好我是你這次的面試官，為你講解白板題題目。題目裡會有N個城市，城市裡有一些航班相接，然後接下來給你這些航班的資訊，然後這資訊是由一個陣列所儲存，然後這陣列叫作Flight，Flight I代表它會包含三個資訊，第一個是航班的起始城市，然後接下來是終點城市，接下來是這航班的價格，接下來你會得知三個整數，分別為1. SRC那個起始的城市, 2 你最終要降落的城市, 3.一個K。然後請你算出從這個起始城市到終止城市，並且要求這個路線上，只能多停留K個城市的路徑上的最便宜的機票，如果不存在這樣的路線的話。請返回- 1 🤖: 好謝謝面試官你的解說，那我理解一下題目。 題目的話我把它轉化成一個圖論題，那城市的話就是圖上的節點，那麼路線的航班的價格，就會是圖上的邊的權重，那麼這一題要去找最便宜的價格，那就會相對於圖論裡的最短路徑的問題 🐇:同學你要這樣理解也是沒問題的 🤖:那麼我想要問一下，關於城市的數量是否有限制 🐇:城市的數量最小是一個城市，最多的是到100個城市 🤖:了解，那麼我這一題直觀的解法的話，我想到的是 Bellman-Ford 的解法，原始演算法的話是做，V-1次對所有邊做 relaxation，但這一題的話是限制說是中間只能停留K個節點。 🤖:那麼我會去改變那個 Bellman-Ford V-1次的部分，那我會把它改成做 K加1次的relaxtion，因為停留K個程式...中間多留 K 個節點的話，那會是多擴展K加1條邊..從起始節點來說的話，是多擴展K加1條邊 🤖:接著我就開始寫我的程式，那麼我會首先會有一個陣列去存所有節點到起始節點的最短路徑 ...然後會有N個節點 ..然後最初始的話是，我先設就是無限大，然後代表說目前都是走不到的，然後最開始的話就是，起始節點到自己是0，然後 for 迴圈裡面會有的計算過程會是然後每次去取最小原本距離，跟去嘗試新的路徑。 🤖:外層的話，我會迭代 K+1 次，接著內層去嘗試所有的航班的路線。 所以會是，我先把它用變數寫出來這樣比較清楚 .. 應該是...這樣算...，然後在這樣做完 relaxation 之後。在最外層之外，就能去得知這個起始程式到我們的降落城市的價格。 🤖:痾這邊寫不好是，我應該取名，不要跟函式的參數相同，所以我再改一下.. (解釋: 函式參數取名src, 而我又取名變數src) 🤖:然後最終返回，我們這個路線的降落城市 (的價格) 🤖:好。那我再自己看一下有沒有問題。 🤖:有一個問題，就是我這裡的話，是直接使用 DP。但是在同一個外層，就是i 這個迭代的話，可能會有影響，所以我需要再額外多一個陣列去儲存，避免那個同一次迭代裡會有多次的縮短距離，所以我們先暫存，... 然後最後在這個內層迴圈結束後然後把它寫回。 🤖:好應該就會，沒有問題了，我自己算一下時間複雜度跟空間複雜度 空間複雜度的話是多用了一個Vector，然後一個變數，然後，還有這裡每次都用到一個Vector。所以空間複雜度上應該是 `O(N)` 。時間複雜度的話會是這裡是K加1次乘上所有航班。 🐇:同學你的解題上，邏輯上應該是沒有問題的。那麼你有優化的的想法嗎 🤖:我想想，有一個優化的空間是我應該可以再多用..多用一個變數去確定說這個路徑上是否是可行的 🤖:喔我看那個錯誤了，不好意思。我修正一下。因為在題目裡說，如果這個路徑沒有，不存在的話要返回 -1，但我這邊已經返回- 1了，所以我再修正一下，所以如果最後發現這個，這個路徑仍是整數最大值的話，那麼它會返回- 1，然後反之的話代表說有存在這個路徑，所以會是長這樣.. version 1 ```cpp class Solution { public: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { vector<int> dp (n, INT_MAX); dp[src] = 0; // dp[i] = min(dp[i], flights[j][i] + cost ) for (int i = 0; i <= k; i++) { vector<int> tmp_dp = dp; for (auto &e: flights) { int s = e[0], d = e[1], c = e[2]; tmp_dp[d] = max(dp[s], tmp_dp[s] + c); } dp = tmp_dp; } return dp[dst] == INT_MAX? -1: dp[dst]; } }; ``` 🤖:那我們再回到能否做優化的問題上，那我會多使用一個變數去看這個，是否這內層迴圈是否還能夠有更短距離的發現。 所以我們先就直接用一個布林值，去紀錄內層迴圈是不是真的有被更改到。在一個內層迴圈之外，所以我會去看是否有任何的一條路徑有被縮得更短，如果都沒有的話代表說接下來的也不會更短的路徑出現。所以就可以提前做，停止。 version 2 ```cpp class Solution { public: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { vector<int> dp (n, INT_MAX); dp[src] = 0; // dp[i] = min(dp[i], flights[j][i] + cost ) for (int i = 0; i <= k; i++) { vector<int> tmp_dp = dp; bool isFinish = false; for (auto &e: flights) { int s = e[0], d = e[1], c = e[2]; if (dp[s] != INT_MAX && dp[s]+c < tmp_dp[d]) { tmp_dp[d] = tmp_dp[s] + c; isFinish = true; } } if (!isFinish) break; dp = tmp_dp; } return dp[dst] == INT_MAX? -1: dp[dst]; } }; ``` 🤖:所以我就做了這剪枝，雖然在複雜度上，應該沒有做改變，但應該是常數時間上會變快。 🐇:謝謝你的解答，然後目前看你的思路上，應該是沒有什麼問題，那謝謝你參與這次的面試。 ## [Leetcode 121 Best time to buy and sell stock (Easy)](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/) [影片(英)](https://youtu.be/Bt_63yfn2DU) 🐇: Hello, I'm your interviewer, and welcome to our coding interview session. I'll give you a problem to solve. Below is the problem statement. 🐇: You are given an array called prices where prices[i] is the price of a given stock on the i-th day. Your task is to find the maximum profit you can achieve by buying one stock and selling it later. You cannot sell the stock before buying it, and you can only make one transaction. If no profit can be achieved, return 0. 🐇: For example, if the array is [7, 1, 5, 3, 6, 4], the maximum profit would be 5 because you could buy the stock on day 2 (price = 1) and sell it on day 5 (price = 6). The difference is 6 - 1 = 5. Is everything clear so far? 🤖: Yes, so I need to find the maximum profit by buying at a low point and selling at a high point afterward? 🐇: Exactly, but remember that you can only perform one buy and one sell operation. 🤖: Got it. I think I can approach this by iterating through the array and, for each day, comparing it with all the later days to find the maximum profit. This would require two loops, though. 🐇: That's a valid brute-force approach. Please go ahead and explain how it would work. 🤖: Okay. So, for each price on day i, I would compare it with every price on a future day j. If prices[j] - prices[i] is greater than the current maximum profit, I would update the maximum profit. I'd repeat this for every day. version 1 ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int maxProfit = 0; for (int I = 0; I < prices.size(); i++) { for (int j = i+1; j < prices.size(); j++) { maxProfit = max(maxProfit, prices[j] – prices[i]); } } return maxProfit; } }; ``` 🐇: Understood. Do you know the time complexity of this solution? 🤖: Yes, since I'm using two loops. One for selecting a buy day and another for checking each sell day—the time complexity would be O(N^2), where N is the number of days. 🐇: That's right. Can you think of a more efficient solution? 🤖: Hmm… Instead of checking every possible pair, I could try to keep track of the minimum price as I iterate through the array. Then, for each day, I just need to check the difference between the current price and the minimum price I’ve seen so far. This way, I can keep the time complexity to O(N) by scanning the array only once. 🐇: That sounds like an improvement. Could you walk me through how you would implement that? 🤖: Sure. I'll initialize two variables: min_price to track the lowest price so far, and max_profit to track the highest profit I've found. As I loop through the prices, for each price, version 2 ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int minPrice = INT_MAX, maxProfit = 0; for (int i = 0; I < prices.size(); i++) { minPrice = min(minPrice, prices[i]); maxProfit = max(maxProfit, prices[i]-minPrices); } return maxProfit; } }; ``` 🐇: It's brilliant. This is the end of coding interview. Think You. ## 初步檢討 - 英文發音很糟糕 如: "afterward" 念成 "of award", "though" 念成 "through", "brute-force" 念成 "blue false" 等。 - 邊打邊說明時候，句子變得很破碎，我也聽不懂我在描述甚麼。 - 填充詞過多，例如: "然後", "痾" 等 - 陳述時講太多 "應該"。 - 做 Leetcode 121 Best time to buy and sell stock 這題時，沒有做 REACTO 的測試。 - 討論 Leetcode 136. Single Number 這題，該說陣列，而非數組