白筱汐

想都是问题,做都是答案

0%

贪心算法-分发饼干

前言

贪心算法(Greedy Algorithm)是一种常用的优化算法,它在每一步选择中都采取当前状态下最优的选择,以期望达到全局最优解。

分发饼干

leetcode-455 简单

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

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

局部最优:既能满足孩子,还消耗最少。

  1. 对饼干数组和胃口数组升序排序。
  2. 遍历饼干数组,找到能满足第一个孩子的饼干。
  3. 然后继续遍历饼干数组,找到满足第二、三、……、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)
}