leetcode 455. Assign Cookies

https://leetcode.com/problems/assign-cookies/

ビスケットをできるだけ多くの子供に分ける.
注意すべき点->適切な割り当てを行うと、問題は簡単に解決されますが、例ではすべての入力値が整列しているため、混同される可能性がありますが、元の問題には値の整列の制約がありません.したがって、コードの上部で直接ソートする必要があります.
草.階調アルゴリズム.

def findContentChildren(self, g: List[int], s: List[int]) -> int:
	g.sort()
    s.sort()
    
    child_i = 0 
    cookie_j = 0
    
    while child_i < len(g) and cookie_j < len(s):
    	if s[cookie_j] >= g[child_i]:
        	child_i += 1
        cookie_j += 1
        
    return child_i

ソート後にサイズを比較し、s[cookie j]>=g[child i]の場合、実行順序は次の子供child i+=である.
草.バイナリ検索(データブラウズ範囲を半分に縮小).

def findContentChildren(self, g: List[int], s: List[int]) -> int:
	g.sort()
    s.sort()
    
    result = 0
    for i in s:
    	index = bisect.bisect_right(g, i)
        if index > result:
        	result += 1
    return result

両方のリストは順番にブラウズするのではなく、1つのリストと同時にバイナリ検索の方法です.次に、現在与えられている子供よりも多くのインデックスを見つけると、より多くのクッキーを与えることができるので、子供の数を増やすことができます.bisect library?:エレメントソートリストで特定のエレメントを検索するときに有効なライブラリ.

対left(list,data):リストにデータを挿入する最も左側のインデックスを検索するための関数(リスト内のソート順を維持します).

対分right(list,data):リストにデータを挿入する右端インデックスの関数を検索します(リストのソート順を維持します).

from bisect import bisect_left, bisect_right

g = [1,2,3,4,5]
i = 3

print(bisect.bisect_left(g, i))     # 2
print(bisect.bisect_right(g, i))    # 3

のり付けバイナリツリー(ヒップホップ)

class Solution:
	def findContentChildren(self, g: List[int], s: List[int]) -> int:
    	heapq.heapify(g) # 리스트를 힙으로 만들기
        heapq.heapify(s) # 리스트를 힙으로 만들기
        
        count: int = 0
        while (s and g):
        	# greed factor
            gf = heapq.heappop(g) # pop하기
            
            # cookie size
            cs = heapq.heappop(s)
            while (s and cs < gf):
            	cs = heapq.heappop(s)
                
            if (cs >= gf):
            	count += 1
            else:
            	break
                
        return count

グリッド係数はロッドの順番に、クッキーを先にあげ、両方とも最小ヒップで管理します.힙 자료구조 및 heapq modulehipは特定のルールを持つツリーであり,基本的には最値と最切り上げを迅速に検索するために設計された完全バイナリツリーである.

最小ヒップホップ:親ノードのキー値が常に子ノードのキー値より小さいヒップホップ

最大臀部:親ノードのキー値が常に子ノードのキー値より大きい臀部
(キー値のサイズ関係は親/子ノード間でのみ成立し、兄弟ノード間ではサイズ関係が確定しません.)

heapqモジュール->heapq(優先キュー)アルゴリズムの提供
すべての親ノードは、そのサブノード値より小さいまたはそれより大きいバイナリツリー構造であり、内部はインデックス0から始まり、k個の要素は常にサブ要素(2 k+1、2 k+2)の最小hop以下の形式で並べ替えられる.

Reference.

トニーパークのブログ

あなたのブログ

LittleFoxのhip資料構造整理