【leetcode】欲張りアルゴリズム1338 455

Online Judgeとアルゴリズムの特徴牛客網は標準的な入出力であり、leetcodeは書く関数であり、面接前に両者とも

訓練を行う.

貪欲なテーマ

試み証明------>貪欲な

を使うことができます

は反証を探します---------->証明は貪欲な

を使うことができません

他に方法がなければ、彼が貪欲だと信じて、次は

をもっと練習します.

題面解読:

題面に「最も」または等価な字が現れるのは貪欲な

かもしれない.

貪欲なテーマには必ず「最」の字がある.

貪欲は往々にしてソートを伴う(ソートは潜在的に貪欲が言及した「良い」を定義しているため)

.
1338配列サイズ半減

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        count_total = 0
        for i,count in enumerate(sorted(collections.Counter(arr).values(),reverse = True)):
            count_total += count 
            if count_total >= len(arr) / 2:
                return i + 1

455.ビスケットを配る

class Solution:
    def findContentChildren(self, g, s):
        g.sort(reverse = True)
        s.sort(reverse = True)

        i = j = 0
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                j += 1
            i += 1
        return j