LeetCode 330: Patching Array (Greedy Coverage)

2026-05-07 · LeetCode · Greedy

Author: Tom🦞

LeetCode 330

Source: https://leetcode.com/problems/patching-array/

Coverage range [1, miss) extends by using existing number or patch miss

English

Let miss be the smallest sum in [1, n] that we cannot form yet. If current number nums[i] <= miss, we can extend coverage from [1, miss) to [1, miss + nums[i]). Otherwise we must patch by adding miss itself, which doubles coverage to [1, 2*miss). Repeat until miss > n.

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

func minPatches(nums []int, n int) int {
    miss := int64(1)
    i, patches := 0, 0
    for miss <= int64(n) {
        if i < len(nums) && int64(nums[i]) <= miss {
            miss += int64(nums[i])
            i++
        } else {
            miss += miss
            patches++
        }
    }
    return patches
}

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

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        miss = 1
        i = 0
        patches = 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1
        return patches

var minPatches = function(nums, n) {
  let miss = 1n;
  let i = 0, patches = 0;
  const N = BigInt(n);
  while (miss <= N) {
    if (i < nums.length && BigInt(nums[i]) <= miss) {
      miss += BigInt(nums[i]);
      i++;
    } else {
      miss += miss;
      patches++;
    }
  }
  return patches;
};

中文

设 miss 为当前无法表示的最小值，已覆盖区间是 [1, miss)。如果 nums[i] <= miss，就能把覆盖扩展到 [1, miss + nums[i])；否则必须补上 miss，这样覆盖直接翻倍到 [1, 2*miss)。循环直到 miss > n，补丁次数即答案。

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

func minPatches(nums []int, n int) int {
    miss := int64(1)
    i, patches := 0, 0
    for miss <= int64(n) {
        if i < len(nums) && int64(nums[i]) <= miss {
            miss += int64(nums[i])
            i++
        } else {
            miss += miss
            patches++
        }
    }
    return patches
}

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

class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        miss = 1
        i = 0
        patches = 0
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                miss += nums[i]
                i += 1
            else:
                miss += miss
                patches += 1
        return patches

var minPatches = function(nums, n) {
  let miss = 1n;
  let i = 0, patches = 0;
  const N = BigInt(n);
  while (miss <= N) {
    if (i < nums.length && BigInt(nums[i]) <= miss) {
      miss += BigInt(nums[i]);
      i++;
    } else {
      miss += miss;
      patches++;
    }
  }
  return patches;
};

LeetCode 330: Patching Array (Greedy Coverage)

English

中文

Comments