---
# System prepended metadata

title: 演算法 HW05

---

# 演算法 HW05
## 第一題
![](https://i.imgur.com/V5Vxa2F.jpg)
## 第二題
![](https://i.imgur.com/iQXI5AH.jpg)
## 第三題
### 目前還不會寫
## 第四題
### 通過畫面截圖
![](https://i.imgur.com/wXjvE3j.png)
### 程式碼
```C++=
class Solution {
public:
    int minTimeToType(string word) {
        int n = word.size();
        char cur = 'a';
        int ans = 0;
        for (int i = 0; i < n; i++) {
            char next = word[i];
            int cw = (next - cur + 26) % 26;  // 順時針方向所需步數
            int ccw = (cur - next + 26) % 26; // 逆時針方向所需步數
            ans += min(cw, ccw) + 1; // 每次移動需要1步
            cur = next; // 更新當前指針位置
        }
        return ans;
    }
};
```
### 解題思路
這一題其實不難，只需要算出順時針與逆時針的步數，並且選出最小的，最後，再更新當前指針位置即可。
### 花費時間
約30分鐘，其中大部分的時間花在如何去計算其中的步數
### 自己完成的比例
全部都由自己完成
## 第五題
### 通過畫面截圖
![](https://i.imgur.com/Be3Q2BK.png)
### 程式碼
```C++=
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int farthest = 0;
        for (int i = 0; i < n; i++) {
            if (i > farthest) return false; // 當前位置大於最遠位置，無法跳躍到最後一個位置
            farthest = max(farthest, i + nums[i]); // 更新最遠位置
            if (farthest >= n - 1) return true; // 已經到達最後一個位置，返回 true
        }
        return true; // 能夠到達最後一個位置
    }
};

```
### 解題思路
farthest代表從當前位置能夠到達的最遠位置，初始值為0。過程中，如果當前位置大於farthest，則返回 false；否則，更新farthest為當前位置能夠到達的最遠位置。如果最遠位置已經超過或等於最後一個位置，則返回 true。最後，如果能夠到達最後一個位置，則返回 true。
### 花費時間
約30分鐘
### 自己完成的比例
五成，有部分參考了網路上的解題方式
## 第六題
### 通過畫面截圖
![](https://i.imgur.com/QmILyi7.png)
### 程式碼
```C++=
class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        int m = rowSum.size();
        int n = colSum.size();
        vector<vector<int>> res(m, vector<int>(n, 0));
        int i = 0, j = 0;
        while (i < m && j < n) {
            int val = min(rowSum[i], colSum[j]);
            res[i][j] = val;
            rowSum[i] -= val;
            colSum[j] -= val;
            if (rowSum[i] == 0) i++;
            if (colSum[j] == 0) j++;
        }
        return res;
    }
};
```
### 解題思路
對於每一個位置(i, j)，可以選擇放置數字 a[i][j] = min(row[i], col[j])。然後更新行列和數組。

假設在某一次更新後，存在某一行或列的和已經為0，但該行或列還存在非零元素，這種情況下無法滿足行列和的條件。因此需要從該行或列的非零元素中選擇一個進行放置，直到該行或列的和變為0。
### 花費時間
約40分鐘
### 自己完成的比例
全部都自己完成
## 心得
這次三題之中有兩題都是medium的題目，難度上面有稍微提升，所以也花了比較多的時間在思考如何去解題，想了很多種方式，其中，有些方式可以解題，但是花費的時間較多，而有方式在邏輯上或是一些例子上會有瑕疵以及錯誤，最後才找到一個洽當的演算法去解題。
