首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
Coding
V2EX  ›  分享创造

无聊想到个算法题

  •  
  •   qiuhanyuan · 51 天前 · 1671 次点击
    这是一个创建于 51 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前提: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
        1
    lihongming   51 天前 via iPhone
    不玩 dota,这道题是不是可以理解为 2 和 4 有多少种可能组成 68 ?
        2
    geelaw   51 天前 via iPhone
    这个数列很简单,你要算的是 Fibonacci[33]
        3
    Xs0ul   51 天前
    从你字面意思来说不太对, possibleKillNumbers 看起来是不包含顺序的

    从你的代码来说,你要求的实际就是第 N / 2 个斐波那契数
        4
    paouke   51 天前 via iPhone
    可以理解为 68 级台阶,青蛙每次上 2 级或者 4 级,有多少种上法吗,哈哈
        5
    a7217107   51 天前
    递归,这就是斐波那契数列
        6
    braveheart7854   51 天前
    2x+4y=68,然后 for x=0; x<=68/2; x++,求 y
        7
    Dogergo   50 天前
    @paouke 昨天面试问这个问题,n 阶台阶,单次 2 或 4 阶,有多少种上法,现在还在懵比
        8
    barnetime   50 天前
    ```

    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)
    }



    ```
        9
    barnetime   50 天前
    ```
    //从上面的递归 到加上缓存(也叫记忆化) 递推

    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)
    }
    }



    ```
        10
    promontory123   50 天前
    2n 阶台阶,单次 2 或 4 阶,最多跳跃多少次 减去 最少跳跃多少 次加一
        11
    dezhou   48 天前 via Android
    ( x+x^2 )^34 的 x^68 的系数
        12
    RicardoY   39 天前 via Android
    这个稍微简单点了..我记得有用拍拍熊打野和小鱼刮痧作为背景的题目..就比较难了
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4330 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 23ms · UTC 03:27 · PVG 11:27 · LAX 19:27 · JFK 22:27
    ♥ Do have faith in what you're doing.