[アルゴリズム]より辛い

5357 ワード
テキストリンク

1.質問



2.私の回答

import heapq
def solution(scoville, k):
    heap = []
    answer = 0 
    
    for num in scoville: 
        heapq.heappush(heap, num)
    
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + heapq.heappop(heap) * 2)
            answer += 1
        except IndexError:
            answer=-1
            break
    return answer
これはグーグルの助けで解決できる問題です.sortの後、私はアルゴリズムを考え出して、前の2つの数字を取り出して、新しいスコビルを生成しましたが、ずっと効率的に失敗していました.Google検索では、一般的なheapqリストとは異なり、push、popを検索するたびに自動的にソートされるやつが存在することが分かった.これにより、ソートコストが削減され、効率の問題が解決されます.
すべての食品のスコビル指数がK以上に達しない場合、-1はreturnである.なかなか思いつかない状況.最初は0が2つしか存在しないと思っていた場合がありましたが、考えてみれば、食べ物を混ぜても1つしか残っていない場合もありますし、K未満の場合もあります.上記の状況はIndexErrorによって解決された.

3.他人の回答

import heapq as hq
def solution(scoville, K):
    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  
    return answer
他の人もほとんどheapqを使って問題を解いています.以上のコードで学んだのは,for文を用いずにリストをheapify構造に変更できることである.また,heapを用いず,IndexErrorを用いた場合,len == 0を得る方法も興味深い.

4.勉強するところ


python heapモジュールの使用
[伯俊]No 2447-星を撮る10(JAVA)
Fitness使用シリーズ8