[LeetCode] Patching Array

简介: Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:
nums = [1, 3], n = 6
Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

解题思路

假设数组当前可以表示的范围为[1, total)内的所有数字,那么向数组中添加元素add可以将表示范围扩充至[1, total + add),其中add≤total。当且仅当add=total时取到范围上限[1, 2 * total)

  • 当数组中有小于等于add的元素时,则利用数组中的元素。
  • 若没有,则添加新元素add

实现代码

//Runtime: 1 ms
public class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int add = 0;
        int i = 0;
        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss){
                miss += nums[i++];
            } else {
                miss += miss;
                add += 1;
            }
        }

        return add;
    }
}
目录
相关文章
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
49 0
|
算法 Python
LeetCode 410. Split Array Largest Sum
给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
144 0
LeetCode 410. Split Array Largest Sum
|
算法
LeetCode 330. Patching Array
给定一个已排序的正整数数组 nums,和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中,使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
79 0
LeetCode 330. Patching Array
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
算法 测试技术
LeetCode 88. 合并两个有序数组 Merge Sorted Array
LeetCode 88. 合并两个有序数组 Merge Sorted Array
|
人工智能 索引
LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum
LeetCode 1013. 将数组分成和相等的三个部分 Partition Array Into Three Parts With Equal Sum
LeetCode 189. 旋转数组 Rotate Array
LeetCode 189. 旋转数组 Rotate Array
|
2月前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
2月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
84 2