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