未分類

Assign Cookies

Go, Greedy, LeetCode

Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:

You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

1
2
3
4
5
6
7
Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

1
2
3
4
5
6
7
Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.
提示 解題應用
Greedy Sort

Default:

1
2
3
func findContentChildren(g []int, s []int) int {
}

解答思路:

原本想說將其中一項儲至hashMap之中來讓另一配對尋找，不過餅乾比慾望多的情形也能滿足條件，所以終究還是會回到餅乾與慾望在大小上的比較，既然如此倒不如一開始就將欲望大小與餅乾大小都做排序，接著開始分配餅乾，如果從最小塊的餅乾能滿足小於等於其欲望就分配該塊給他，繼續往下分配給其它的小朋友，如果該塊餅乾無法滿足他，那麼肯定後頭的小朋友也無法滿足，直接換大塊點來繼續做判斷，最後直到能發出的餅乾都分完了或每個小朋友都已經拿到了才結束。

程式碼解說:

因為需要比較餅乾與慾望，所以一開始就用內建的library將兩項資料陣列做由小至大的排序，如此一來稍後就可以很容易處理大小比較的問題，接著利用一迴圈開始從最小塊的餅乾開始分配，如果餅乾無法滿足其慾望，就直接換下一塊餅乾，若足以滿足其欲望就換下一個小朋友(計數+1)，當所有的小朋友都已經分配到餅乾(餅乾還有剩)就跳出回圈或餅乾已經沒了，最後才回傳計數的結果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var content int
var count int
sort.Ints(g)
sort.Ints(s)
for _, cookie := range s {
	content = g[count]
	if cookie < content {
		continue
	} else {
		count++
		if count == len(g) {
			break
		}
	}
}
return count

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func findContentChildren(g []int, s []int) int {
	var content int
	var count int
	sort.Ints(g)
	sort.Ints(s)
	for _, cookie := range s {
		content = g[count]
		if cookie < content {
			continue
		} else {
			count++
			if count == len(g) {
				break
			}
		}
	}
	return count
}

總結:

對於分配餅乾與能滿足慾望上的分配，要找出最多能滿足的小朋友就是標準的貪心問題，因為餅乾比慾望多的情形也能滿足條件，終究還是會回到餅乾與慾望在大小上的比較，所以將給予的資料(餅乾與慾望)都做排序，如此一來就可以很輕易的找出答案了。

分享到