# [129.Sum root to leaf number](https://leetcode.com/problems/sum-root-to-leaf-numbers/description/)
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
- For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
- Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
限制:
- tree depth<=10
- 0 <= Node.val <= 9
- The number of nodes in the tree is in the range [1, 1000]
---
## [影片](https://youtu.be/n4wGlk6zOJQ)
## 面試過程
### Question:
這是物流公司內的配送路線圖，每條路徑代表從配送中心到顧客的路徑。請計算有幾條路徑。
- 面試官: 這是物流公司內的配送路線圖，每條路徑代表從配送中心到顧客的路徑。請計算有幾條路徑。
- 面試者: 所以會給我配送路線圖，然後去計算有幾條路徑，想問一下資料的形式是如何？
- 面試官: 圖的路徑會是以binary tree的方式做存取，範例如圖:
- 面試官:
```
Input: root = [4,9,0,5,1]
Output: 3
Explain:4-9-0 1條，4-9-1 1條，4-0 1條，總共3條
```
- 面試者: 了解，所以其實我就是要計算有幾條路徑是root到leaf的總共路徑
- 面試官: 沒錯，你打算如何解決這個問題？你能描述一下你考慮的演算法嗎？
- 面試者: 我打算......
- 面試官: 作法聽起來很合理，你可以用你擅長的語言填寫
- 面試者: 我會用C來實作，想問一下這題有什麼限制嗎?
- 面試官:
- tree depth<=10
- The number of nodes in the tree is in the range [1, 1000]
### Code
```clike
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int tree_travel(struct TreeNode* node){
if(node==NULL)
return 0;
if(node ->left == NULL && node->right == NULL)
return 1;
int left_sum = tree_travel(node-> left);
int right_sum =tree_travel(node-> right);
return left_sum+right_sum;
}
int sumNumbers(struct TreeNode* root) {
int result = tree_travel(root);
return result;
}
```
## 延伸
- 面試官: 你的程式碼看起來沒什麼問題，那現在如果我想要你計算出從配送中心到每位顧客的總成本，計算方式如下:
Example:
- 面試者: 好的，那想詢問一下計算上有什麼限制的變動嗎？
- 面試官:
- 限制:
- tree depth<=10(不變)
- 0 <= Node.val <= 9(新增)
- The number of nodes in the tree is in the range [1, 1000](不變)
- 面試者: 了解，這邊的話我將我的程式碼做點改動~
### Code
```clike=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int tree_travel(struct TreeNode* node, int result){
if(node==NULL)
return 0;
result = result*10 + node->val;
if(node ->left == NULL && node->right == NULL)
return result;
int left_sum = tree_travel(node-> left, result);
int right_sum =tree_travel(node-> right, result);
return left_sum+right_sum;
}
int sumNumbers(struct TreeNode* root) {
int result = 0;
result = tree_travel(root, result);
return result;
}
```
# [122. Best Time to Buy and Sell Stock II](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/)
## Question
你是一位電力公司資源調度的負責人，需負責在不同的時段內買入和賣出能源來滿足需求並獲取最大利潤。已知每個時段的電價（以列表形式給出），你可以在任何時段買入和賣出電力，但一次只能持有最多一單（即不能同時有兩筆買入的交易）。請找出可以獲得的最大利潤。
* Constraints:
* 1 <= prices.length <= 3 * 104
* 0 <= prices[i] <= 104
## [影片](https://youtu.be/zRCACBj01cI)
## 面試過程
**1. Repeat（需求理解）**:
* 候選人： 所以我們有一系列時段的電價，我們需要找出買入和賣出時機來最大化我們的利潤。只能在每次賣出後再進行下一次買入，且一次只能持有一筆交易。
* 面試官：對
* 候選人：我有幾個問題想確認一下。我們在每個時段都可以買入和賣出電力嗎？是否可以在同一天內完成買入和賣出？
* 面試官： Y
* 候選人： 我們的交易次數是否有上限？或者我們可以進行無限次的交易？
* 面試官： 沒有交易次數的上限，可以進行多次交易。
**2. Example（舉例）**: 我會舉以下的例子跟你確認
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
**3. Approach（演算法設計）**
面試官： 你打算如何解決這個問題？你能描述一下你考慮的演算法嗎？
候選人： 我打算...
**4. Code（實作）**
```python
def maxProfit(prices):
if not prices:
return 0
n = len(prices)
dp = [[0, 0] for _ in range(n)]
# 初始化第一天的狀態
dp[0][0] = 0 # 第一天不持有電力
dp[0][1] = -prices[0] # 第一天持有電力
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
return dp[n-1][0]
```
面試官：為什麼...
面試官：時間複雜度...
**5. Optimize（優化）**
面試官： 很好，現在我們來討論如何優化這個算法。你有沒有想過這個問題還有其他更有效的方法？
候選人：(實作)
```
def maxProfit(prices):
max_profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
max_profit += prices[i] - prices[i - 1]
return max_profit
```
面試官：為什麼...
面試官：時間複雜度比較前者...
Sign in with Wallet
Connect another wallet