今天讲一个贪心算法解决的问题。一、金条切割问题1、题目描述将金条切成两半需要与长度值相同的铜板。比如一根长度为20的金条，不管怎么切都要20个铜板。一群人要瓜分整个金条，怎么瓜分最多的铜盘？输入一个数组，返回拆分的最小成本。例如：给定一个数组{10,20,30}，代表一共三个人，那么整个金条的长度就是10+20+30=60，那么金条应该分成三部分10，20、30（不分顺序）。如果将长度为60的金条分成10和50，则花费60；然后将长度为50的金条分为20和30，花费50；一共花了110个铜板。但是如果你先把长度为60的金条分成30和30，就是60；2、思路（1）准备一个小根桩。将数组放入这个小根堆中。(2)从堆顶弹出的两个数之和为A，将A放回小根堆。(3)执行第2步，直到堆中只剩下一个数。最后每第二步A的累加和就是最终的结果。比如给定一根长度为150的金条，应该分成10、20、30、40、50块。最后花费的铜板数量就是上图中蓝色圈圈的总和，即,150+60+90+30=330。也就是我们解代码的时候，从叶子到根查找，然后从根到叶子就是金条的切割顺序，最后所有的叶子就是需要的块的大小被削减。3.代码/***@authorJava与算法学习：周一*/publicstaticintlessMoneySplitGold(int[]arr){if(arr==null||arr.length==0){return0;}//准备一个小的根堆Queuequeue=newPriorityQueue<>();//将所有数字放入小根堆for(Integers:arr){queue.offer(s);}整数结果=0;国际电流；while(queue.size()>1){//弹出前两个数，每次求和current=queue.poll()+queue.poll();结果+=当前；queue.offer（当前）；}returnresult;}包含对数的所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/greedy/LessMoneySplitGold.java2.光照问题1，题目描述给定一个字符串str，它只由两个字符'X'和'.'组成。'X'表示一面墙，不能放灯，可以开也可以不开；'.'意思是住宅区，可以放灯，需要开灯。如果把灯放在位置i，则可以点亮i-1、i、i+1这三个位置。返回至少需要多少盏灯才能点亮str中所有需要点亮的位置。2.思路（1）位置i是'X'，没关系，到位置i+1（2）位置i是'.'，位置i+1是'X'，位置i需要放灯，来positioni+2position(3)ipositionis'.',i+1is'.',i+2is'.',i+1position需要放灯,来到i+3position(这一步是greedy)(4)i位置是'.'，i+1是'.'，i+2是'X'，i或i+1位置需要放灯，来到i+3位置3，代码/***@authorJava和算法学习：周一*/publicstaticintlight(Stringlight){char[]lightChars=light.toCharArray();//已经点亮的灯的数量intresult=0;//当前位置inti=0;while(i=项目启动资金），根据盈利将项目放入大根堆，弹出大根堆中最上面的项目A，k加1，w加上A的利润（3）一直执行step2，直到达到k项，最后返回w。很像游戏中的打怪升级。每次在打败的怪物中找到最赚钱的怪物，继续战斗，在保证不被打败的情况下，你会越来越强大。3.代码/***@authorJava与算法学习：Monday*/publicstaticintfindMaximizedCapital(intk,intw,int[]profits,int[]capital){//准备一个小根堆QueuecapitalSmallQueue=newPriorityQueue<>((a,b)->a.capital-b.capital);//根据启动项目所需的资金，将所有项目放入小根堆for(inti=0;iprofitsBigQueue=newPriorityQueue<>((a,b)->b.profit-a.profit);for(inti=0;i=项目启动资金,将项目从小根堆弹出到大根堆while(!capitalSmallQueue.isEmpty()&&w>=capitalSmallQueue.peek().capital){利润BigQueue.offer(capitalSmallQueue.poll());可能/资金不足，现在还可以做项目，但是Dagenheap里面没有适合你的项目if(profitsBigQueue.isEmpty()){returnw;}}w+=profitsBigQueue.poll().profit;}返回w;}public静态类程序{publicintprofit;公共资本；publicProgram(intprofit,intcapital){this.profit=profit;this.capital=资本；}}这道题可以直接在LeetCode上测试，所以不需要4.测试结果中是否找到了贪心算法的解法？上一篇文章提到过，难点在于贪心策略的提出和证明。代码往往比较简单，面试时辨别度不是很高。
