贪心算法的题目

每一步都做出一个局部最优的选择，最终的结果就是全局最优

只有一部分问题才能用贪心算法（严格来讲，一个问题能不能用贪心算法需要证明的）

2022.8.30 蔚来笔试题：

有a个y,b个o,c个u,用这些字母拼成一个字符串，三个相邻的字母you则可以获得2分，两个相邻的字母是oo则可以得到1分(注意如果四个o：oooo，这种情况是得3分的而不是两分），问最多可以得到多少分？

解答：用贪心，先拼出尽可能多的you出来（因为you的分数最高)，剩下的再拼oo

class Solution
{
   //传入a，b，c分别代表y，o，u的个数
   public int score(int a,int b,int c)
   {
      //求出a,b,c中最小的数，最小的数=最多可以拼出you的个数
      int num1=Math.min(Math.min(a,b),c);
 
      //用完num1个y，num1个o，num1个c来拼出num1个you，求出还剩下多少个o
      b=b-num1; 
       
      //用剩下的o拼成oo,起码还剩下两个才能拼出oo
      if(b>=2)
      {
         return num1*2+b-1;
      }
      else
      {
        return num1*2;   
      }
   }
}

力扣976 三角形的最大周长

先将数组排序，每次选取最大的三个数，如果能凑成三角形就是周长最大的三角形

class Solution 
{
    public int largestPerimeter(int[] nums) 
    {
        Arrays.sort(nums);

        for(int i=nums.length-1;i>=2;i--)
        {
           if(nums[i-1]+nums[i-2]>nums[i])
           {
               return   nums[i]+nums[i-1]+nums[i-2];
           }
        }
        
        return 0;
    }
}

给你多个形如[start,end]的闭区间，求出最多有几个互不相交的区间

比如[1,3],[2,4].[3,6]三个区间，最多有两个区间互不相交

这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，请问你今天最多能参加几个活动呢？（你一个人不能同时参加两个活动）

有很多种贪心的设想

（1）哪个会议开始的早就参加哪个会，一直贪下去

（2）哪个会议时间短就参加哪个会，一直贪下去

(3）哪个会议结束的早，就参加哪个会，一直贪下去

最终发现第三种贪心策略是对的

step1：从所有区间中找到结束最早的那个区间（也就是end最小的那个区间），假设这个区间是x

step2：然后将所有和这个x区间相交（有重叠）的区间都从区间集合里删除

重复步骤1，2，直到区间集合为空，之前选出的那些x的数量就是最多可以参加的活动数

//current表示滑到哪个会议了（第0个会议，第1个会议，第2个会议......），

index表示是和第几个会议进行比较

result用来统计总共可以参加几个会议

Arrays.sort(nums,(a,b)->(a[1]-b[1]) )

int  index=0;
int  current=1; 
int  result=1;

while(current<nums.length-1)
{
   while(nums[current][0]<nums[index][1])//current一直滑到和index这个区间没有重叠的为止
   {
        current++;
   }
   index=current;
   result++;
}

切法一：

切法二：

哈夫曼编码问题

比如数组为[2,3,4,7,9,2]

先把所有的数放到小根堆里面

每一次弹出两个数，进行结合，然后把结合得到的数继续放到小根堆里面去

然后重复上面的步骤，继续弹出两个数，进行结合，将得到的数继续放到小根堆里面去......

public class tanxin
{
    public static void main(String[] args)
    {
        int[]  nums={2,3,4,7,9,2};

        PriorityQueue<Integer> pq=new PriorityQueue<>();

        //所有数字扔到小根堆里去
        for(int i=0;i<nums.length;i++)
        {
           pq.add(nums[i]);
        }

        int sum=0;
        int cur=0;//用来计算每次弹出的两个数之和

        while(pq.size()>1)
        {
            cur=pq.poll()+pq.poll();
            sum=sum+cur;
            pq.add(cur);
        }
        System.out.println(sum);
        return;

    }
}

文章来源地址https://uudwc.com/A/woyV8