由于大学时候专业并不是计算机专业的,虽然有时也会一时兴起刷一些算法题目,但更多的时候是三天打鱼两天晒网,甚至很长一段时间都不会有什么动作,因为大多数的算法平台做解答算法题目的时候都需要手动获得输入内容,这一部分的内容感觉并没有太大的操作难度,很多时候却让人非常的难受。

直到后来我发现了Leetcode这个平台,他的参数会直接通过方法给出,不需要解题者一个个的获取,或许有人会抨击我这种想法,但是我从来都不会觉得如何,我做我自己的事情,不需要他人指责。

现在的我已经正式的开始踏上了工作的旅途,深知算法对于面试的重要性,或许工作的时候不会经常的用到,但是算法的重要性无需多言,日后对于程序的性能优化等都需要基于过硬的算法功底。

所以我决定开始一个特别的系列《LeetCode每日一题系列》,也正是因为LeetCode推出了每日一题的服务,我才会想到要做这个系列,也会跟随LeetCode的每日一题解答。话不多说,这就开始吧。

887.鸡蛋掉落

你将获得K个鸡蛋,并可以使用一栋从1N层共有N层的楼的建筑。
每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。
你知道存在楼层F,满足0<=F<=N任何从高于F的楼层落下的鸡蛋都会碎,从F楼层或比它低的楼层落下的鸡蛋都不会破。
每次一栋,你可以取一个鸡蛋(如果你有完整的鸡蛋)并把它从任一楼层X扔下(满足1<=X<=N)。
你的目标是确切地知道F的值是多少。
无论F的初始值如何,你确定F的值的最小移动次数是多少?

很多人可能像我一样第一感觉就是二分查找,但是仔细一想,二分查找只求次数的话直接可以通过公式log2N得出结论,但是如果这样的话,题目中给出的鸡蛋的个数K就毫无用武之地,不像是算法题中会出现的情况。在不限制鸡蛋个数的情况下可以通过二分法的公式计算得出结果,但是当鸡蛋的个数有限制的时候,为了避免不必要的浪费,自然不能随意的通过二分法来断定此次扔鸡蛋的楼层,因为当鸡蛋碎掉之后还有剩余很多的楼层时将无法判断出结果。

其实最终结果就是这道题涉及到了动态规划的问题,将一个大的问题拆分成多个小的子问题,算出子问题的最优解之后再向原问题合并。

示例代码如下:

import kotlin.math.max
import kotlin.math.min

class EggDrop {
    //定义一个HashMap存储已经解决过的子问题,避免重复计算,耗费时间
    lateinit var cache: HashMap<Pair<Int, Int>, Int>
    fun superEggDrop(K: Int, N: Int) {
        cache = HashMap()
        println(dp(K, N))
    }

    fun dp(K: Int, N: Int): Int {
        //当楼层数为0时不需要尝试,为1时可以确定只用一次就可以确定,当鸡蛋数量为1时只能使用从第一层开始到第N层的方式尝试,所以均可返回N
        //此处则为递归算法的返回条件
        if (N == 0 || N == 1 || K == 1) {
            return N
        }
        //除以上情况之外,都需要进行计算,先假设最少需要N次(楼层数为N,所以最多只要N次)
        var minimum: Int = N;
        for (i in 1..N) {
            //分别计算在第i层鸡蛋碎掉了和鸡蛋没碎掉情况需要尝试的次数,求出最大值,
            //如果该值比前几次循环所得的最小值都小的话,就将最小值设为此值
            val pair1 = Pair(K - i, i - 1)
            val pair2 = Pair(K, N - 1)
            if (!cache.containsKey(pair1)) {
                cache[pair1] = dp(K - i, i - 1)
            }
            if (!cache.containsKey(pair2)) {
                cache[pair2] = dp(K, N - 1)
            }
            val temp = max(cache[pair1]!!, cache[pair2]!!)
            minimum = min(minimum, temp + 1)
        }
        //经过遍历和递归,最终得出一个最优的解,返回
        return minimum
    }
}

基本代码和思路都已经写在上面了,但是这并不是性能最好的方法,只是最简单、最容易理解的一种方法。鄙人的水平暂时还不能接触到更高的阶段,所以这个问题暂时就先用这种方式解决,之后有机会再优化算法。

今天的分享就到此结束了,感谢大家的查看。