给定一个长度为 n 的数组 nums 和一个整数 m。请判断能否执行一系列操作,将数组拆分成 n 个非空数组。

在每一步操作中,你可以选择一个长度至少为 2 的现有数组(之前步骤的结果)并将其拆分成 2 个子数组,而得到的每个子数组,至少需要满足以下条件之一:

  1. 子数组的长度为 1
  2. 子数组元素之和大于或等于 m

如果你可以将给定数组拆分成 n 个满足要求的数组,返回 true;否则,返回 false

注意: 子数组是数组中的一个连续非空元素序列。

示例

示例 1:

输入:nums = [2, 2, 1], m = 4

输出:true

解释:第 1 步,将数组 nums 拆分成 [2, 2] 和 [1]。第 2 步,将数组 [2, 2] 拆分成 [2] 和 [2]。因此,答案为 true

示例 2:

输入:nums = [2, 1, 3], m = 5

输出:false

解释:存在两种不同的拆分方法:第 1 种,将数组 nums 拆分成 [2, 1] 和 [3]。第 2 种,将数组 nums 拆分成 [2] 和 [1, 3]。然而,这两种方法都不满足题意。因此,答案为 false

示例 3:

输入:nums = [2, 3, 3, 2, 3], m = 6

输出:true

解释:第 1 步,将数组 nums 拆分成 [2, 3, 3, 2] 和 [3]。第 2 步,将数组 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2]。第 3 步,将数组 [2, 3, 3] 拆分成 [2] 和 [3, 3]。第 4 步,将数组 [3, 3] 拆分成 [3] 和 [3]。因此,答案为 true

提示

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= 100
  • 1 <= m <= 200

代码实现

class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        if (nums.size() == 2) return 1;
        int n = nums.size();
        while(n--) {
            for (int i = 0; i < nums.size() - 1; ++i) {
                if (nums[i] + nums[i + 1] >= m) {
                    nums[i] += nums[i + 1];
                    nums.erase(nums.begin() + i + 1);
                }
            }    
        }
        return nums.size() == 1;
    }
}; 
分类: Thought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status