LeetCode Candy
LeetCode解題のCandy
原題
直線的にN人の子供が立っていて、すべての子供は自分の数字を持っていて、今以下の規則に従って子供にキャンディを配布します:すべての子供は少なくとも1つのキャンディがあります;隣の子の中で数字が大きい方が持っているキャンディも多いです.最低何個のキャンディを出すことを求めます.
注意点: なし
例:
入力:ratings=[1,2,3,2]
出力:7
問題を解く構想.
行った後に遍歴する時、私達は昇順の序列だけを考慮して、その中の1段の昇順の序列に対して、最も理想的な情況は1,2,3...このようにキャンディを配布します;降順のシーケンスについては,後から先へ遍歴すれば昇順になる.前序と後序を遍歴すると、昇順と降順の受け渡し先の点に2つの値があり、両側の子供が手に入れたキャンディよりも多いので、その値を大きくします.このとき得られる配列は,テーマの要件を満たす前提で,子ども一人当たりの最低のキャンディ数を返し,その和を返すことでよい.
ACソース
私のGithub(https://github.com/gavinfish/LeetCode-Python)を使用して、関連するソースコードを取得します.
原題
直線的にN人の子供が立っていて、すべての子供は自分の数字を持っていて、今以下の規則に従って子供にキャンディを配布します:すべての子供は少なくとも1つのキャンディがあります;隣の子の中で数字が大きい方が持っているキャンディも多いです.最低何個のキャンディを出すことを求めます.
注意点:
例:
入力:ratings=[1,2,3,2]
出力:7
問題を解く構想.
行った後に遍歴する時、私達は昇順の序列だけを考慮して、その中の1段の昇順の序列に対して、最も理想的な情況は1,2,3...このようにキャンディを配布します;降順のシーケンスについては,後から先へ遍歴すれば昇順になる.前序と後序を遍歴すると、昇順と降順の受け渡し先の点に2つの値があり、両側の子供が手に入れたキャンディよりも多いので、その値を大きくします.このとき得られる配列は,テーマの要件を満たす前提で,子ども一人当たりの最低のキャンディ数を返し,その和を返すことでよい.
ACソース
class Solution(object):
def candy(self, ratings):
""" :type ratings: List[int] :rtype: int """
n = len(ratings)
candy = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candy[i] = candy[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candy[i] = max(candy[i], candy[i + 1] + 1)
return sum(candy)
if __name__ == "__main__":
assert Solution().candy([1, 2, 3, 7, 4, 3, 2, 1]) == 21
私のGithub(https://github.com/gavinfish/LeetCode-Python)を使用して、関連するソースコードを取得します.