美文网首页
001-135-Candy by Python

001-135-Candy by Python

作者: 浪尖的游鱼 | 来源:发表于2019-05-07 11:58 被阅读0次

    本文例题来自135-Candy

    先看题

    135-Candy

    理解

    首先需求的条件有两个,第一个非常好理解,总糖果量至少是N,即孩子的数量。第二个条件就有点难了,我们先假设第n个孩子分得的糖果数量是f(n) 1<=n<=N,分数是r(n) 1<=n<=N,那么化为数学问题,即

    if r(n) > r(n-1) then
        need f(n)>f(n-1) 
    if r(n) > r(n+1) then
        need f(n)>f(n+1) 
    

    再加上条件求得需要准备最少的糖果数量,简单讲need f(n)>f(n-1)换成f(n)=f(n-1)+1即可,所以最简单的解法也就顺势出来了。

    个人的解法

    #!/usr/bin/python3
    class Solution:
        def candy(self, ratings: List[int]) -> int:
            sum = len(ratings)#条件一
            rat_lan = sum
            tmp =[0]*rat_lan#初始化
    #if r(n) > r(n-1) then
    #    need f(n)>f(n-1) 
            for i in range(1,rat_lan):
                if ratings[i] > ratings[i-1] and tmp[i] <= tmp[i-1]:
                    tmp[i] = tmp[i-1]+1
    #if r(n) > r(n+1) then
    #    need f(n)>f(n+1) 
            for i in range(rat_lan-2,-1,-1):
                if ratings[i] > ratings[i+1] and tmp[i] <= tmp[i+1]:
                    tmp[i] = tmp[i+1]+1
            for a in tmp:
                sum+=a
            return sum
    

    学习评论

    大多数解法就是用的本文的解法,毕竟好理解。

    但是发现一只独秀

    qmx521125
    动态规划,一次遍历
    C++

    好吧大佬,来理解一下,话说这题能提炼出动态规划也是强。
    long time age
    好吧,噱头,不能叫做动态规划
    不过倒是一次遍历的方法,归纳如下:
    1.正序遍历当遇到等值时:f(n)=1即可
    2.正序遍历当遇到顺序递增时:f(n) = f(n-1)+1
    3.正序遍历当遇到顺序递减时:问题来了,如果递减的数量大于之前一个递增的数量,无法预估上一个递增的最大值?解决方案:

    • 发现开始递减时,记录上一个 递增的长度
    • 记录递减的长度
    • sum值的计算改为增加 递减的长度
    • 当 递减的长度 >= 上一个 递增的长度 时 递减的长度 的额外加一,其实就是把递增和递减公用的数,算到递减的长度里面去了
      具体如下,为嘛说不是动态规划呢,因为子问题(1个人到N个人)是有,但是不是建立在子问题之上求大问题(sum(n)与sum(n-1)没有绝对的逻辑关系)的解。


      一次循环
    一次遍历的另一种方法

    非常简单用两个tmp数组,一个正序,一个逆序,只是相当于把最初的方法整合了。

    相关文章

      网友评论

          本文标题:001-135-Candy by Python

          本文链接:https://www.haomeiwen.com/subject/crnsoqtx.html