以下是今日份的總結

122 買賣股票的最佳時機 II
55 跳躍游戲
45 跳躍游戲II
1005 K次取反后最大化的數組和

今天的題目難度不低，盡量還是寫一些簡潔代碼 ^?_?^

買賣股票的最佳時機 II

思路：

算出每一天的差值，然后計算所有正值的和，不計算虧損

值得注意的是

局部最優：收集每天的正利潤
全局最優：求得最大利潤。

    int maxProfit(vector<int>& prices) {int res = 0;for (int i = 1; i < prices.size(); i++) {res += max(prices[i] - prices[i - 1],0);}return res;}

跳躍游戲

思路：

局部最優解：每次取最大跳躍步數（取最大覆蓋范圍）
整體最優解：最后得到整體最大覆蓋范圍，看是否能到終點。

值得注意的是

因為元素值是最大跳躍步數，所以可以在范圍內跳任意步數

       bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1)return true; // 只有一個元素，就是能達到for (int i = 0; i <= cover; i++) { // 注意這里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1)return true; // 說明可以覆蓋到終點了}return false;}

跳躍游戲II

思路：

從覆蓋范圍出發，不管怎么跳，覆蓋范圍內一定是可以跳到的，以最小的步數增加覆蓋范圍，覆蓋范圍一旦覆蓋了終點，得到的就是最少步數

值得注意的是

需要統計兩個覆蓋范圍，當前這一步的最大覆蓋和下一步最大覆蓋

    int jump(vector<int>& nums) {int curDistance = 0;  // 當前覆蓋的最遠距離下標int ans = 0;          // 記錄走的最大步數int nextDistance = 0; // 下一步覆蓋的最遠距離下標for (int i = 0; i < nums.size() - 1;i++) { // 注意這里是小于nums.size() - 1，這是關鍵所在nextDistance =max(nums[i] + i, nextDistance); // 更新下一步覆蓋的最遠距離下標if (i == curDistance) { // 遇到當前覆蓋的最遠距離下標curDistance = nextDistance; // 更新當前覆蓋的最遠距離下標ans++;if (nextDistance >= nums.size() - 1)break; // 當前覆蓋最遠距到達集合終點，不用做ans++操作了，直接結束}}return ans;}

K次取反后最大化的數組和

思路：

第一步：將數組按照絕對值大小從小到大排序，注意要按照絕對值的大小
第二步：從前向后遍歷，遇到負數將其變為正數，同時K–
第三步：如果K還大于0，那么反復轉變數值最小的元素，將K用完
第四步：求和

值得注意的是

貪心第一次
局部最優：讓絕對值大的負數變為正數，當前數值達到最大
整體最優：整個數組和達到最大。
再貪一次
局部最優：只找數值最小的正整數進行反轉，當前數值和可以達到最大
全局最優：整個 數組和 達到最大。

    int largestSumAfterKNegations(vector<int>& nums, int k) {int res = 0;//排序，假設將最小的負數放在數組最前面sort(nums.begin(), nums.end());for (int i = 0; i < nums.size(); i++) {//盡可能的處理數組中的負數if (nums[i] < 0 && k > 0) {nums[i] = -nums[i];k--;}}//全是正數，在此調整排序，k有余是單數，則將開頭的數字負數化        if (k % 2 != 0) {sort(nums.begin(), nums.end());nums[0] = -nums[0];}for (int i : nums) {res += i;}return res;}

兩次排序太羅嗦了，優化一下

   static bool cmp(int a, int b) { return abs(a) < abs(b); }int largestSumAfterKNegations(vector<int>& nums, int k) {int res = 0;//按絕對值排序，解決兩次排序的問題sort(nums.begin(), nums.end(), cmp);for (int i = nums.size() - 1; i >= 0; i--) {if (nums[i] < 0 && k > 0) {nums[i] = -nums[i];k--;}}if (k % 2 == 1) {nums[0] = -nums[0];//最小值取負}for (int i : nums) {res += i;}return res;}

寫在最后

----OK，今日份的博客就寫到這里，這一期的貪心算法好難想，明天繼續加油！！！
—還沒看下期的題，但是我的棧還有一節沒寫；
–追上時間進度了嗎？如追，從欠兩天變成欠一天！！（笑
-月亮在走，太陽在跑，時間在睡覺，機會不會等我。