Patching Array
给一个已排序数组和一个n, 问这个数组添加几个元素能让其中的任何个数数字之和等于n. 这个题需要找规律. 规律是数组从小往大求和. 这个和就是能覆盖的数组, 当遇到一个数字无法覆盖的时候, patch应该是当前可覆盖范围最大值+1, 因为这样才能保证每个数都覆盖, 然后继续求和, 直到n.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class Solution { public int minPatches(int[] nums, int n) { int count = 0; int i = 0; long sum = 0; while(sum < n) { if(i < nums.length && nums[i] <= sum+1) sum+=nums[i++]; else{ sum+=sum+1; count++; } } return count; } } |