LeetCode 455 分發餅乾

2022-09-22 06:02:08 字數 1466 閱讀 9693

問題描述:

假設你是一位很棒的家長,想要給你的孩子們一些小餅乾。但是,每個孩子最多隻能給一塊餅乾。對每個孩子 i ,都有一個胃口值 gi ,這是能讓孩子們滿足胃口的餅乾的最小尺寸;並且每塊餅乾 j ,都有一個尺寸 sj 。如果 sj >= gi ,我們可以將這個餅乾 j 分配給孩子 i ,這個孩子會得到滿足。你的目標是儘可能滿足越多數量的孩子,並輸出這個最大數值。

注意:

你可以假設胃口值為正。

一個小朋友最多隻能擁有一塊餅乾。

示例 1:

輸入:[1,2,3], [1,1]輸出:1解釋:你有三個孩子和兩塊小餅乾,3個孩子的胃口值分別是:1,2,3。

雖然你有兩塊小餅乾,由於他們的尺寸都是1,你只能讓胃口值是1的孩子滿足。

所以你應該輸出1。

示例 2:

輸入:[1,2], [1,2,3]輸出:2解釋:你有兩個孩子和三塊小餅乾,2個孩子的胃口值分別是1,2。

你擁有的餅乾數量和尺寸都足以讓所有孩子滿足。

所以你應該輸出2.

方法1:g = [10,9,8,7] s =[5,6,7,8] sort 和逆序之後 g = [10,9,8,7] s =[8,7,6,5]  用j,i進行索引,s[i] - s[j] >= 0 則 num++ i ++ j ++ ,else j ++

1

class

solution(object):

2def

findcontentchildren(self, g, s):

3"""

4:type g: list[int]

5:type s: list[int]

6:rtype: int

7"""

8g.sort()

9s.sort()

10 g_len =len(g)

11 s_len =len(s)

12 s = s[::-1]

13 g= g[::-1]

14 num=0

15 i,j =0,0

16while i < s_len and j 17if s[i] - g[j] >=0:

18 num += 1

19 i += 1

20 j += 1

21else

:22 j += 1

23return num

2018-10-03 20:52:30

LeetCode 455 分發餅乾(C )

假設你是一位很棒的家長,想要給你的孩子們一些小餅乾。但是,每個孩子最多隻能給一塊餅乾。對每個孩子 i ,都有一個胃口值 gi ,這是能讓孩子...

LeetCode455 分發餅乾

直接類似雙指標比較,本質就是貪心,小餅乾給小的胃口,貪心小胃口 1 class solution 10else i 11 12return res 13 14 大尺寸的餅乾既可以滿足胃口大的孩子也可以滿足胃口小的孩子,那麼就應該優先滿足胃口大的。這裡的區域性最優就是大餅乾餵給胃口大的,充分利用餅乾尺寸...

LeetCode 安排工作以達到最大收益 455

有一些工作 difficulty i 表示第i個工作的難度,profit i 表示第i個工作的收益。 現在我們有一些工人。worker i...