48.哀家要长脑子了！

1.376. 摆动序列 - 力扣（LeetCode） 

 看问题抓本质 本质！！识别和追踪数组中元素值的变化趋势。摆动序列是什么，什么是摆动序列，就是差值正负正负的来，最后要求摆动序列的子序列的长度的话，统计这个来回有多少次就好，没必要硬是把摆动序列数组求出来，想什么呢你！

C++版

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {/* 初始化为1，因为仅有一个元素的序列也视为摆动序列所以任何单个元素本身可以被视为一个长度为1的摆动序列up表示以一个上升的趋势结束的最长摆动子序列的长度*/int up = 1, down = 1;for(int i = 1; i < nums.size(); i++){// 说明当前元素形成了一个上升的趋势// 此时最长摆动子序列应该是在前一个下降趋势的基础上加1if(nums[i] > nums[i-1])up = down + 1;else if(nums[i] < nums[i-1])down = up + 1;}// 因为最终的最长摆动子序列可能以一个上升或下降的趋势结束// 所以需要返回up或down中的最大值作为结果return max(up, down);}
};

Java版

class Solution {public int wiggleMaxLength(int[] nums) {int up = 1, down = 1;for(int i = 1; i < nums.length; i++) {if(nums[i] > nums[i-1])up = down + 1;else if(nums[i] < nums[i-1])down = up + 1;}return Math.max(up, down);}
}

2.135. 分发糖果 - 力扣（LeetCode）

 我感觉我的阅读理解能力不好。。。每次抓不到问题的本质有很大一部分是这个原因。

要满足的条件：

        Ra Rb：a的成绩高于b a分的糖果多于b --从左往右看

                      b的成绩高于a b分的糖果多于a --从右往左看

所以来两次左右遍历数组，分别构造满足这两个条件的糖果数组，最后在二者之间去较小的就好。

我觉得这个贪心就贪在眼前，对于一个学生的成绩，我只要看他相邻的学生就好，让他与相邻的学生满足条件，因为要最少的糖果，分糖果的时候也是1个1个加。

C++版

class Solution {
public:int candy(vector<int>& ratings) {vector<int> left(ratings.size(), 1);vector<int> right(ratings.size(), 1);for(int i = 1; i < ratings.size(); i++)if(ratings[i] > ratings[i-1])right[i] = right[i-1] + 1;for(int i = ratings.size()-2; i >= 0; i--)if(ratings[i] >ratings[i+1])left[i] = left[i+1] + 1;int res = 0;for(int i = 0; i < ratings.size(); i++)res += left[i] > right[i] ? left[i] : right[i];return res;}
};

Java版

class Solution {public int candy(int[] ratings) {int[] left = new int[ratings.length];int[] right = new int[ratings.length];Arrays.fill(left, 1);Arrays.fill(right, 1);for(int i = 1; i < ratings.length; i++)if(ratings[i] > ratings[i-1])right[i] = right[i-1] + 1;for(int i = ratings.length - 2; i >= 0; i--) if(ratings[i] > ratings[i+1])left[i] = left[i+1] + 1;int res = 0;for(int i = 0; i < ratings.length; i++) res += left[i] > right[i] ? left[i] : right[i];return res;}
}

3.322. 零钱兑换 - 力扣（LeetCode）

哎呀，其实我感觉准备蓝桥杯的时候好像做过这道题。。。然而还是不会。。我讨厌你这么蠢。

dp[i]：凑齐金额 i 所需要最少的硬币，初始化为一个比较大的数，用来判断最后是否有硬币可以来凑齐这个金额，补药用INT_MAX，他参与计算的时候很可能会溢出

外循环遍历金额，内循环遍历每一种硬币

dp[i -coins[j]] + 1

意味着金额 i-coins[j] 所需的最小硬币数，加上当前硬币coins[j] 后，总硬币数为dp[i -coins[j]] + 1

C++版

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1, amount+1);、// 金额为0 需要0个硬币dp[0] = 0;for(int i = 1; i <= amount; i++) {for(int j = 0; j < coins.size(); j++) {// 此时选择的硬币小于金额 可以考虑使用这枚硬币去凑if(i >= coins[j]) {// 有更小的选择吗。。。dp[i] = min(dp[i], dp[i-coins[j]]+1);}}}return dp[amount] > amount ? -1 : dp[amount];}
};

Java版