判断是否能拆分数组

6953. 判断是否能拆分数组

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

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

子数组的长度为 1 ，或者
子数组元素之和 大于或等于 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) { } };

javascript 解法, 执行用时: 72 ms, 内存消耗: 41.4 MB, 提交时间: 2023-08-07 15:34:07

/**
 * @param {number[]} nums
 * @param {number} m
 * @return {boolean}
 */
var canSplitArray = function(nums, m) {
	const n = nums.length;
	if ( n <= 2 ) {
		return true;
	}
	for ( let i = 1; i < n; i++ ) {
		if ( nums[i-1]+nums[i] >= m ) {
			return true;
		}
	}
	return false;
};

php 解法, 执行用时: 16 ms, 内存消耗: 18.9 MB, 提交时间: 2023-08-07 15:32:26

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $m
     * @return Boolean
     */
    function canSplitArray($nums, $m) {
    	$n = count($nums);
    	if ( $n <= 2 ) return true;

    	for ( $i = 1; $i < $n; $i++ ) {
    		if ( $nums[$i-1] + $nums[$i] >=  $m ) {
    			return true;
    		}
    	}
    	return false;
    }
}

golang 解法, 执行用时: 12 ms, 内存消耗: 2.9 MB, 提交时间: 2023-08-07 15:30:44

func canSplitArray(nums []int, m int) bool {
	n := len(nums)
	if n <= 2 {
		return true
	}
	for i := 1; i < n; i++ {
		if nums[i-1]+nums[i] >= m {
			return true
		}
	}
	return false
}

cpp 解法, 执行用时: 12 ms, 内存消耗: 17.1 MB, 提交时间: 2023-08-07 15:30:15

class Solution {
public:
    bool canSplitArray(vector<int> &nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++)
            if (nums[i - 1] + nums[i] >= m)
                return true;
        return false;
    }
};

java 解法, 执行用时: 0 ms, 内存消耗: 40.7 MB, 提交时间: 2023-08-07 15:30:00

class Solution {
    public boolean canSplitArray(List<Integer> nums, int m) {
        int n = nums.size();
        if (n <= 2) return true;
        for (int i = 1; i < n; i++)
            if (nums.get(i - 1) + nums.get(i) >= m)
                return true;
        return false;
    }
}

python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-08-07 15:29:40

'''
脑筋急转弯
先特判 n≤2 的情况，这是满足要求的。
对于 n≥3 的情况，无论按照何种方式分割，一定会在某个时刻，分割出一个长为 2 的子数组。
如果 nums 中任何长为 2 的子数组的元素和都小于 m，那么无法满足要求。
否则，可以用这个子数组作为「核心」，像剥洋葱一样，一个一个地去掉 nums 的首尾元素，最后得到这个子数组。
由于子数组的元素和 ≥m，所以每次分割出一个元素时，剩余的子数组的元素和也必然是 ≥m 的，满足要求。
所以问题变成：判断数组中是否有两个相邻数字 ≥m。
'''
class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        return len(nums) <= 2 or any(x + y >= m for x, y in pairwise(nums))

上一题

下一题

详情