V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ljy2010a
V2EX  ›  算法

2018027 今日算法

  •  1
     
  •   ljy2010a · 2018-03-27 12:56:53 +08:00 · 2461 次点击
    这是一个创建于 2194 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个青蛙跳台阶
    每个台阶上有个随机数, 比如:

    staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64]
    

    给定 n 个台阶和可能跳的步数,比如:

    possible_steps = [3,4,5]
    

    对跳到的台阶的数求和,比如:

    step_sequence = [3,4] ,  sum = 44+55 = 99
    step_sequence = [4,4,4] , sum = 5+45+(超出台阶算 0) = 50
    

    问和最大的时候是多少? 比如:

    best_step_sequence = [3,4,4] , best_sum = 44+55+64 = 163
    

    Example:

    Input:

    staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64]
    possible_steps = [3,4,5]
    

    Output

    163
    
    9 条回复    2018-03-27 14:37:02 +08:00
    lhx2008
        1
    lhx2008  
       2018-03-27 13:00:40 +08:00 via Android
    动态规划问题,只会递归,不太会优化
    vegito2002
        2
    vegito2002  
       2018-03-27 13:36:04 +08:00
    vegito2002
        3
    vegito2002  
       2018-03-27 13:38:12 +08:00
    今天的题还可以, 虽然还是经典的 DP, 不过不是直接 LeetCode 上面抄来的题目了

    V2 插入图片真的是死结了.

    <img src="http://i67.tinypic.com/2cr60ci.png" width="800">
    vegito2002
        4
    vegito2002  
       2018-03-27 13:51:39 +08:00
    vegito2002
        5
    vegito2002  
       2018-03-27 14:21:42 +08:00   ❤️ 1
    每一个 iteration 里面的第二个循环, 需要遍历一个 min_step 的长度, 这个过程可以用一个 min_queue 的 window 来维护, 这样这个遍历就没有必要, amortized O(1) time:

    vegito2002
        6
    vegito2002  
       2018-03-27 14:29:44 +08:00
    window 应该返回 max, 上面实现写错了:

    int windowMax () {
    return mins.peekLast ();
    }

    对应的调用换一下就行了
    vegito2002
        7
    vegito2002  
       2018-03-27 14:33:14 +08:00
    算了, 上面的 minqueue 版本还是有问题, 应该是维护 maxqueue. 不贴图片污染环境了, 直接这个 gist


    https://gist.github.com/vegito2002/679f0af72ca15b2e9ce1866a6bf4e1a4
    muziki
        8
    muziki  
       2018-03-27 14:35:36 +08:00 via iPhone
    @vegito2002 图片插入貌似只支持 imugr 和 Weibo
    vegito2002
        9
    vegito2002  
       2018-03-27 14:37:02 +08:00
    @muziki 恩, 刚学会. 第一次贴图片, 以前失败了也都是懒得管
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2893 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 11:14 · PVG 19:14 · LAX 04:14 · JFK 07:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.