LeetCode 135:candy問題解Python
标题:子供一人一人にrating値があり、子供一人一人にキャンディを割り当てます.もしある子供のratingが隣の誰かより高いなら、彼のキャンディも彼より多いです.最低でもキャンディをいくら出す必要がありますか?
これは欲張りで、まず端を掃いて、シーケンスが増えれば、キャンディの数は順番に1を加えて、小さくなったら1にします.最も少ないキャンディシーケンスが得られた.
そしてもう一度欲張る.最後に2つのシーケンスをmaxを求めて加算すればいいです
>.<久しぶりにアルゴリズムを作ってずっと水の問題をしています.pythonを習ったつもりにしましょう.
実習はあまり問題を作る時間がありませんが.しかしやはり毎日堅持しなければなりません!
これは欲張りで、まず端を掃いて、シーケンスが増えれば、キャンディの数は順番に1を加えて、小さくなったら1にします.最も少ないキャンディシーケンスが得られた.
そしてもう一度欲張る.最後に2つのシーケンスをmaxを求めて加算すればいいです
>.<久しぶりにアルゴリズムを作ってずっと水の問題をしています.pythonを習ったつもりにしましょう.
class Solution:
# @param {integer[]} ratings
# @return {integer}
def candy(self, ratings):
num = [1]
cnt = 1
for i in range(1,len(ratings)) :
if ratings[i]>ratings[i-1] :
cnt += 1
else :
cnt = 1
num.append(cnt)
# ans = num.pop()
ans = num[len(ratings)-1]
cnt = 1
for i in range(len(ratings)-1,0,-1) :
if ratings[i-1]>ratings[i] :
cnt += 1
else :
cnt = 1
ans += max ( num[i-1], cnt )
return ans
if __name__ == '__main__' :
a = Solution ()
ratings = [1,2,3,4,3,2,1]
ans2 = a.candy(ratings)
print ans2
~
~
実習はあまり問題を作る時間がありませんが.しかしやはり毎日堅持しなければなりません!