Day31|贪心算法1

小明 2025-05-03 18:13:16 5

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

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

一般解题步骤：

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

2.找出适合的贪心策略

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

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

分发饼干

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

class Solution{
public:
   int findContentChildren(vector&g,vector& s){
       sort(g.begin(),g.end());
       sort(s.begin(),s.end());
       int index = s.size() - 1;
       int result = 0;
       for(int i = g.size() - 1;i >= 0; i--){
        if(index >= 0 && s[index] >= g[i]){
            result++;
            index--;
        }
       }
       return result;
   }
};

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

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

 反过来，先满足胃口小的，从小到大去满足：

class Solution{
public:
   int findContentChildren(vector& g,vector&s){
    sort(g.begin(),g.end());
    sort(s.begin(),s.end());
    int index = 0;
    for(int i = 0; i  

class Solution{
  public int findContentChildren(int[] g,int[] s){
    Arrays.sort(g);//排序胃口
    Arrays.sort(s);//排序饼干
    int count = 0;
    int start = s.length - 1;//胃口数组长度，从start开始遍历，倒着遍历，先考虑胃口大的
    //遍历胃口，从大到小
    for(int index = g.length - 1;index >= 0;index--){
      if(start >= 0 && g[index]  0或者prediff > 0 && curdiff  

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

1.上下坡有平坡
 

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

 

当i指向第一个2的时候，prediff > 0&&curdiff=0，当 i 指向最后一个2的时候，prediff=0 && curdiff = 0&&curDiff  

2.数组首尾两端
 

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

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

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

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

3.单调坡中有平坡
 

之前我们在讨论 情况一 ：相同数字练习的时候，prediff = 0，curdiff 0也记为波谷
 

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

[2,2,5]
 

针对以上情形，result初始值为1，此时curDiff > 0&&preDiff nums[i - 1]）,要么是作为山谷（即nums[i]  

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

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

//设dp状态dp[i][0],表示考虑前i个数，第i个数作为山峰的摆动子序列的最长长度
//设dp状态dp[i][1],表示考虑前i个数，第i个数作为山谷的摆动子序列的最长长度
class Solution{
public:
   int wiggleMaxLength(vector&nums){
    memset(dp,0,sizeof dp);
    dp[0][0] = dp[0][1] = 1;
    for(int i = 1;i  nums[i])dp[i][1] = max(dp[i][1],dp[j][0]+1);
        }
        for(int j = 0;j  

最大子序和
 

//记录局部最优，推出全局最优，相当于暴力求解+调整子区间起始位置，用了一个result来更新和记录最大结果count
class Solution{
    public:
         int maxSubArray(vector&nums){
            int count = 0;
            for(int i = 0;i  result){
                    result = count;//更新最大值
                }
                if(count
The End

标签：

微信