前言
贪心算法(Greedy Algorithm)是一种常用的优化算法,它在每一步选择中都采取当前状态下最优的选择,以期望达到全局最优解。
分发饼干
leetcode-455 简单
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
局部最优:既能满足孩子,还消耗最少。
- 对饼干数组和胃口数组升序排序。
- 遍历饼干数组,找到能满足第一个孩子的饼干。
- 然后继续遍历饼干数组,找到满足第二、三、……、n个孩子的饼干。
1 2 3 4 5 6 7 8 9 10 11 12 13
| function findContentChildren(g,s) { const sort = (a,b) => a - b; g.sort(sort); s.sort(sort); let i = 0; s.forEach(n => { if (n >= g[i]) { i++; } }) return i }
|
go代码演示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| package main
import ( "fmt" "sort" )
func findContentChildren(g, s []int) int { sort.Ints(g) sort.Ints(s) i := 0 for n := range s { if n >= g[i] { i++ } } return i }
func main() { g := []int{1, 2} s := []int{1, 1, 3}
n := findContentChildren(g, s) fmt.Println(n) }
|