演算法作業HW06

第一題

第二題

通過螢幕截圖

程式碼

class Solution {
public:
    int maxArea(vector<int>& height) {
        if (height.size() < 2) {
            return{};
        }
        int count = 0;
        int left = 0;
        int mostcount = 0;
        int right = height.size() - 1;
        while (left < right) {
            if (height[left] > height[right]) {
                count = height[right] * (right - left);
                right--;
                if (count > mostcount) {
                    mostcount = count;
                }
            }
            else{
                count = height[left] * (right - left);
                left++;
                if (count > mostcount) {
                    mostcount = count;
                }
            }
        }
        return mostcount;
    }
};

解題思路

用two pointer方法解，若左邊較小，則left++;若右邊較小，則right++。
如果算出大小比之前大，則取代之，最後算出答案。

花費時間

約15分鐘，以前有解過，所以不難，不過一開始忘記考慮兩邊相等的情況，多花了一些時間除錯。

自己完成的比例

全部由自己完成。

第三題

通過螢幕截圖

程式碼

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0;
        int left = 0;
        int right = 0;

        while (right < nums.size() - 1) {
            int farthest = 0;
            while (left < right + 1) {
                farthest = max(farthest, left + nums[left]);
                left++;
            }
            left = right + 1;
            right = farthest;
            count++;
        }
        return count;
    }
};

解題思路

這題跟期中考練習題第三題一樣，當時解得出來，現在不知道為甚麼解不出來。
這題解題思路是先設right = 0，然後再由left = 0逐漸遞增，找出能跳出最遠的值，再用right取代之。

花費時間

約一小時，過程數次runtime error

自己完成的比例

一半，最後花太多時間在網路上尋找資源

心得

這次第三題真的花了很多時間，我用以前練習過的概念去解，總是跑出run time error，但原本的練習運行起來卻沒有甚麼問題，最後只好找網路上的