Leetcode330 Patching Array

Posted on Edited on In

题目描述

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:

1
2
3
4
5
6
7
Input: nums = [1,3], n = 6
Output: 1 
Explanation:
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:

1
2
3
Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

1
2
Input: nums = [1,2,2], n = 5
Output: 0

题目解析

这道题目意思很简单，一个排序好了的数列，选择其中任意的几个相加，要求结果覆盖1 - n，如果不能覆盖，则可以添加patch，求最小patch数。

首先说明下，这道题我并没有做出来，这是我见过的最优雅的贪心算法之一，可以用非常简洁的代码完成任务。

首先，假设有一个数miss了，那说明[1, miss - 1]已经被覆盖了，而为了覆盖miss，找一个数x，这个x必然小于等于miss，因为大于的话miss依旧不会被覆盖，举几个数就能理解了，这个x就是题目中的patch，也就是补丁，添加了x后覆盖范围就变成了[1, miss + x - 1]了，我们为了让patch数最小，就得每次在范围拓展的时候将上限，也就是(miss + x - 1)尽可能的大，之前在对于x的讨论中，可以发现要x的可能取值范围在[1, miss]之间，取最大值即可，也就是说每次添加的patch正好为miss值，有了这样一个概念，题目也就迎刃而解了。

算法描述:

  • Initialize the range [1, miss) = [1, 1) = empty
    While n is not covered yet
  • if the current element nums[i] is less than or equal to miss
    • extends the range to [1, miss + nums[i])
    • increase i by 1
  • otherwise
    • patch the array with miss, extends the range to [1, miss + miss)
    • increase the number of patches
  • Return the number of patches
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int minPatches(int[] nums, int n) {
    // 这边用long 防止溢出
    long miss = 1;
    int patches = 0;
    int i = 0;
    while(miss <= n){
        if(i < nums.length && nums[i] <= miss){
            miss += nums[i++];
        }
        else{
            miss *= 2;
            ++patches;
        }
    }
    return patches;
}

总结

这是我见过的最优雅的利用Greedy思想解决的问题，一开始我还想了很多，甚至考虑到哥德巴赫猜想什么的（感叹下自己的脑洞），但解决起来，其实只是一个基本的观察和推演思考，说实话这个miss与之前的关系我还真没有想到，抽象思维能力感觉与高中相比退化了不少，希望能通过这些题目予以训练和改善吧。

总而言之，这是一道非常好的题目，如果有人能在面试的时候答出来，建议直接录用。