面试算法大全-贪心算法总结

喜欢ヅ旅行 2022-10-17 13:51 184阅读 0赞

## 11、贪心 ##

### 11.1 贪心算法总结 ###

贪心算法是指在每个阶段做选择的时候都做出当前阶段（或状态）最好的选择，并且  
期望这样做到的结果是全局最优解（但未必是全局最优解）。

**基本步骤**

步骤1：从某个初始解出发；

步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；

步骤3：将所有解综合起来。

**贪心算法与动态规划的不同**在于它对每个子问题的解决方案都做出选择，**不能回退**。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

### 11.2 经典题目源码总结 ###

#### [换酒问题][Link 1] ####

public int numWaterBottles(int numBottles, int numExchange) {
        
        int total = numBottles;
        while (numBottles >= numExchange) {
        
            //change表示的是兑换成酒的数量
            int change = numBottles / numExchange;
            //total再加上兑换的酒
            total += change;
            //瓶子数量变为兑换成酒的数量加上没有兑换成酒的数量
            numBottles = change + numBottles % numExchange;
        }
        return total;
    }

#### [分发饼干][Link 2] ####

public int findContentChildren(int[] grid, int[] size) {
        
    	if (grid == null || size == null) {
        
    		return 0;
    	}
    	Arrays.sort(grid);
    	Arrays.sort(size);
    	int gi = 0, si = 0;
    	while (gi < grid.length && si < size.length) {
        
    		if (grid[gi] <= size[si]) {
        
    			gi++;
    		}
    		si++;
    	}
    	return gi;
    }

#### [避免重复字母的最小删除成本][Link 3] ####

class Solution {
        
        public int minCost(String s, int[] cost) {
        
            int i = 0, len = s.length();
            int ret = 0;
            while (i < len) {
        
                char ch = s.charAt(i);
                int maxValue = 0;
                int sum = 0;
    
                while (i < len && s.charAt(i) == ch) {
        
                    maxValue = Math.max(maxValue, cost[i]);
                    sum += cost[i];
                    i++;
                }
                ret += (sum - maxValue);
            }
            return ret;
        }
    }

#### [根据身高重建队列][Link 4] ####

class Solution {
        
      public int[][] reconstructQueue(int[][] people) {
        
        Arrays.sort(people, new Comparator<int[]>() {
        
          @Override
          public int compare(int[] o1, int[] o2) {
        
            // if the heights are equal, compare k-values
            return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
          }
        });
        List<int[]> output = new LinkedList<>();
        for(int[] p : people){
        
          output.add(p[1], p);
        }
        int n = people.length;
        return output.toArray(new int[n][2]);
      }
    }

#### [用最少数量的箭引爆气球][Link 5] ####

class Solution {
        
      public int findMinArrowShots(int[][] points) {
        
        if (points.length == 0) return 0;
    
        // sort by x_end
        Arrays.sort(points, new Comparator<int[]>() {
        
          @Override
          public int compare(int[] o1, int[] o2) {
        
            return o1[1] - o2[1];
          }
        });
    
        int arrows = 1;
        int xStart, xEnd, firstEnd = points[0][1];
        for (int[] p : points) {
        
          xStart = p[0];
          xEnd = p[1];
          // if the current balloon starts after the end of another one,
          // one needs one more arrow
          if (firstEnd < xStart) {
        
            arrows++;
            firstEnd = xEnd;
          }
        }
    
        return arrows;
      }
    }

#### [无重叠区间][Link 6] ####

public int intervalSchedule(int[][] intvs) {
        
        if (intvs.length == 0) {
        
            return 0;
        }
        // 按 end 升序排序
        Arrays.sort(intvs, new Comparator<int[]>() {
        
            public int compare(int[] a, int[] b) {
        
                return a[1] - b[1];
            }
        });
        // 至少有一个区间不相交
        int count = 1;
        // 排序后，第一个区间就是 x
        int x_end = intvs[0][1];
        for (int[] interval : intvs) {
        
            int start = interval[0];
            if (start >= x_end) {
        
                // 找到下一个选择的区间了
                count++;
                x_end = interval[1];
            }
        }
        return count;
    }

[Link 1]: https://leetcode-cn.com/problems/water-bottles/
[Link 2]: https://leetcode-cn.com/problems/assign-cookies/
[Link 3]: https://leetcode-cn.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/
[Link 4]: https://leetcode-cn.com/problems/queue-reconstruction-by-height/
[Link 5]: https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/
[Link 6]: https://leetcode-cn.com/problems/non-overlapping-intervals/