按要求补齐数组(每日一题)

leetcode 笔记

题目描述

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

示例 1:

输入: nums = [1,3], n = 6
输出: 1 
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。
示例 2:

输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。
示例 3:

输入: nums = [1,2,2], n = 5
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/patching-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

code

给定 1 ~ i 连续数字，组合可表达的范围为 1 ~ (2 * i + 1), 最大范围无非是所有数相加。

初始表达范围[0, v = 1)。对于nums中item, 如果item 已经在表达范围内(item < v)，则 v += item 作为新的范围。

如果没有在范围内，则需要补数字，每次补一个边界外下一个数字，也就是v, 可表达的范围变为[0, v += v) 直到能表示item

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long v = 1;
        int ans = 0, i = 0, size = nums.size();
        while (v <= n) 
            if (i < size && nums[i] <= v)
                v += nums[i++];
            else
                ans++, v <<= 1;
        return ans;
    }
};

class Solution {
 public:
  int minPatches(vector<int> &nums, int n) {
    long long v = 1;
    int ans = 0;
    for (int i = 0, size = nums.size(); v <= n; ++i) {
      long long next = i < size ? nums[i] : (n + 1L);
      while (v < next && v <= n) ans++, v <<= 1;
      v += next;
    }
    return ans;
  }
};

kotlin

一刀流，尾递归

tailrec fun minPatches(ans:Int, v:Long, i:Int): Int = when {v > n -> ans; i < nums.size && nums[i] <= v -> minPatches(ans, v + nums[i], i + 1) else -> minPatches(ans + 1, v shl 1, i) }

class Solution {
    fun minPatches(nums: IntArray, n: Int): Int {
        tailrec fun minPatches(ans:Int, v:Long, i:Int): Int = when {
            v > n -> ans
            i < nums.size && nums[i] <= v -> minPatches(ans, v + nums[i], i + 1)
            else -> minPatches(ans + 1, v shl 1, i)
        }
        return minPatches(0, 1L, 0)
    }
}

scala

@tailrec
def minPatches(ans:Int, v:Long, i:Int):Int = if(v > n) ans else if(i < nums.length && nums(i) <= v) minPatches(ans, v + nums(i), i + 1) else minPatches(ans + 1, v << 1, i)

import scala.annotation.tailrec

object Solution {
  def minPatches(nums: Array[Int], n: Int): Int = {
    @tailrec
    def minPatches(ans: Int, v: Long, i: Int): Int = if (v > n) ans
    else if (i < nums.length && nums(i) <= v) minPatches(ans, v + nums(i), i + 1)
    else minPatches(ans + 1, v << 1, i)
    
    minPatches(0, 1, 0)
  }
}

Rust

拿不到外层的nums, n。只能传进去。或者用Y组合子 + 闭包

impl Solution {
    pub fn min_patches(nums: Vec<i32>, n: i32) -> i32 {
        fn min_patches(nums: Vec<i32>, n: i32, ans: i32, v: i64, i: usize) -> i32 {
            if v > (n as i64) {
                ans
            } else if i < nums.len() && nums[i] as i64 <= v {
                min_patches(nums, n, ans, v + (nums[i] as i64), i + 1)
            } else {
                min_patches(nums, n, ans + 1, v << 1, i)
            }
        }
        min_patches(nums, n, 0, 1, 0)
    }
}

Y组合子实现递归

kotlin

fun minPatches(nums: IntArray, n: Int): Int = Y<Data, Int> { f, (ans, v, i) -> when { v > n -> ans; i < nums.size && nums[i] <= v -> f(Data(ans, v + nums[i], i + 1))else -> f(Data(ans + 1, v shl 1, i)) } }(Data(0, 1, 0))

class Solution {
    data class Data(val ans: Int, val v: Long, val i: Int)

    fun <T, R> Y(g: ((T) -> R, T) -> R): (T) -> R = { g(Y(g), it) }

    fun minPatches(nums: IntArray, n: Int): Int =
        Y<Data, Int> { f, (ans, v, i) ->
            when {
                v > n -> ans
                i < nums.size && nums[i] <= v -> f(Data(ans, v + nums[i], i + 1))
                else -> f(Data(ans + 1, v shl 1, i))
            }
        }(Data(0, 1, 0))
}

scala

object Solution {

  def Y[T, R](g: (T => R, T) => R): T => R = t => g(Y(g), t)

  def minPatches(nums: Array[Int], n: Int): Int = {
    Y[(Int, Long, Int), Int]{ (f, t) =>
      if (t._2 > n) t._1
    else if (t._3 < nums.length && nums(t._3) <= t._2)
      f((t._1, t._2 + nums(t._3), t._3 + 1))
    else f(t._1 + 1, t._2 << 1, t._3)
    }((0, 1, 0))
  }
}

Rust

fn Y<'a, T, R>(g: &'a impl Fn(&dyn Fn(T) -> R, T) -> R) -> impl Fn(T) -> R + 'a {
    move |t| g(&Y(g), t)
}

impl Solution {
    pub fn min_patches(nums: Vec<i32>, n: i32) -> i32 {
        (Y(&|f: &dyn Fn((i32, i64, usize)) -> i32, (ans, v, i)|
            if v > (n as i64) {
                ans
            } else if i < nums.len() && nums[i] as i64 <= v {
                f((ans, v + (nums[i] as i64), i + 1))
            } else {
                f((ans + 1, v << 1, i))
            }
        ))((0, 1, 0))
    }
}

I'm Prime

十方三世，尽在一念