09-贪心算法解题思路.md

[TOC]

# 1 贪心算法

## 1.1 基本概念

1、最自然智慧的算法

2、用一种局部最功利的标准，总是能做出在当前看来是最好的选择

3、难点在于证明局部最优解可以最终得到全局最优解

4、对于贪心算法的学习主要是以经验为主，尝试为主

### 1.2.1 贪心算法解释

正例：通过一个例子来解释，假设一个数组中N个正数，第一个挑选出来的数乘以1，第二个挑选出来的数乘以2，同理，第N次挑选出来的数乘以N，总的加起来是我们的分数。怎么挑选数字使我们达到最大分数？

> 数组按从小到大的顺序排序，我们按顺序依次挑选，最终结果就是最大的。本质思想是因子随着挑选次数的增加会增大，我们尽量让大数去结合大的因子。

> 贪心算法有时是无效的，下文会举贪心算法无效的例子

### 1.2.2 贪心算法的证明问题

如何证明贪心算法的有效性？

> 一般来说，贪心算法不推荐证明，很多时候证明是非常复杂的。通过下面例子来说明贪心算法证明的复杂性；

例子：给定一个由字符串组成的数组strs，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果。

> 字典序概念：直观理解，两个单词放到字典中，从头开始查找这个单词，哪个先被查找到，哪个字典序小。

> 字典序严格定义，我们把字符串当成k进制的数，a-z当成26进制的正数，字符长度一样，abk>abc，那么我们说abk的字典序更大。字符长度不一样ac和b，那么我们要把短的用0补齐，0小于a的accil，那么ac<b0，高位b>a即可比较出来大小。

常见的语言标准库中比较字符串的函数，大都是比较字典序。

思路1：按照单个元素字典序贪心，例如在[ac,bk,sc,ket]字符串数组中，我们拼接出来最终的字符串字典序最小，那么我们依次挑选字典序最小的进行拼接的贪心策略得到acbkketsc。

> 但是这样的贪心不一定是正确的，例如[ba,b]按照上述思路的贪心结果是bba，但是bab明显是最小的结果

思路2：两个元素x和y，x拼接y小于等于y拼接x，那么x放前，否则y放前面。例如x=b,y=ba。bba大于bab的字典序，那么ba放前面


证明：

我们把拼接当成k进制数的数学运算，把a-z的数当成26进制的数，'ks'拼接'ts'实质是ks * 26^2 + te。

目标先证明我们比较的传递性：证明a拼接b小于b拼接a，b拼接c小于等于c拼接b，推导出a拼接c小于等于c拼接a。

a拼接b等于a乘以k的b长度次方 + b。我们把k的x长度次方这个操作当成m(x)函数。所以：

```math
a * m(b) + b <= b * m(a) + a  

b * m(c) + c <= c * m(b) + b 

=> 

a * m(b) * c <= b * m(a) * c + ac - bc

b * m(c) * a + ca - ba <= c * m(b) * a 

=>

b * m(c) * a + ca - ba <= b * m(a) * c + ac - bc

=> 

m(c) * a + c <= m(a) * c + a

```

至此，我们证明出我们的排序具有传递性质。

根据我们排序策略得到的一组序列，证明我们任意交换两个字符的位置，都会得到更大的字典序。


例如按照思路二得到的amnb序列，我们交换a和b。我们先把a和m交换，由于按照思路二得到的序列，满足a.m <= m.a 那么所以manb > amnb，同理得到amnb < bmna。

再证明任意三个交换都会变为更大的字典序，那么最终数学归纳法，得到思路二的正确性

> 所以贪心算法的证明实质是比较复杂的，我们大可不必每次去证明贪心的正确性

```Go
package main

import (
	"sort"
	"strings"
)

// 方法1 暴力法穷举，排列组合。略

// LowestStringByGreedy 方法2 贪心法
func LowestStringByGreedy(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	Sort(strs, func(a, b string) int {
		return strings.Compare(a, b)
	})

	res := ""
	for i := 0; i < len(strs); i++ {
		res += strs[i]
	}
	return res
}

type Comparator func(a, b string) int

func Sort(values []string, comparator Comparator) {
	sort.Sort(sortable{values, comparator})
}

type sortable struct {
	values     []string
	comparator Comparator
}

func (s sortable) Len() int {
	return len(s.values)
}

func (s sortable) Swap(i, j int) {
	s.values[i], s.values[j] = s.values[j], s.values[i]
}

func (s sortable) Less(i, j int) bool {
	return s.comparator(s.values[i], s.values[j]) < 0
}
```

> 全排列的时间复杂度为：O(N!)

> 每一种贪心算法有可能都有属于他自身的特有证明，例如哈夫曼树算法，证明千变万化

> 贪心策略算法，尽量不要陷入复杂的证明

## 1.2 贪心算法求解思路

### 1.2.1 标准求解过程

1、分析业务

2、根据业务逻辑找到不同的贪心策略

3、对于能举出反例的策略，直接跳过，不能举出反例的策略要证明有效性，这往往是比较困难的，要求数学能力很高且不具有统一的技巧性

### 1.2.2 贪心算法解题套路

1、实现一个不依靠贪心策略的解法X,可以用暴力尝试

2、脑补出贪心策略A,贪心策略B,贪心策略C......

3、用解法X和对数器，用实验的方式得知哪个贪心策略正确

4、不要去纠结贪心策略的证明

> 贪心类的题目在笔试中，出现的概率高达6到7成，而面试中出现贪心的概率不到2成。因为笔试要的是淘汰率，面试要的是区分度。由于贪心的解决完全取决于贪心策略有没有想对，有很高的淘汰率但是没有很好的区分度

## 1.3 贪心算法套路解题实战

### 1.3.1 例一：会议日程安排问题

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目宣讲。给你每个项目的开始时间和结束时间，你来安排宣讲的日程，要求会议室进行宣讲的场数最多。

返回最多的宣讲场次。

> 思路：本题常见的几种贪心策略，一种是按照谁先开始安排谁，第二种按照持续时间短的先安排，第三种按照谁先结束安排谁。

> 通过验证，无需证明得出第三种贪心策略是正确的

```Go
package main

import "sort"

type Program struct {
	start int
	end   int
}

type Programs []*Program

func bestArrange(programs Programs) int {
	sort.Sort(programs)
	// timeline表示来到的时间点
	timeLine := 0
	// result表示安排了多少个会议
	result := 0
	// 由于刚才按照结束时间排序，当前是按照谁结束时间早的顺序遍历
	for i := 0; i < len(programs); i++ {
		if timeLine <= programs[i].start {
			result++
			timeLine = programs[i].end
		}
	}
	return result
}

func (p Programs) Len() int {
	return len(p)
}

// Less 根据谁的结束时间早排序
func (p Programs) Less(i, j int) bool {
	return p[i].end-p[j].end > 0
}

func (p Programs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}
```

### 1.3.2 例二：居民楼路灯问题

给定一个字符串str，只由‘X’和‘.’两个字符构成。

‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。

如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮，返回如果点亮str中所需要点亮的位置，至少需要几盏灯

例如： X..X......X..X. 需要至少5盏灯

```Go
package main

// minLight 给定一个由'X'和'.'组成的居民楼路径。要照亮所有居民楼，返回最少需要几盏灯
func minLight(road string) int {
	str := []byte(road)
	// index从0出发
	index := 0
	// 当前灯的个数
	light := 0
	for index < len(str) {
		// 当前i位置是X，直接跳到下一个位置做决定
		if str[index] == 'X' {
			index++
		} else { // i 位置是 . 不管i+1是X还是.当前区域需要放灯
			light++
			// 接下来没字符了，遍历结束
			if index + 1 == len(str) {
				break
			} else {
				// 如果i+1位置是X，在i位置放灯，去i+2位置做决定
				if str[index + 1] == 'X' {
					index = index + 2
				} else { // i位置是. i+1也是. 那么不管i+2是什么，都在i+1位置放灯，到i+3去做决定
					index = index + 3
				}
			}
		}
	}
	return light
}
```

### 1.3.3 例三：哈夫曼树问题

一根金条切成两半，是需要花费和长度值一样的铜板的。

比如长度为20的金条，不管怎么切，都需要花费20个铜板。一群人想整分整块金条，怎么分最省铜板？

例如：给定数组[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个铜板。

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

> 小根堆，大根堆，排序。是贪心策略最常用的手段，coding代码量很少。因为堆天然就具备根据我们自定义的排序规则重新组织数据

```Go
package main

import (
	"container/heap"
	"fmt"
)

// CutCost Array 例如[10, 20, 30]表示价值为60的金条，需要切割成10 20 30的条段给三个人分
type CutCost struct {
	Array []int
}

func (c CutCost)Len() int {
	return len(c.Array)
}

func (c CutCost)Less(i, j int) bool {
	return c.Array[i] > c.Array[j]
}

func (c CutCost)Swap(i, j int) {
	c.Array[i], c.Array[j] = c.Array[j], c.Array[i]
}

func (c *CutCost) Push(h interface{}) {
	c.Array = append(c.Array, h.(int))
}

func (c *CutCost) Pop() (x interface{}) {
	n := len(c.Array)
	x = c.Array[n - 1]
	c.Array = c.Array[:n-1]
	return x
}

// 切金条，贪心解法，建立一个小根堆，把所有数扔进去
func lessMoney (c *CutCost) int {
	fmt.Println("原始slice: ", c.Array)

	heap.Init(c)
	// 通过堆初始化后的arr
	fmt.Println("堆初始化后的slice:", c.Array)

	sum := 0
	cur := 0
	for len(c.Array) > 1 {
		// 每一次弹出两个数，合并成一个数
		// 合成的数一定输非叶子节点
		cur = c.Pop().(int) + c.Pop().(int)
		// 把合成的数累加到sum中去
		sum += cur
		// 把合成的数加入小根堆中
		c.Push(cur)
	}
	return sum
}
```

### 1.3.4 例四：项目花费和利润问题

输入：正数数组costs，正数数组profits,正数K,正数M

costs[i]表示i号项目的花费，profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）

K表示你只能串行的最多K个项目，M表示你的初始资金。

说明：每做完一个项目，马上获得收益，可以支持你去做下一个项目。不能并行的做项目。

输出：你最后获得的最大钱数。

```Go
package main

import (
	"container/heap"
)

// Item 项目
type Item struct {
	C int
	P int
}

// MinCostQ 项目最小花费。由花费组织的小根堆
type MinCostQ struct {
	Items []*Item
}

func (c MinCostQ) Len() int {
	return len(c.Items)
}

// Less i对应的花费C的值小于j对应的值为true，则从小到大排序，即小根堆
func (c MinCostQ) Less(i, j int) bool {
	return c.Items[i].C < c.Items[j].C
}

func (c MinCostQ) Swap(i, j int) {
	c.Items[i], c.Items[j] = c.Items[j], c.Items[i]
}

func (c *MinCostQ) Push(h interface{}) {
	c.Items = append(c.Items, h.(*Item))
}

func (c *MinCostQ) Pop() (x interface{}) {
	n := len(c.Items)
	x = c.Items[n-1]
	c.Items = c.Items[:n-1]
	return x
}

// MaxProfitQ 项目最大利润，由利润组织的大根堆
type MaxProfitQ struct {
	Items []*Item
}

func (c MaxProfitQ) Len() int {
	return len(c.Items)
}

// Less i对应的利润P的值大于j对应的值为true，则从大到小排序，即大根堆
func (c MaxProfitQ) Less(i, j int) bool {
	return c.Items[i].P > c.Items[j].P
}

func (c MaxProfitQ) Swap(i, j int) {
	c.Items[i], c.Items[j] = c.Items[j], c.Items[i]
}

func (c *MaxProfitQ) Push(h interface{}) {
	c.Items = append(c.Items, h.(*Item))
}

func (c *MaxProfitQ) Pop() (x interface{}) {
	n := len(c.Items)
	x = c.Items[n-1]
	c.Items = c.Items[:n-1]
	return x
}

// findMaximizedCapital 找到项目最大利润。由于Profits和Capital一一对应
// K表示你只能串行的最多K个项目，M表示你的初始资金。
func findMaximizedCapital(K, W int, Profits, Capital []int) int {
	Items := make([]*Item, 0)
	for i := 0; i < len(Profits); i++ {
		im := &Item{
			C: Capital[i],
			P: Profits[i],
		}
		Items = append(Items, im)
	}
	minC := &MinCostQ{
		Items: Items,
	}

	maxQ := &MaxProfitQ{
		Items: Items,
	}

	// 由花费组织的小根堆。初始化
	heap.Init(minC)
	// 由利润组织的大根堆。初始化
	heap.Init(maxQ)

	// 做k轮项目
	for i := 0; i < K; i++ {
		// 小根堆不为空，且堆顶的花费被我当前启动资金cover住
		for len(minC.Items) != 0 && minC.Items[len(minC.Items) - 1].C <= W {
			// 小根堆的堆顶扔到大根堆中去
			maxQ.Push(minC.Pop())
		}
		// 大根堆没有可以做的项目，直接返回总钱数
		if len(maxQ.Items) == 0 {
			return W
		}
		// 大根堆不为空，堆顶元素的利润直接加到我们的总钱数上
		// 大根堆弹出堆顶元素
		W += maxQ.Pop().(Item).P
	}
	return W
}
```