前言

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

主要就是讲几道题

  1. 拼接字符串问题
  2. 哈夫曼编码问题
  3. IPO问题
  4. 项目宣讲问题

贪心算法

也叫贪婪算法(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; 
	}