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

无聊想到个算法题

  •  
  •   qiuhanyuan · 2019-10-22 01:33:03 +08:00 · 3194 次点击
    这是一个创建于 1866 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前提:Dota2 游戏中,英雄沉默术士在击杀一名敌方英雄后可以获得智力

    假设沉默术士每次击杀可以随机获得 2 点或 4 点额外智力,当他的额外智力为 68 时,可能的击杀敌方英雄的情况有多少种?

    下面是我用动态规划实现的一种解法(不知道对不对)

    public class Silencer {
    
        private int intNum;
        private int[] array;
    
        private Silencer(int intNum) {
            this.intNum = intNum;
        }
    
        private int possibleKillNumbers() {
            this.array = new int[this.intNum+1];
            this.array[0] = 1;
            this.array[2] = 1;
    
            if (this.intNum <= 2) {
                return this.array[this.intNum];
            }
    
            for (int i = 4; i <= this.intNum; i+=2) {
                this.array[i] = this.array[i-2] + this.array[i-4];
            }
    
            return this.array[this.intNum];
        }
    
        public static void main(String[] args) {
            Silencer sil = new Silencer(68);
            System.out.println(sil.possibleKillNumbers()); 	// output: 9227465
        }
    }
    
    12 条回复    2019-11-02 21:34:30 +08:00
    lihongming
        1
    lihongming  
       2019-10-22 01:41:39 +08:00 via iPhone
    不玩 dota,这道题是不是可以理解为 2 和 4 有多少种可能组成 68 ?
    geelaw
        2
    geelaw  
       2019-10-22 01:48:18 +08:00 via iPhone
    这个数列很简单,你要算的是 Fibonacci[33]
    Xs0ul
        3
    Xs0ul  
       2019-10-22 02:00:18 +08:00
    从你字面意思来说不太对, possibleKillNumbers 看起来是不包含顺序的

    从你的代码来说,你要求的实际就是第 N / 2 个斐波那契数
    paouke
        4
    paouke  
       2019-10-22 09:11:31 +08:00 via iPhone
    可以理解为 68 级台阶,青蛙每次上 2 级或者 4 级,有多少种上法吗,哈哈
    a7217107
        5
    a7217107  
       2019-10-22 09:25:59 +08:00
    递归,这就是斐波那契数列
    braveheart7854
        6
    braveheart7854  
       2019-10-22 10:03:37 +08:00
    2x+4y=68,然后 for x=0; x<=68/2; x++,求 y
    Dogergo
        7
    Dogergo  
       2019-10-22 13:48:39 +08:00
    @paouke 昨天面试问这个问题,n 阶台阶,单次 2 或 4 阶,有多少种上法,现在还在懵比
    barnetime
        8
    barnetime  
       2019-10-22 20:28:14 +08:00
    ```

    def possibleKillNum(target: Int) : Int = {
    val k1 = 2
    val k2 = 4
    if (target == 2) return 1
    if (target == 4) return 2
    possibleKillNum(target - k1) + possibleKillNum(target - k2)
    }



    ```
    barnetime
        9
    barnetime  
       2019-10-22 21:01:55 +08:00
    ```
    //从上面的递归 到加上缓存(也叫记忆化) 递推

    def possibleKillNum1(target: Int, cash : mutable.Map[Int, Int]) : Int = {
    //需要传一个空 Map 做缓存
    if (cash.isEmpty) {
    cash += 2 -> 1
    cash += 4 -> 2
    }
    val k1 = 2
    val k2 = 4
    if (cash.getOrElse(target, null) == null) {
    val r = possibleKillNum1(target - k1, cash) + possibleKillNum1(target - k2, cash)
    cash += target -> r
    r
    } else {
    cash(target)
    }
    }



    ```
    promontory123
        10
    promontory123  
       2019-10-23 11:06:52 +08:00
    2n 阶台阶,单次 2 或 4 阶,最多跳跃多少次 减去 最少跳跃多少 次加一
    dezhou
        11
    dezhou  
       2019-10-25 08:51:12 +08:00 via Android
    ( x+x^2 )^34 的 x^68 的系数
    RicardoY
        12
    RicardoY  
       2019-11-02 21:34:30 +08:00 via Android
    这个稍微简单点了..我记得有用拍拍熊打野和小鱼刮痧作为背景的题目..就比较难了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2233 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 00:50 · PVG 08:50 · LAX 16:50 · JFK 19:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.