前言

之前也是看过一遍，但那时候都是纠结于比较器那里。现在就是想从头梳理一下。

主要就是讲几道题

拼接字符串问题
哈夫曼编码问题
IPO问题
项目宣讲问题

贪心算法

也叫贪婪算法（greedy algorithm）。顾名思义，就是每一步都要做到最好，这就是很贪婪了…
主要就是在贪心策略上强大。但遇到一个问题时，可能会想出、会脑补出很多策略来进行实现，至于那个是对的，就不好说了。在贪心策略的证明上，会耗费很多时间，如果时间有限的话，还是不要轻易去证明这个策略为什么对，反正就是可以这么来解决问题就是了。这个贪心策略的选择跟个人的经验值有关…
不要去纠结怎么证明这个贪心策略为什么对。

比较器 ：（因为是用java实现的）这里先说说比较器的使用。在用贪心策略时，有些是把给的数据按我们的贪心要求把它排好序，这里就要用到比较器。 compare，还是compareTo方法，都是返回一个int型。
还是当做一种模式把它记住就好了，（因为至于内部传给构造函数时是怎么排的，我不清楚…）
（在compare方法中：compare（第一个参数，第二个参数））
就是如果是按照从小到大排序，就用第一个参数减第二个参数。
　　如果是按照从大到下排序，就用第二个参数减第一个参数。
（在compareTo中类比就是：第一个参数.compareTo(第二参数) ）

第一题

上题目：

思路：

因为要拼接成字符串的字典序最小的，所以有一种很自然的想法：把原数组中的字符串都按照从小到大排完序，再依次将这些字符串拼接起来即可（每一个都要最小，在每一个上贪）。但是！but！however！这样的做法是错误的！
可以举出反例：就题目里的b，ba；这就是每个字符串按字典序排好了的，但是这样返回的是bba，不符合题目要求！

所以，另一种贪心的选择： 2个2个的比较，比如说有x，y这两个字符串：
看看是x+y的字典序小还是 y+x的字典序小，以次来看是x放前面还是 y放前面。（在2个中的整体上来贪）
证明这贪心策略为什么是对的，就比较麻烦了，这里从略。主要是证明①.这个策略有传递性，还有②.以这个策略排出来再拼接出来的字符串字典序一定是最小。任意交换2个字符串，产生新的拼接后的字符串的字典序都比之前的要大。
证明的思路：就是把字符串看成一个k进制的数，把数来比大小…

上代码：

   public static class MyComparator implements Comparator<String>{
   
		 
		public int compare(String a, String b) {
   
			return (a+b).compareTo(b+a);  // 按从小到大的顺序排列
		} 	
	}
	
	public static String lowestString(String[] s) {
   
		if(s == null) {
   
			return "";
		}
		
		String res = "";
		Arrays.sort(s, new MyComparator() );
		for(String str : s) {
   
			res += str;
		}
		return res;
	}

第二题

题目：

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为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 再把长度30金条分成10和20，花费30 一共花费90铜板。

输入一个数组，返回分割的最小代价

思路：

一开始想的是从原本的一整块怎么怎么分下来，可是到这里就没办法了。
所以，从最终结果开始。因为是先把要分成的结果直接给你，让你选择哪种分法用的代价最小。
所以就在给的数组中每次拿出2个最小的数字，让他们加起来合并成一个数字再装回去。这样就是分金块的时候的最后一步，把一个金块分成已知2个最小的金块，这样的代价是最小的。就在这个操作上一步一步往上贪上去，直到数组里只剩下一块金块，就是原来没分之前的大金块。在这中间记录每次合并后的代价在相加起来就是我们要求的最小代价。

其实，这样的做法就是构造一个哈夫曼树的过程，就是给你了数据之后，要你求这个数据的最小什么什么东西，应该都可以用构造哈夫曼树这个过程。
（题外话：说到哈夫曼树就有点头疼了，上次的期末考试数据结构考了哈夫曼树，那时我理解的是不对的，有问题，所以可能那题做错了吧…）

上代码：

	public static int lessCost(int[] arr) {
   
		if(arr == null) {
   
			return 0;
		}
		
		// java 提供的优先队列（堆）就是一个 最小堆
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for(int i : arr) {
   
			pq.add(i);
		}
		
		int sum = 0;
		int cur = 0;
		while(pq.size() > 1) {
   
			cur = pq.poll() + pq.poll();	// 每次拿出2个最小的，合并成一个数字
			sum += cur;  // 记录那个代价总和
			pq.add(cur);	// 把合并成一个的数字 再装回去
		}
		return sum;
	}

第三题

题目：

（LeetCode编号为502号题）

因为不知道IPO是什么意思，这里解释一下下：
IPO：首次公开募股（Initial Public Offerings）。
是指一家企业或公司（股份有限公司）第一次将它的股份向公众出售（首次公开发行，指股份公司首次向社会公众公开招股的发行方式）。

思路：

因为每次只能做一个项目，而且每个项目只能做一次。
很自然的，每次我们都想做收益最大的那个项目，赚了钱之后，看看还有没有之前因为钱不够不能做但收益最大的项目。在每个收益最大上贪。
这个策略很直白，这样也是对的。至于怎么证明为什么对，就不说了，我也不知道，反正就是对的。以人们的日常主观经验感受，这样做可以使最后的收益最多。

在代码实现时，就是准备一个最小堆（用来排序每个项目的启动资金从小到大排），全部项目信息装入这个堆中。再准备一个最大堆（用来排序每个项目的收益从大到小排）可以做的项目装入这个堆中，每次做的是这个堆顶的项目，也就是收益最大的项目。直到循环够了k次，或者最大堆里没元素了，就停，放回最大收益。

上代码：

	// 一个项目类; 项目就包含着2个信息，花费和收益。
	public static class Node{
   
		int c;	 // 花费
		int p;	 // 收益
		
		public Node(int cost, int profit) {
   
			c = cost;
			p = profit;
		}
	}
	
	public static class minCostComparator implements Comparator<Node>{
   
		
		public int compare(Node a, Node b) {
   
			return a.c - b.c;	// 按花费从小到大排序
		}
	}
	
	public static class maxProfitComparator implements Comparator<Node>{
   
		
		public int compare(Node a, Node b) {
   
			return b.p - a.p;	// 按收益从大到小排序
		}
	}
	
	public static int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
   
		Node[] nodes = new Node[Profits.length];
		for(int i = 0; i < nodes.length; i++){
   
			nodes[i] = new Node(Capital[i], Profits[i]);	// 看好自己怎么定义的，不要传错了！
		}
		
		PriorityQueue<Node> minCostQ = new PriorityQueue<Node>(new minCostComparator());
		PriorityQueue<Node> maxProfitQ = new PriorityQueue<Node>(new maxProfitComparator());
		for(Node node : nodes) {
   
			minCostQ.add(node);
		}
		
		// 循环k次停
		for(int i = 0; i < k; i++) {
   
			// 不能写成 minCostQ.peek().c <= W && !minCostQ.isEmpty() ；
			// 因为 有可能minCostQ里是空的，却还调用peek方***导致 空指针异常
			while(  !minCostQ.isEmpty() && minCostQ.peek().c <= W) {
   
				maxProfitQ.add( minCostQ.poll() );
			}
			if( maxProfitQ.isEmpty() ) {
   	// 最大堆里为空了，也就是没有项目可以做了的时候，停。
				return W;
			}
			W += maxProfitQ.poll().p; 
		}
		return W; 	
	}

第四题

题目：

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间(给你一个数组，里面是一个个具体的项目)，
你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。返回这个最多的宣讲场次。

思路：

先说说几种安排策略，也就是贪心策略。
①. 谁先开始就先安排谁。可是这样不对；
反例：有一个项目6点开始，占全天。
　　　这样就只能排一个，而其他的短时间的项目都不能排了。
②.谁的持续时间短就先排谁。这样也不对；
反例：有3个项目：一个6:00-9:00,占3小时；
　　　　　　　　　一个10:00-13:00,占3小时；
　　　　　　　　　一个8:50-10:50,占2小时。
　　　这样排的话，就只能排最后一个项目，而最多的方案是可以排前面2个项目。

正确的：
③谁先结束就先排谁。
因为只是要求安排可以宣讲的场数最多，不关心是一定要谁来宣讲。
所以就先安排早结束，后面有尽多的时间可以留出来。
至于怎么证明为什么对的，不知道…

上代码：

	//一个项目类
	public static class Program{
   
		int start;	//开始时间
		int end;	//结束时间
		
		public Program(int start, int end) {
   
			this.start = start;
			this.end = end;
		}
	}
	
	// 比较器
	public static class MyComparator implements Comparator<Program>{
   

		public int compare(Program a, Program b) {
   
			return a.end - b.end;	// 按结束的时间 从小到大排
		}
	}
	
	public static int bestArrange(Program[] pragrams, int start) {
   
		Arrays.sort( pragrams, new MyComparator() );
		int cur = start;
		int res = 0;
		for(Program p : pragrams) {
   		//从按要求排好序的数组中一个个来 选 
			if(cur <= p.start) {
   
				res++;
				cur = p.end;
			}
		}
		return res; 
	}

有关贪心算法的几道题

前言

贪心算法

第一题

上题目：

思路：

上代码：

第二题

题目：

思路：

上代码：

第三题

题目：

思路：

上代码：

第四题

题目：

思路：

上代码：