• Day31|贪心算法1


    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。

    无固定套路,举不出反例,就可以试试贪心。

    一般解题步骤:

    1.将问题分解成若干子问题

    2.找出适合的贪心策略

    3.求解每一个子问题的最优解

    4.将局部最优解堆叠成全局最优解

    分发饼干

    思路:为了满足更多的小孩,就不要造成饼干尺寸的浪费,大尺寸的饼干既可以满足胃口大的孩子,也可以满足胃口小的孩子,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。可以尝试使用贪心策略,先将饼干数组和小孩数组进行排序。然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。

    1. class Solution{
    2. public:
    3. int findContentChildren(vector<int>&g,vector<int>& s){
    4. sort(g.begin(),g.end());
    5. sort(s.begin(),s.end());
    6. int index = s.size() - 1;
    7. int result = 0;
    8. for(int i = g.size() - 1;i >= 0; i--){
    9. if(index >= 0 && s[index] >= g[i]){
    10. result++;
    11. index--;
    12. }
    13. }
    14. return result;
    15. }
    16. };

    从代码中可以看出,index用来控制饼干数组的遍历,遍历饼干没有再起一个循环,而是采用自减的方式,这是常用的技巧。

    不可以先遍历比骨干再遍历胃口,因为外面for,i是固定移动的,if的index才是符合条件移动的。

     反过来,先满足胃口小的,从小到大去满足:

    1. class Solution{
    2. public:
    3. int findContentChildren(vector<int>& g,vector<int>&s){
    4. sort(g.begin(),g.end());
    5. sort(s.begin(),s.end());
    6. int index = 0;
    7. for(int i = 0; i < size(); i++){
    8. if(index < g.size() && g[index] <= s[i]){
    9. index++;
    10. }
    11. }
    12. return index;
    13. }
    14. };
    1. //思路一
    2. class Solution{
    3. public int findContentChildren(int[] g, int[] s){
    4. Arrays.sort(g);
    5. Arrays.sort(s);
    6. int start = 0;
    7. int count = 0;
    8. for(int i = 0; i < s.length && start < g.length; i++){
    9. if(s[i] >= g[start]){
    10. start++;
    11. count++;
    12. }
    13. }
    14. return count;
    15. }
    16. }
    1. class Solution{
    2. public int findContentChildren(int[] g,int[] s){
    3. Arrays.sort(g);//排序胃口
    4. Arrays.sort(s);//排序饼干
    5. int count = 0;
    6. int start = s.length - 1;//胃口数组长度,从start开始遍历,倒着遍历,先考虑胃口大的
    7. //遍历胃口,从大到小
    8. for(int index = g.length - 1;index >= 0;index--){
    9. if(start >= 0 && g[index] <= s[start]){
    10. start--;//从大到小
    11. count++;//满足一个计数+1
    12. }
    13. }
    14. return count;//返回计数
    15. }
    16. }

    摆动序列

    如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在地话),可能是正数或负数,少于两个元素的序列也是摆动序列。

    给定一个整数序列,返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些元素来获得子序列,剩下的元素保持其原始顺序。

    思路:

    贪心

    删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值。

    整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列。

    实际操作中,删除操作都不用,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)

    这就是贪心所贪的地方, 让峰值尽可能地保持峰值,然后删除单一坡度上的节点。

    在计算是否有峰值的时候,大家知道遍历的下标i,计算presiff(nums[i] - nums[i - 1])和curdiff(nums[i + 1] - nums[i]),如果presiff < 0 && surdiff > 0或者prediff > 0 && curdiff < 0,此时就有波动就需要统计。

    这是我们思考本题的一个大体思路,但本题还要考虑三种情况:

    1.上下坡有平坡

    [1,2,2,2,2,1]删除左边的三个2,或者删除右边的三个2,摆动长度为3

    当i指向第一个2的时候,prediff > 0&&curdiff=0,当 i 指向最后一个2的时候,prediff=0 && curdiff <0.

    如果采用删除左面三个2的规则,那么当prediff = 0&&curdiff < 0也要记录一个峰值,因为他是把之前相同的元素都删掉留下的峰值。

    我们记录峰值的条件应该是:(preDiff <=0 &&curDiff > 0)||(preDiff >= 0&&curDiff < 0) 

    2.数组首尾两端

    本题统计峰值的时候,数组最左面和最右面如何统计。

    当有两个不同的元素时,摆动序列也是2.

    例如[2,5],如果靠统计差值来计算峰值个数,就需要考虑数组最左面和最右面的特殊情况。

    因为我们在计算prediff(nums[i] - nums[i - 1])和curdiff(nums[i+1] - nums[i])的时候,至少需要三个数字才能计算,而数组只有两个数字。这里如果只有两个数字,且是不同的元素,那结果为2.

    3.单调坡中有平坡

    之前我们在讨论 情况一 :相同数字练习的时候,prediff = 0,curdiff < 0或者>0也记为波谷

    为了统一规则。针对序列[2,5],可以假设为[2,2,5],这样就有了坡度,即preDiff = 0.

    [2,2,5]

    针对以上情形,result初始值为1,此时curDiff > 0&&preDiff<=0,那么result++(计算了左面的峰值),最后得到结果为2(峰值个数为2即摆动序列长度为2)

    1. class Solution{
    2. public:
    3. int wiggleMaxLength(vector<int>&nums){
    4. if(num.size() <= 1)return nums.size();
    5. int curDiff = 0;
    6. int preDiff = 0;
    7. int result = 1;
    8. for(int i = 0; i < nums.size() - 1;i++){
    9. curDiff = nums[i + 1]-nums[i];
    10. if((preDiff <= 0 &&curDiff >0)||(preDiff >= 0 && curDiff < 0)){
    11. result++;
    12. }
    13. preDiff = curDiff;
    14. }
    15. };
    16. }

    3.在上面解法中,忽略了第三种情况,即如果在一个单调坡度上有平坡,例如[1,2,2,2,3,4]

    图中我们可以看出,应该记录2,单调中的平坡不能算作峰值(摆动)

     需要在坡度摆动变化时,更新prediff,这样prediff在单调区间有平坡的时候就不会发生变化,造成误判。

    1. class Solution{
    2. public:
    3. int wiggleMaxLength(vctor<int>&nums){
    4. if(nums.size() <= 1)return nums.size();
    5. int curDiff = 0;
    6. int preDiff = 0;
    7. int result = 1;
    8. for(int i = 0; i < nums.size() - 1;i++){
    9. curDiff = nums[i + 1] - nums[i];
    10. //出现峰值
    11. if((preDiff <= 0 && curDiff > 0)||(preDiff >= 0&& curDiff < 0)){
    12. result++;
    13. preDiff = curDiff;
    14. }
    15. }
    16. return result;
    17. }
    18. };

    用动态规划求解

    思路:

    对于我们当前考虑的这个数,要么是作为山峰(nums[i] > nums[i - 1]),要么是作为山谷(即nums[i] < nums[i-1])

    设dp状态dp[i][0],表示考虑前i个数,第i个数作为山峰的摆动子序列的最长长度。

    设dp状态为dp[i][1],表示考虑前i个数,第i个数作为山谷的摆动子序列的最长长度

    1. //设dp状态dp[i][0],表示考虑前i个数,第i个数作为山峰的摆动子序列的最长长度
    2. //设dp状态dp[i][1],表示考虑前i个数,第i个数作为山谷的摆动子序列的最长长度
    3. class Solution{
    4. public:
    5. int wiggleMaxLength(vector<int>&nums){
    6. memset(dp,0,sizeof dp);
    7. dp[0][0] = dp[0][1] = 1;
    8. for(int i = 1;i < nums.size(); ++i){
    9. dp[i][0] = dp[i][1] = 1;
    10. for(int j = 0;j < i;++j){
    11. if(nums[j] > nums[i])dp[i][1] = max(dp[i][1],dp[j][0]+1);
    12. }
    13. for(int j = 0;j < i; ++j){
    14. if(nums[j] < nums[i])dp[i][0] = max(dp[i][0],dp[j][1] + 1);
    15. }
    16. }
    17. return max(dp[nums.size() - 1][0],dp[nums.size() - 1][1]);
    18. }
    19. };

    最大子序和

    1. //记录局部最优,推出全局最优,相当于暴力求解+调整子区间起始位置,用了一个result来更新和记录最大结果count
    2. class Solution{
    3. public:
    4. int maxSubArray(vector<int>&nums){
    5. int count = 0;
    6. for(int i = 0;i < nums.size(); i++){
    7. count += nums[i];
    8. if(count > result){
    9. result = count;//更新最大值
    10. }
    11. if(count <= 0)count = 0;//重置最大子序列的初始位置
    12. }
    13. return result;
    14. }
    15. };

  • 相关阅读:
    遥感和随机森林核心思想python
    堆(完全二叉树的一种) 模拟
    CUTLASS
    go goroutine
    搞笑短视频如何撰写脚本?分享简单小技巧
    使用Apache Doris自动同步整个 MySQL/Oracle 数据库进行数据分析
    java毕业设计基于的电商平台的设计与实现Mybatis+系统+数据库+调试部署
    GEE:对二值图层进行腐蚀和/或膨胀操作
    西瓜视频基于 Hertz 的微服务落地实践
    图解关系数据库设计思想,这也太形象了
  • 原文地址:https://blog.csdn.net/WEnyue4261/article/details/136442758