贪心算法

1)最自然智慧的算法 2)用一种局部最功利的标准，总是做出在当前看来是最好的选择 3)难点在于证明局部最功利的标准可以得到全局最优解 4)对于贪心算法的学习主要以增加阅历和经验为主

案例题目

• 给定一个有字符串组成的数组Strs
• 必须把所有的字符串拼接起来
• 返回所有的拼接结果中，字典序最小的结果

证明： a.b <= b.a b.c <= c.b 能否推出 a.c <= c.a

字符串排序后: 【.....a .... b....】 < 【.....b .... a....】

	public static class MyComparator implements Comparator<String> {
		@Override
		public int compare(String a, String b) {
			return (a + b).compareTo(b + a);
		}
	}

	public static String lowestString2(String[] strs) {
		if (strs == null || strs.length == 0) {
			return "";
		}
		Arrays.sort(strs, new MyComparator());
		String res = "";
		for (int i = 0; i < strs.length; i++) {
			res += strs[i];
		}
		return res;
    }

1.安排会议

每一次都选结束时间最早的

	public static class Program {
		public int start;
		public int end;

		public Program(int start, int end) {
			this.start = start;
			this.end = end;
		}

	public static int bestArrange2(Program[] programs) {
		Arrays.sort(programs, new ProgramComparator());
		int timeLine = 0;
		int result = 0;
		// 依次遍历每一个会议，结束时间早的会议先遍历
		for (int i = 0; i < programs.length; i++) {
            // 当前时间 <= 会议开始时间
			if (timeLine <= programs[i].start) {
				result++;
				timeLine = programs[i].end; // 更新时间
			}
		}
		return result;
	}

	public static class ProgramComparator implements Comparator<Program> {
		@Override
		public int compare(Program o1, Program o2) {
			return o1.end - o2.end;
		}
	}
//return o1 - o2，那么就是 return dest[j-1] - dest[j]。
//当 dest[j-1] > dest[j] 时，就进行交换。当 dest[j-1] <= dest[j] 时位置不变，从而达到数组升序。降序也是一样的道理，就不多讲了

2 . 哈夫曼数组切割

一个数组10 20 30

60切一刀为10和50，代价为60,50切一刀，代价为50 总：110

60切一刀为30和30，代价为60，30切一刀，代价30 总：90

• 利用一个小根堆，哈夫曼编码
• 每次弹出两个数，合成一个数，放进小根堆
• 代价为所有 合成数 的和

	public static int lessMoney2(int[] arr) {
		PriorityQueue<Integer> pQ = new PriorityQueue<>();
		for (int i = 0; i < arr.length; i++) {
			pQ.add(arr[i]);
		}
		int sum = 0;
		int cur = 0;
        // 小根堆只剩一个数的时候停止
		while (pQ.size() > 1) {
			cur = pQ.poll() + pQ.poll();
			sum += cur; // 代价
			pQ.add(cur);
		}
		return sum;
	}

3. 类银行家算法贪心

输入:正数数组costs、正数数组profits、 正数K、正数M

• costs[0]表示i号项目的花费
• profits[]表示i号项目在扣除花费之后还能挣到的钱(利润)
• K表示你只能串行的最多做k个项目
• M表示你初始的资金 说明:每做完一个项目，马上获得的收益，可以支持你去做下一 个项目不能并行的做项目。 输出:你最后获得的最大钱数。

1. 小根堆（花费排序）
2. 大根堆（利润排序）
3. 小根堆解锁到大根堆，然后从大根堆顶取出do

	public static class Program {
		public int p;
		public int c;

		public Program(int p, int c) {
			this.p = p;
			this.c = c;
		}
	}

	public static class MinCostComparator implements Comparator<Program> {
		@Override
		public int compare(Program o1, Program o2) {
			return o1.c - o2.c;
		}
	}

	public static class MaxProfitComparator implements Comparator<Program> {
		@Override
		public int compare(Program o1, Program o2) {
			return o2.p - o1.p;
		}
	}

	// 最多K个项目
	// W是初始资金
	// Profits[] Capital[] 一定等长
	// 返回最终最大的资金
	public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
		PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
		PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        // 开始把所有项目放到小根堆
		for (int i = 0; i < Profits.length; i++) {
			minCostQ.add(new Program(Profits[i], Capital[i]));
		}
        // 拿K个项目
		for (int i = 0; i < K; i++) {
            // 小根堆不为空 当前项目花费资金 <= 当前拥有资金
			while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
				maxProfitQ.add(minCostQ.poll());
			}
            // 有可能完不成K轮 提前结束
			if (maxProfitQ.isEmpty()) {
				return W;
			}
            // 大根堆不为空  直接弹出堆顶元素
			W += maxProfitQ.poll().p;
		}
		return W;
	}

4. 点灯

给定一个字符串str，只由'X’ 和 . 两种字符构成。 'X’表示墙，不能放灯，也不需要点亮 '.'表示居民点，可以放灯，需要点亮 如果灯放在i位置，可以让i-1， i 和 i+1三个位置被点亮 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯

策略：
如果i位置是个X 直接跳到i+1位置
如果i位置是个. 如果i+1是X，灯+1，跳到i+2
如果i位置是个. 如果i+2是X，灯+1，跳到i+3
如果i位置是个. 如果i+3是X，灯+1，跳到i+4

	public static int minLight2(String road) {
		char[] str = road.toCharArray();
		int i = 0;
		int light = 0;
		while (i < str.length) {
			if (str[i] == 'X') {
				i++;
			} else {
				light++;
				if (i + 1 == str.length) {
					break;
				} else { // 有i位置  i+ 1   X  .
					if (str[i + 1] == 'X') {
						i = i + 2;
					} else {
						i = i + 3;
					}
				}
			}
		}
		return light;
	}