TechNomads

今天，我们先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。

1.买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路：

func maxProfit(prices []int) int {
	// 1. 暴力 双重循环
	//max := 0
	//length := len(prices)
	//for i := 0; i < length - 1; i++ {
	//	j := i +1
	//
	//	for j < length && prices[i] < prices[j] {
	//		temp := prices[j] - prices[i]
	//		if temp > max {
	//			max = temp
	//		}
	//		j++
	//	}
	//}
	//return max
	// 2. 贪心算法，单层循环
	min := math.MaxInt32
	max := 0
	for _, price := range prices {
		if price < min {
			min = price
		}

		temp := price - min
		if temp > max {
			max = temp
		}
	}
	return max
}

2.分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

解题思路：通过正反两次遍历解决，GO实现代码如下：

func candy(ratings []int) int {

	length := len(ratings)
	var candies [] int

	// 正序
	for k, v := range ratings {
		candies = append(candies, 1)

		if k > 0 && v > ratings[k-1] {
			candies[k] = candies[k-1] + 1
		}
	}

	// 倒序
	for j := length - 2; j >= 0; j-- {
		if ratings[j] > ratings[j+1] && candies[j] <= candies[j+1] {
			candies[j] = candies[j+1] + 1
		}
	}

	var count int

	for _, v := range candies {
		count += v
	}
	return count
}

3.判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:
s = "abc", t = "ahbgdc"

返回 true.

示例 2:
s = "axc", t = "ahbgdc"

返回 false.

解题思路：双重循环去遍历，外层循环是子序列T，内层循环是字符串S，从S中找到T的第一个字符后j++判断下一个位置，通过计数器累加，最终判断计数器是否等于T的长度

func isSubsequence(s string, t string) bool {

	sMatchLen := 0
	j := 0
	for i := 0; i < len(s); i++ {

		for  j < len(t) {
			if s[i] == t[j] {
				sMatchLen++
				j++
				break
			}
			j++
		}
	}

	return sMatchLen == len(s)
}

4.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

 
示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

解题思路：先对两个数组排序。然后双重循环解决，外层循环是糖果S，内层循环是孩子G，G[j] <= S[i] 则能发成功一个糖果

func findContentChildren(g []int, s []int) int {
	if len(g) < 0 || len(s) < 0 {
		return 0
	}

	count := 0

	sort.Ints(g)
	sort.Ints(s)
	j:=0
	for i:=0; i<len(g); i++ {

		for j<len(s)  {
			if g[i] <= s[j]  {
				count ++
				j++
				break
			}

			j++
		}
	}

	return count
}

func  contails(target[] int, t int ) bool  {

	for _, v := range target {
		if v == t {
			return true
		}
	}
	return false
}