贪心 -力扣860.柠檬水找零力扣2208.将数组和减半的最少操作次数力扣179.最大数力扣376.摆动序列

 

目录

力扣860.柠檬水找零

力扣2208.将数组和减半的最少操作次数

力扣179.最大数

力扣376.摆动序列

---

贪心策略，局部最优->全局最优

1.把解决问题的过程分为若干步骤

2.解决每一步的时候，都选择当前看起来“最优秀的”解法

3.希望能够得到全局最优解

例子1：找零问题 50-4=46  ->[20,10,5,1] 46->26->6->5->1   找当前能够找到的最大解法。

例子2:最小路径和（当初动态规划）

每次只能向下，或者向右侧，找到最小的路径，                                                                              11611，这个不一定对，但是符合贪心的策略，鼠目寸光

例子三：背包问题

疯狂装体积小的，直接塞满（只去考虑体积，考虑价值，则去疯狂交给价值）

1.贪心策略的特点:

1.贪心策略的提出是没有标准和模版的

2.可能每一道贪心策略都是不同的

2.贪心策略的正确性

贪心策略可能是一个错误的方法，正确的贪心，是需要一个证明的

常用的证明方法:数学中见过的所有方法

找零问题:【20,10,5,1】

力扣860.柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
if(bills[0]>5){
    return false;
}
//找钱也就是15块和5块
int five=0;int ten=0;
for(int i=0;i<bills.length;i++){
    if(bills[i]==5){
        five++;
    }else if(bills[i]==10){
        ten++;
        five--;
    }
    else if(bills[i]==20){
        if(ten>0){
        ten--;
        five--;
        }else{
       five=five-3;
        }
    }
     if(five<0||ten<0){
    return false;
}
 
}
 
return true;
    }
}

力扣2208.将数组和减半的最少操作次数

class Solution {
    //贪心，每次都去挑选数组中最大的数，然后减半，知道数组和到原来的一半
    public int halveArray(int[] nums) {
  
    int count=0;
    //每次都挑选最大的数，借助一个数据结构(大根堆)
//拿到堆顶，然后再去/2放到大根堆里面
 PriorityQueue <Double>priorityQueue=new PriorityQueue<>((a,b)->b.compareTo(a));
   double sum=0;
    for(double num:nums){
        priorityQueue.add(num);
        sum+=num;
    }
    sum=sum/2.0;
while(sum>0){
    double p=priorityQueue.poll()/2.0;
    count++;
    sum=sum-p;
    priorityQueue.add(p);
}
return count;
 
    }
}

力扣179.最大数

正常的排序:确定元素的先后顺序:谁在前面，谁在后面

a和b是同一数量级，比如 8，9 或者10，11或者34， 36。我的意思是，两位数和两位数比，一位数和一位数比

a和b不是统一数量级，假如位数不一样，那么就依次循环，来确定首尾

谈谈这块，首先这个sort的使用比较器的方法，只适用于包装类的逆序，并不适用于基础类型

      Integer []nums={1,2,3,4};
            //排序
            Arrays.sort(nums,Comparator.reverseOrder());
            for(int x:nums){
                System.out.println(x);
            }

在Java中，当你尝试对字符串数组使用Lambda表达式进行排序，并且使用(b+a).compareTo(a+b)作为比较逻辑时，b+a和a+b在大多数情况下看起来可能相同，因为它们都是将两个字符串拼接起来。但是，这里的关键在于这两个表达式在特定的字符串上可能会产生不同的结果，特别是当涉及到字符串连接时的数值解释时。

考虑以下情况：

当a和b都是数字字符串时（例如a="12"，b="3"），b+a和a+b拼接后的字符串在数值上可能不同，但它们在字典顺序上可能是相同的。例如，"312"和"123"作为字符串在字典顺序上是不同的。
当a和b中包含非数字字符时，拼接后的结果将完全基于字符串的字典顺序，而不是任何潜在的数值解释。

现在，让我们详细分析(b+a).compareTo(a+b)的比较逻辑：

如果b+a在字典顺序上位于a+b之前，则compareTo方法将返回一个负数，表示b应该在a之前。
如果b+a和a+b在字典顺序上相同，则compareTo方法将返回0，表示a和b的位置不变。
如果b+a在字典顺序上位于a+b之后，则compareTo方法将返回一个正数，表示b应该在a之后。

这种比较逻辑在某些特定情况下可能看起来有些奇怪，特别是当处理数字字符串时。通常，如果你想要按照数值对数字字符串进行排序，你应该先将它们转换为数值类型（如Integer或Long），然后再进行比较。

然而，在你提供的例子中，这种比较逻辑可能用于创建一种特定的排序顺序，该顺序可能基于字符串的某种非直观或特殊的比较逻辑。

最后，值得注意的是，对于非数字字符串，这种比较逻辑可能不会产生有意义的结果，因为字符串的字典顺序和它们的任何潜在数值解释之间可能没有直接关系。

其实不用记住顺序，尝试一遍不就好咯。

class Solution {
    public String largestNumber(int[] nums) {
    int n=nums.length;
    String[] strs=new String[n];
    for(int i=0;i<n;i++) strs[i]=""+nums[i];
    //排序
    Arrays.sort(strs,(a,b)->
    {
       return (b+a).compareTo(a+b);
    });
//提取结果
StringBuffer ret=new StringBuffer();
for(String s:strs) ret.append(s);
if(ret.charAt(0)=='0')return "0";
return ret.toString();
    }
}

只有符合全序关系，才能说明贪心正确。

证明 ab,ba两个拼接起来都是数，能够比较大小，就算是字符串也是可以比较ac码，所以可以视为数字。

力扣376.摆动序列

class Solution {
    public  static int wiggleMaxLength(int[] nums) {
        int n=nums.length;
            if(n<2){
                return n;
            }
            int left=0;
            int ret=0;
            int right=0;
            for(int i=0;i<n-1;i++){
 
                right=nums[i+1]-nums[i];
                if(right==0){
                    continue;
                }
                //y要么是波峰， 要么是波谷
                //第一个点也考虑进去,注意等于0的情况是第一个点，假如第一个点不是0，那么left*right也不会等于0，因为假如right=0，那么就会跳过了
                if(left*right<=0){
                    ret++;
                }
                left=right;
            }
            return ret+1;
        }
        
}