阅读 34

LeetCode之Patching Array(Kotlin)

问题:


方法: 假设 miss 是缺少的数字中最小的,则区间 [1, miss) (左闭右开) 已经被完全覆盖。为了覆盖 miss,我们需要添加某些小于等于 miss 的数字。否则将不可能覆盖到。 假设我们添加的数字是 xx,则区间 [1, miss) 和 [x, x + miss) 均被覆盖到。由于我们知道 x <= miss,这两个区间必然覆盖了区间 [1, x + miss)。我们希望能够尽可能选择大的 xx,这样覆盖的范围就可以尽可能大。因此,最好的选择是 x = miss。 在覆盖到 miss 后,我们可以重新计算覆盖范围,查看新的最小的缺少数字。然后加上该数字。重复操作直到全部数字都被堵盖到。 具体实现:

class PatchingArray {
    fun minPatches(nums: IntArray, n: Int): Int {
        var count = 0
        var miss = 1L
        var i = 0
        while (miss <= n) {
            if (i <= nums.lastIndex && nums[i] <= miss) {
                miss += nums[i++]
            } else {
                count++
                miss += miss
            }
        }
        return count
    }
}

fun main(args: Array<String>) {
    val nums = intArrayOf(1, 2, 31, 33)
    val n = 2147483647
    val patchingArray = PatchingArray()
    println(patchingArray.minPatches(nums, n))
}
复制代码

有问题随时沟通

具体代码实现可以参考Github