【leetcode】 330.patching-array

发表于 | 分类于 ，

判断能否构成连续序列


描述

给定一个数组 a 以及一个整数 n ，需要令 a 中数加成 1 到 n 的序列。
例如 输入 a = [1,2,3], n = 6
[1, 2, 3] 可以构成 [1,2,3,4(1+3),5(2+3),6(3+3)]，这时不需要添加元素
而a = [1,2], n = 6 则不能成立，需要补一个数 3 。本题需要求出要加上多少个数能完成要求。

样例

样例1

1
2
输入: a = [1,3], n = 6
输出: 1

样例2

1
2
输入: a = [1,5,10], n = 20
输出: 2

样例3

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

思路

一开始理解错了题意，以为将一个集合不断膨胀，然后判断能否构成一个新的序列，不行的话再加上一个数补充，这个过程中新产生的结果是可以再利用的，但是认真想一想， 发现集合中只要有 1 就能构成所有的序列，又何必要求呢？ 这个题目显然新产生的结果是不能再次利用的，emmm，参考的其他的代码，需要学习一下写注释的风格。

注意整型可能溢出，题目会有数据 a = [1], n = 2^31 - 1

代码

求解原文地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
   //   1) [1,2] can cover [1,2,3]
   //    2) [1,2,3] can cover [1,2,3,4,5,6]
   //    So the max reach is the sum of  number
   //
   //   3) [1,2] can cover [1,2,3],but can not cover 4
   //   then we patch 4 to it [1,2,4] can cover 1,2,3(1+2),4,5(1+4),6(1+2),7(1+3)
   //   So we can see [1,2,4] can reach 7  (sum of all number);
   //
   //  So, we can figure out our solution
   //
   //      0) considering the 'n' we need to cover
   //      1) maintain a variable we are trying to patch, supose named 'try_patch'
   //      3) if 'try_patch' >=  'nums[i] ,we just add keep the current array
   //         and set 'try_patch' to the next candidate number 'sum+1'
   //      4) if 'try_path' < 'nums', which means we need to patch.
   //
   //
   //
   int minPatches(vector<int>& nums, int n) {
      long long  patchCnt = 0;
      int i = 0;
      long long coverd = 0;
      while (i < nums.size()) {
         int try_patch = 1 +coverd;
         if (try_patch >= nums[i]) {
            coverd += nums[i];
            i++;
         }
         else {
            coverd += try_patch;
            patchCnt++;
         }
         if (coverd >= n) {
            break;
         }
      }
      // if the number is single, that means it is the last number  [ {1} 7 ]
      // so there is no next number n[i+1] to reach 
      // we can just use 'n' to cover
      // note: cover may be overflow!
      while (coverd < n) {
         int try_patch = coverd + 1;
         patchCnt ++ ;
         coverd += try_patch;
         cout << coverd << "\t";
      }

      return patchCnt;
   }

};

另一份代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
public:
   int minPatches(vector<int>& nums, int n) {
      int ans = 0;
      sort(nums.begin(),nums.end());
      long long  int sum = 1;
      int i = 0;
      while (sum <= n)
      {
         if (i<nums.size() && sum >= nums[i])sum += (long long int)nums[i++];
         else { ans++; sum += sum; }
      }
      return ans;
   }
};

参考

原题链接