文章目录贪心算法简介什么是贪心算法?贪心算法的特点学习贪心算法的方法示例一、柠檬水找零解题思路代码实现及解析总结二、最大数解题思路代码实现及解析总结三、摆动序列解题思路代码实现及解析总结四、最长递增子序列解题思路代码实现及解析总结五、买卖股票的最佳时机 II解题思路代码实现及解析总结六、按身高排序解题思路代码实现及解析总结七、优势洗牌解题思路代码实现及解析总结贪心算法简介什么是贪心算法?贪心算法更准确的将是一种贪心策略解决问题的策略局部最优—全局最优贪婪 鼠目寸光把解决问题的过程分为若干步;解决每一步的时候,都选择当前看起来”最优的”解法不去关联其他的步骤;“希望”得到全局最优解由于贪心策略的“鼠目寸光”可能使最终的结果不正确所以对于每个贪心策略我们都要证明它的正确性。贪心算法的特点贪心算法需要充分挖掘题目中条件没有固定的模式和套路可能每一道题的贪心策略都是不同的解决有贪心算法需要一定的直觉和经验。正确的贪心策略,我们是需要”证明的”常用的证明的方法数学中见过的所有证明方法能使用贪心算法解决的问题必须具备「无后效性」即某个状态以前的过程不会影响以后的状态只与当前状态有关。学习贪心算法的方法遇到不会的贪心题很正常把心态放平。毕竟它没有模版、套路只能就题具体分析前期学习的时候把重点放在贪心的策略上把这个策略当成经验吸收记住它。而这个策略的证明问题虽然也重要但并不需要钻牛角尖去死磕毕竟每个题目的策略证明都不一定能套用而且证明过程大都很复杂。示例找46块钱但是只有20、10、5、1的面值每种纸币可无限选问怎么选才能使用最少的纸币张数贪心策略每步选一张纸币每次只选所能选择的最大面值的钱本题的选法就是202051证明简要解释设最优解的纸币的张数分别为A、B、C、D发现以上性质B1的话明明就能用A来代替了。设贪心策略的纸币张数分别为a、b、c、d与最优解比较a一定A不然就不是贪心了能选较大面额就选而又证明a不可能A因为如果这样A少的那部分就得由BCD来分担可是发现BCD加起来压根就凑不够20最多19因为有前面性质的限定所以a一定A其他同理。所以贪心策略就是最优解对贪心策略证明的总结结论先行不需要学严谨的数学证明但专研算法的才是需要把数学证明层面吃透把每一题的贪心策略中逻辑上的几个关键点搞清楚这些关键点可以达到使人对贪心策略的逻辑上的正确性而认同就行不学证明 → 想不出策略❌️想出贪心策略靠的是刷题量 - 见过类似题型后的类似策略模式的识别直觉验证 - 拿样例模拟看看策略是否合理反例思考 - 能不能构造出让策略失败的例子数学证明能帮助的场景极少证明通常是事后确认不是发现策略的工具从上面示例的证明也可以看出证明过程确实对策略的提出没什么联系、帮助面试官问“为什么这个贪心策略是对的”✅ 好的回答逻辑层面不需要的回答数学证明面试官根本不需要听这些而且会怀疑你是背的模板。所以接下来的题目就只给出对策略逻辑正确性的认同层面的证明一、柠檬水找零Leetcode链接在柠檬水摊上每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。注意一开始你手头没有任何零钱。给你一个整数数组 bills 其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。解题思路贪心策略分情况讨论a. 遇到 5 元钱直接收下b. 遇到10 元钱找零 5 元钱之后收下没有5块钱就return falsec. 遇到 20 元钱1.先尝试凑 10 5 的组合贪心2.如果凑不出来、就拼凑 5 5 5 的组合还是没有就return false简要证明我们每次遇到 20 元时,优先用 105 找零不行了再使用555因为 5 元更万能 —— 给 10 元和 20 元都需要 5 元,但 10 元只在给 20 元找零时有用。保留更多 5 元意味着后续能应对更多情况,所以优先消耗 10 元。代码实现及解析classSolution{publicbooleanlemonadeChange(int[]bills){intfive0,ten0;//发现在找零的过程中只需关注5块、10块的数量变化就行for(intx:bills){if(x5)five;elseif(x10){if(five!0){five--;ten;}elsereturnfalse;}else{if(ten!0five!0){ten--;five--;}elseif(five3){five-3;}elsereturnfalse;}}returntrue;}}总结复习解题思路二、最大数Leetcode链接给定一组非负整数 nums重新排列每个数的顺序每个数不可拆分使之组成一个最大的整数。注意输出结果可能非常大所以你需要返回一个字符串而不是整数。示例 1输入nums [10,2]输出“210”解题思路贪心策略依题意就是重新对数组进行排序使之最终拼接成一个最大的数所以本题其实是一个“排序题”我们只要定义出某种排序规则按照这种规则使用sort()对数组进行排序即可要找到这种决定“谁先谁后”的排序规则其实并不用刻意去想规律、特征什么的我们只需要在比较器中直接利用“结果判断法”进行定义即可就是要判断a、b 谁先谁后就先把它们分别一前一后地进行拼接看到底哪个在前时拼出来的数才是较大的不用非要依靠什么特征、技巧直接以计算结果来决定但是两个数拼接太麻烦了a、b—ab要先计算 b 有多少位让a乘于这个位数再b我们可以直接把整型数据转化为字符串直接使用字符串拼接再比较字符串的字典序即可还有一个关键点当我们自定义比较器的时候比较规则必须具备“比较传递性”也就是由“ab、bc”必须是可以得出“ac”的否则排序将会混乱。反例自定义规则搞出循环不能排序有3个人A、B、C规则石头剪刀布赢的排在前面A赢B → A排在B前面ABB赢C → B排在C前面BC但是C赢A → C排在A前面CA现在ABBCCA出现了一个圈 A→B→C→A 没有传递性这时Java排序会直接报错、乱序。不过实数的比较天生具备传递性AB、BC —AC 恒成立。那么本题的证明就是围绕着这个比较规则是否具有传递性而展开的很复杂所以略。另外本题中当出现[0,0,0…]这样的数据时最后的结果会是000…这不是正确答案需要特判一下如果出现就 return “0”代码实现及解析classSolution{publicStringlargestNumber(int[]nums){intnnums.length;String[]strnewString[n];for(inti0;in;i)str[i]nums[i];Arrays.sort(str,(a,b)-(ba).compareTo(ab));StringBufferretnewStringBuffer();for(Stringx:str)ret.append(x);if(ret.charAt(0)0)return0;returnret.toString();}}总结复习解题思路三、摆动序列Leetcode链接如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。解题思路如果把整个数组放以“折线图”的形式展现我们发现统计出所有的波峰以及波谷的个数即可但是本题要特殊处理一下“——”这种平滑段对于平滑段我们应只对其中一个数据进行判断来避免统计重复/错误此以及统计方法详见代码简要证明对于单调递增/递减的一段我们肯定只能选其中一个元素而选择其峰值才会使接下来更易改变变化趋势代码实现及解析classSolution{publicintwiggleMaxLength(int[]nums){intnnums.length;if(n1)returnn;intflag0;//记录数据的实时变化趋势0代表平滑intcur10,cur2cur11;//利用两个指针遍历intcount0;for(inti0;in-1;i){intnewFlagnums[cur2]-nums[cur1];//最新的变化趋势if(newFlag0)continue;//发现接下来是平滑的直接跳过该点这样对于一段平滑段我们只会对最后一个数据进行是否为极值点的判断if(flag*newFlag0){//增减趋势发生变化进行计数并将flag更新count;flagnewFlag;}}returncount1;//最后一个点被忽略了而它又是一个必选的点}}总结复习解题思路和代码注释画图真的很重要四、最长递增子序列Leetcode链接给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。解题思路本题之前已经分别使用了dp算法和二分算法来解决的这次的贪心算法则是由dp算法引申出贪心策略再由二分查找算法进行查找优化而来的这也是Leetcode官方贪心版本的解法贪心策略dp算法的过程在填写dp[i]时通过在它前面寻找可以拼接到哪些序列后面得出最长的那个那么对于这些可供nums[i]拼接的序列dp[j]可不可以进行筛选这个筛选策略就是贪心策略。我们把这些序列按照长度分类1、2、3… 而对于每一类比如长度为 2 的这些序列有的以元素 8 为结尾有的以元素 4 为结尾它们都可以供之后的nums[i]进行拼接但是我们发现既然同一类的长度都相等那是不是保留结尾最小的那一个更容易使后来的nums[i]成功拼接要求递增也就是更容易得出更长的递增子序列按以上分类并筛选后得到以下结果可以看到在填表过程中得到的这些符合题意的序列已经安装长度分类并只储存了每类中结尾值最小的那个序列的结尾元素值那么比如在填写dp[7]即以元素13为结尾的最长递增子序列的长度时我们只需要以长度递增的方向去遍历hash表看看它最长能拼接在多长的子序列后13最多可以跟在7后面此时形成了长度为4的子序列而我们又只保留同类中结尾元素最小的所以将长度为4的那一类的储存值改为13这样最后就完成了填表最后返回hash表的长度即可看看最长能形成多长的递增子序列查找优化但是我们发现还是要完整遍历一遍hash表去得出nums[i]的拼接位置时间复杂度优化的并不够但hash表其实也是递增的因为长度为2的子序列是拼接在长度为1的子序列后面的而hash表中又保留的都是同一类中结尾最小的那一个又因为拼接后序列仍是递增的所以hash表一定是严格递增的这样当在hash表中寻找nums[i]的拼接位置时也就是寻找第一个大于nums[i]的位置时就可以使用二分查找算法代码实现及解析classSolution{publicintlengthOfLIS(int[]nums){intnnums.length;ArrayListIntegerhashnewArrayList();hash.add(nums[0]);for(inti1;in;i){if(nums[i]hash.get(hash.size()-1))//处理一下特殊情况可能nums[i]比hash表中所有的值都大此时不能再用二分查找hash.add(nums[i]);else{intleft0,righthash.size()-1;while(leftright){intmid(leftright)/2;if(hash.get(mid)nums[i])leftmid1;elserightmid;}hash.set(right,nums[i]);}}returnhash.size();}}总结复习解题思路五、买卖股票的最佳时机 IILeetcode链接给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而你可以在 同一天 多次买卖该股票但要确保你持有的股票不超过一股。返回 你能获得的 最大 利润 。解题思路本题只要画出股票价格折线图就很容易能得出贪心策略可以看出只要在这些上升段进行交易就可以得到最大的利润所以我们可以定义两个指针来定位到每个上升段的两段并进行累加计算即可i、j 两个指针从0下标开始只有j右边的趋势仍为上升趋势prices[j1]prices[j]就让j直到判定出j的右边不再是上升段为止此时计算利润。然后令i、j 都移动到 j1位置也就是未遍历到的范围继续同样的操作。代码实现及解析classSolution{publicintmaxProfit(int[]prices){intnprices.length;inti0,j0;//两个指针intret0;while(jn){while(j1nprices[j1]prices[j])j;//先让j去找只要j右边的趋势还是上升的就让j右移retprices[j]-prices[i];//while循环出来后此时就可以计算i、j之间的差值ijj1;//计算完之后使i、j都右移跳过这些非上升段}returnret;}}总结复习解题思路可以看一下指针移动逻辑的代码实现六、按身高排序Leetcode链接给你一个字符串数组 names 和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。对于每个下标 inames[i] 和 heights[i] 表示第 i 个人的名字和身高。请按身高 降序 顺序返回对应的名字数组 names 。解题思路本题主要是为了介绍一种新的排序方法为了下一题做铺垫按照题目要求将身高排序之后就找不到其对应名字了解法一比较简单很常见就是使用hashMap将身高与名字进行绑定。但是有没有不绑定的解法这就是本题要介绍的解法二下标排序法在对身高数据进行排序的时候我们是对其下标进行排序不是对下标的数值排序而是虽然对下标进行排序但排序的依据却是其背后的身高数据。因为我们可以自己定义比较器所以在得到两个下标时比较规则里使用的是下标所对应的身高数据这是一个非常实用的技巧。代码实现及解析classSolution{publicString[]sortPeople(String[]names,int[]heights){intnheights.length;Integer[]indexnewInteger[n];//这里要注意下面的sort()方法要么直接用基本数据类型int想要自定义比较器的时候就必须使用“对象数组”整型类型的话就要使用Integer这个对象for(inti0;in;i)index[i]i;//初始化下标数组Arrays.sort(index,(a,b)-heights[b]-heights[a]);//使用自定义比较器用身高的逻辑来对其下标进行排序降序//提取结果String[]retnewString[n];for(inti0;in;i)ret[i]names[index[i]];returnret;}}总结复习解题思路和代码实现优势洗牌田忌赛马七、优势洗牌Leetcode链接给定两个长度相等的数组 nums1 和 nums2nums1 相对于 nums2 的优势可以用满足 nums1[i] nums2[i] 的索引 i 的数目来描述。返回 nums1 的 任意 排列使其相对于 nums2 的优势最大化。示例 1输入nums1 [2,7,11,15], nums2 [1,10,4,11]输出[2,11,7,15]解题思路可以发现本题是和【田忌赛马】的故事是几乎一模一样的田忌赛马是通过调整田忌的赛马出场排列使田忌的优势最大。所以我们可以采取像田忌赛马一样的策略先对两个数组进行升序排序遍历nums1从前往后和nums2中的数进行比较若nums1中的数nums2中的数就可以把该数放到该位置与nums2中的数进行匹配因为已经排过序了所以nums1中没有更小的数该位置nums2的数了所以可以直接匹配否则nums1中的数nums2中的数就把该数放到nums2最后的位置进行比较反正该下等马已经无法获得优势了干脆让它去与nums2中此时最上等的马进行匹配拖累掉nums2的上等马这样以来就有时要让nums1的数在nums2前面的位置匹配有时要在nums2中后面位置匹配所以需要两个指针来定位但是改变nums2的顺序的话最终的结果是不符合要求的所以可以使用上题的排序技巧要对nums2进行排序我们使用nums2中的元素大小的逻辑但对其下标进行排序这样既得到了排序效果又保留了原数据的顺序代码实现及解析classSolution{publicint[]advantageCount(int[]nums1,int[]nums2){intnnums1.length;//排序Arrays.sort(nums1);Integer[]indexnewInteger[n];for(inti0;in;i)index[i]i;Arrays.sort(index,(i,j)-nums2[i]-nums2[j]);//田忌赛马策略intleft0,rightn-1;//定位nums2匹配位置的两个指针int[]retnewint[n];for(intx:nums1){if(xnums2[index[left]]){//田忌的马有优势可以直接匹配ret[index[left]]x;}else{//田忌的马没有优势那直接去最后面去拖累人家的上等马ret[index[right--]]x;}}returnret;}}总结复习解题思路
贪心算法专题（一）
文章目录贪心算法简介什么是贪心算法?贪心算法的特点学习贪心算法的方法示例一、柠檬水找零解题思路代码实现及解析总结二、最大数解题思路代码实现及解析总结三、摆动序列解题思路代码实现及解析总结四、最长递增子序列解题思路代码实现及解析总结五、买卖股票的最佳时机 II解题思路代码实现及解析总结六、按身高排序解题思路代码实现及解析总结七、优势洗牌解题思路代码实现及解析总结贪心算法简介什么是贪心算法?贪心算法更准确的将是一种贪心策略解决问题的策略局部最优—全局最优贪婪 鼠目寸光把解决问题的过程分为若干步;解决每一步的时候,都选择当前看起来”最优的”解法不去关联其他的步骤;“希望”得到全局最优解由于贪心策略的“鼠目寸光”可能使最终的结果不正确所以对于每个贪心策略我们都要证明它的正确性。贪心算法的特点贪心算法需要充分挖掘题目中条件没有固定的模式和套路可能每一道题的贪心策略都是不同的解决有贪心算法需要一定的直觉和经验。正确的贪心策略,我们是需要”证明的”常用的证明的方法数学中见过的所有证明方法能使用贪心算法解决的问题必须具备「无后效性」即某个状态以前的过程不会影响以后的状态只与当前状态有关。学习贪心算法的方法遇到不会的贪心题很正常把心态放平。毕竟它没有模版、套路只能就题具体分析前期学习的时候把重点放在贪心的策略上把这个策略当成经验吸收记住它。而这个策略的证明问题虽然也重要但并不需要钻牛角尖去死磕毕竟每个题目的策略证明都不一定能套用而且证明过程大都很复杂。示例找46块钱但是只有20、10、5、1的面值每种纸币可无限选问怎么选才能使用最少的纸币张数贪心策略每步选一张纸币每次只选所能选择的最大面值的钱本题的选法就是202051证明简要解释设最优解的纸币的张数分别为A、B、C、D发现以上性质B1的话明明就能用A来代替了。设贪心策略的纸币张数分别为a、b、c、d与最优解比较a一定A不然就不是贪心了能选较大面额就选而又证明a不可能A因为如果这样A少的那部分就得由BCD来分担可是发现BCD加起来压根就凑不够20最多19因为有前面性质的限定所以a一定A其他同理。所以贪心策略就是最优解对贪心策略证明的总结结论先行不需要学严谨的数学证明但专研算法的才是需要把数学证明层面吃透把每一题的贪心策略中逻辑上的几个关键点搞清楚这些关键点可以达到使人对贪心策略的逻辑上的正确性而认同就行不学证明 → 想不出策略❌️想出贪心策略靠的是刷题量 - 见过类似题型后的类似策略模式的识别直觉验证 - 拿样例模拟看看策略是否合理反例思考 - 能不能构造出让策略失败的例子数学证明能帮助的场景极少证明通常是事后确认不是发现策略的工具从上面示例的证明也可以看出证明过程确实对策略的提出没什么联系、帮助面试官问“为什么这个贪心策略是对的”✅ 好的回答逻辑层面不需要的回答数学证明面试官根本不需要听这些而且会怀疑你是背的模板。所以接下来的题目就只给出对策略逻辑正确性的认同层面的证明一、柠檬水找零Leetcode链接在柠檬水摊上每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。注意一开始你手头没有任何零钱。给你一个整数数组 bills 其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。解题思路贪心策略分情况讨论a. 遇到 5 元钱直接收下b. 遇到10 元钱找零 5 元钱之后收下没有5块钱就return falsec. 遇到 20 元钱1.先尝试凑 10 5 的组合贪心2.如果凑不出来、就拼凑 5 5 5 的组合还是没有就return false简要证明我们每次遇到 20 元时,优先用 105 找零不行了再使用555因为 5 元更万能 —— 给 10 元和 20 元都需要 5 元,但 10 元只在给 20 元找零时有用。保留更多 5 元意味着后续能应对更多情况,所以优先消耗 10 元。代码实现及解析classSolution{publicbooleanlemonadeChange(int[]bills){intfive0,ten0;//发现在找零的过程中只需关注5块、10块的数量变化就行for(intx:bills){if(x5)five;elseif(x10){if(five!0){five--;ten;}elsereturnfalse;}else{if(ten!0five!0){ten--;five--;}elseif(five3){five-3;}elsereturnfalse;}}returntrue;}}总结复习解题思路二、最大数Leetcode链接给定一组非负整数 nums重新排列每个数的顺序每个数不可拆分使之组成一个最大的整数。注意输出结果可能非常大所以你需要返回一个字符串而不是整数。示例 1输入nums [10,2]输出“210”解题思路贪心策略依题意就是重新对数组进行排序使之最终拼接成一个最大的数所以本题其实是一个“排序题”我们只要定义出某种排序规则按照这种规则使用sort()对数组进行排序即可要找到这种决定“谁先谁后”的排序规则其实并不用刻意去想规律、特征什么的我们只需要在比较器中直接利用“结果判断法”进行定义即可就是要判断a、b 谁先谁后就先把它们分别一前一后地进行拼接看到底哪个在前时拼出来的数才是较大的不用非要依靠什么特征、技巧直接以计算结果来决定但是两个数拼接太麻烦了a、b—ab要先计算 b 有多少位让a乘于这个位数再b我们可以直接把整型数据转化为字符串直接使用字符串拼接再比较字符串的字典序即可还有一个关键点当我们自定义比较器的时候比较规则必须具备“比较传递性”也就是由“ab、bc”必须是可以得出“ac”的否则排序将会混乱。反例自定义规则搞出循环不能排序有3个人A、B、C规则石头剪刀布赢的排在前面A赢B → A排在B前面ABB赢C → B排在C前面BC但是C赢A → C排在A前面CA现在ABBCCA出现了一个圈 A→B→C→A 没有传递性这时Java排序会直接报错、乱序。不过实数的比较天生具备传递性AB、BC —AC 恒成立。那么本题的证明就是围绕着这个比较规则是否具有传递性而展开的很复杂所以略。另外本题中当出现[0,0,0…]这样的数据时最后的结果会是000…这不是正确答案需要特判一下如果出现就 return “0”代码实现及解析classSolution{publicStringlargestNumber(int[]nums){intnnums.length;String[]strnewString[n];for(inti0;in;i)str[i]nums[i];Arrays.sort(str,(a,b)-(ba).compareTo(ab));StringBufferretnewStringBuffer();for(Stringx:str)ret.append(x);if(ret.charAt(0)0)return0;returnret.toString();}}总结复习解题思路三、摆动序列Leetcode链接如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。子序列 可以通过从原始序列中删除一些也可以不删除元素来获得剩下的元素保持其原始顺序。给你一个整数数组 nums 返回 nums 中作为 摆动序列 的 最长子序列的长度 。解题思路如果把整个数组放以“折线图”的形式展现我们发现统计出所有的波峰以及波谷的个数即可但是本题要特殊处理一下“——”这种平滑段对于平滑段我们应只对其中一个数据进行判断来避免统计重复/错误此以及统计方法详见代码简要证明对于单调递增/递减的一段我们肯定只能选其中一个元素而选择其峰值才会使接下来更易改变变化趋势代码实现及解析classSolution{publicintwiggleMaxLength(int[]nums){intnnums.length;if(n1)returnn;intflag0;//记录数据的实时变化趋势0代表平滑intcur10,cur2cur11;//利用两个指针遍历intcount0;for(inti0;in-1;i){intnewFlagnums[cur2]-nums[cur1];//最新的变化趋势if(newFlag0)continue;//发现接下来是平滑的直接跳过该点这样对于一段平滑段我们只会对最后一个数据进行是否为极值点的判断if(flag*newFlag0){//增减趋势发生变化进行计数并将flag更新count;flagnewFlag;}}returncount1;//最后一个点被忽略了而它又是一个必选的点}}总结复习解题思路和代码注释画图真的很重要四、最长递增子序列Leetcode链接给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。解题思路本题之前已经分别使用了dp算法和二分算法来解决的这次的贪心算法则是由dp算法引申出贪心策略再由二分查找算法进行查找优化而来的这也是Leetcode官方贪心版本的解法贪心策略dp算法的过程在填写dp[i]时通过在它前面寻找可以拼接到哪些序列后面得出最长的那个那么对于这些可供nums[i]拼接的序列dp[j]可不可以进行筛选这个筛选策略就是贪心策略。我们把这些序列按照长度分类1、2、3… 而对于每一类比如长度为 2 的这些序列有的以元素 8 为结尾有的以元素 4 为结尾它们都可以供之后的nums[i]进行拼接但是我们发现既然同一类的长度都相等那是不是保留结尾最小的那一个更容易使后来的nums[i]成功拼接要求递增也就是更容易得出更长的递增子序列按以上分类并筛选后得到以下结果可以看到在填表过程中得到的这些符合题意的序列已经安装长度分类并只储存了每类中结尾值最小的那个序列的结尾元素值那么比如在填写dp[7]即以元素13为结尾的最长递增子序列的长度时我们只需要以长度递增的方向去遍历hash表看看它最长能拼接在多长的子序列后13最多可以跟在7后面此时形成了长度为4的子序列而我们又只保留同类中结尾元素最小的所以将长度为4的那一类的储存值改为13这样最后就完成了填表最后返回hash表的长度即可看看最长能形成多长的递增子序列查找优化但是我们发现还是要完整遍历一遍hash表去得出nums[i]的拼接位置时间复杂度优化的并不够但hash表其实也是递增的因为长度为2的子序列是拼接在长度为1的子序列后面的而hash表中又保留的都是同一类中结尾最小的那一个又因为拼接后序列仍是递增的所以hash表一定是严格递增的这样当在hash表中寻找nums[i]的拼接位置时也就是寻找第一个大于nums[i]的位置时就可以使用二分查找算法代码实现及解析classSolution{publicintlengthOfLIS(int[]nums){intnnums.length;ArrayListIntegerhashnewArrayList();hash.add(nums[0]);for(inti1;in;i){if(nums[i]hash.get(hash.size()-1))//处理一下特殊情况可能nums[i]比hash表中所有的值都大此时不能再用二分查找hash.add(nums[i]);else{intleft0,righthash.size()-1;while(leftright){intmid(leftright)/2;if(hash.get(mid)nums[i])leftmid1;elserightmid;}hash.set(right,nums[i]);}}returnhash.size();}}总结复习解题思路五、买卖股票的最佳时机 IILeetcode链接给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而你可以在 同一天 多次买卖该股票但要确保你持有的股票不超过一股。返回 你能获得的 最大 利润 。解题思路本题只要画出股票价格折线图就很容易能得出贪心策略可以看出只要在这些上升段进行交易就可以得到最大的利润所以我们可以定义两个指针来定位到每个上升段的两段并进行累加计算即可i、j 两个指针从0下标开始只有j右边的趋势仍为上升趋势prices[j1]prices[j]就让j直到判定出j的右边不再是上升段为止此时计算利润。然后令i、j 都移动到 j1位置也就是未遍历到的范围继续同样的操作。代码实现及解析classSolution{publicintmaxProfit(int[]prices){intnprices.length;inti0,j0;//两个指针intret0;while(jn){while(j1nprices[j1]prices[j])j;//先让j去找只要j右边的趋势还是上升的就让j右移retprices[j]-prices[i];//while循环出来后此时就可以计算i、j之间的差值ijj1;//计算完之后使i、j都右移跳过这些非上升段}returnret;}}总结复习解题思路可以看一下指针移动逻辑的代码实现六、按身高排序Leetcode链接给你一个字符串数组 names 和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。对于每个下标 inames[i] 和 heights[i] 表示第 i 个人的名字和身高。请按身高 降序 顺序返回对应的名字数组 names 。解题思路本题主要是为了介绍一种新的排序方法为了下一题做铺垫按照题目要求将身高排序之后就找不到其对应名字了解法一比较简单很常见就是使用hashMap将身高与名字进行绑定。但是有没有不绑定的解法这就是本题要介绍的解法二下标排序法在对身高数据进行排序的时候我们是对其下标进行排序不是对下标的数值排序而是虽然对下标进行排序但排序的依据却是其背后的身高数据。因为我们可以自己定义比较器所以在得到两个下标时比较规则里使用的是下标所对应的身高数据这是一个非常实用的技巧。代码实现及解析classSolution{publicString[]sortPeople(String[]names,int[]heights){intnheights.length;Integer[]indexnewInteger[n];//这里要注意下面的sort()方法要么直接用基本数据类型int想要自定义比较器的时候就必须使用“对象数组”整型类型的话就要使用Integer这个对象for(inti0;in;i)index[i]i;//初始化下标数组Arrays.sort(index,(a,b)-heights[b]-heights[a]);//使用自定义比较器用身高的逻辑来对其下标进行排序降序//提取结果String[]retnewString[n];for(inti0;in;i)ret[i]names[index[i]];returnret;}}总结复习解题思路和代码实现优势洗牌田忌赛马七、优势洗牌Leetcode链接给定两个长度相等的数组 nums1 和 nums2nums1 相对于 nums2 的优势可以用满足 nums1[i] nums2[i] 的索引 i 的数目来描述。返回 nums1 的 任意 排列使其相对于 nums2 的优势最大化。示例 1输入nums1 [2,7,11,15], nums2 [1,10,4,11]输出[2,11,7,15]解题思路可以发现本题是和【田忌赛马】的故事是几乎一模一样的田忌赛马是通过调整田忌的赛马出场排列使田忌的优势最大。所以我们可以采取像田忌赛马一样的策略先对两个数组进行升序排序遍历nums1从前往后和nums2中的数进行比较若nums1中的数nums2中的数就可以把该数放到该位置与nums2中的数进行匹配因为已经排过序了所以nums1中没有更小的数该位置nums2的数了所以可以直接匹配否则nums1中的数nums2中的数就把该数放到nums2最后的位置进行比较反正该下等马已经无法获得优势了干脆让它去与nums2中此时最上等的马进行匹配拖累掉nums2的上等马这样以来就有时要让nums1的数在nums2前面的位置匹配有时要在nums2中后面位置匹配所以需要两个指针来定位但是改变nums2的顺序的话最终的结果是不符合要求的所以可以使用上题的排序技巧要对nums2进行排序我们使用nums2中的元素大小的逻辑但对其下标进行排序这样既得到了排序效果又保留了原数据的顺序代码实现及解析classSolution{publicint[]advantageCount(int[]nums1,int[]nums2){intnnums1.length;//排序Arrays.sort(nums1);Integer[]indexnewInteger[n];for(inti0;in;i)index[i]i;Arrays.sort(index,(i,j)-nums2[i]-nums2[j]);//田忌赛马策略intleft0,rightn-1;//定位nums2匹配位置的两个指针int[]retnewint[n];for(intx:nums1){if(xnums2[index[left]]){//田忌的马有优势可以直接匹配ret[index[left]]x;}else{//田忌的马没有优势那直接去最后面去拖累人家的上等马ret[index[right--]]x;}}returnret;}}总结复习解题思路