leetcode 330. Patching Array | 1798. Maximum Number of Consecutive Values You Can Make-蒲公英云

leetcode 330. Patching Array | 1798. Maximum Number of Consecutive Values You Can Make

向右看齐 2022-09-09 06:48 216阅读 0赞

1798. Maximum Number of Consecutive Values You Can Make | 1798. 你能构造出连续值的最大数目

https://leetcode.com/problems/maximum-number-of-consecutive-values-you-can-make/
在这里插入图片描述

题解

这题没有套路。。

随手就是一个 O(2^n) 暴力，妥妥的超时了。看了 hint 没看懂，后来看了答案：

参考：https://leetcode-cn.com/problems/maximum-number-of-consecutive-values-you-can-make/solution/ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf/
在这里插入图片描述

class Solution { 
    public int getMaximumConsecutive(int[] coins) { 
        Arrays.sort(coins);
        int end = 0;
        for (int coin : coins) { 
            if (coin <= end + 1) end += coin;
            else break;
        }
        return end + 1;
    }
}

在这里插入图片描述

leetcode 330. Patching Array | 330. 按要求补齐数组

https://leetcode.com/problems/patching-array/
在这里插入图片描述

题解

做过上一道 330. Patching Array 之后，这个题的思路就简单了。

当连续区间 0~end 和下一个 num 不连续的时候，用 end+1 来填充，然后更新 end，直到 end 能和下一个 num 毗邻为止。

class Solution { 
    public int minPatches(int[] nums, int n) { 
        int count = 0;
        long end = 0;
        for (long num : nums) { 
            while (num > end + 1) { 
                count += 1;
                end += (end + 1);
                if (end >= n) return count; // 满足条件，随时跑路！
            }
            end += num;
            if (end >= n) return count;  // 满足条件，随时跑路！
        }
        // 收尾
        while (n > end + 1) { 
            count += 1;
            end += (end + 1);
        }
        return count;
    }
}