将数组分割成最多数目的子数组

100019. 将数组分割成最多数目的子数组

给你一个只包含非负整数的数组 nums 。

我们定义满足 l <= r 的子数组 nums[l..r] 的分数为 nums[l] AND nums[l + 1] AND ... AND nums[r] ，其中 AND 是按位与运算。

请你将数组分割成一个或者更多子数组，满足：

每个元素都只属于一个子数组。
子数组分数之和尽可能小。

请你在满足以上要求的条件下，返回最多可以得到多少个子数组。

一个 子数组 是一个数组中一段连续的元素。

示例 1：

输入：nums = [1,0,2,0,1,2]
输出：3
解释：我们可以将数组分割成以下子数组：
- [1,0] 。子数组分数为 1 AND 0 = 0 。
- [2,0] 。子数组分数为 2 AND 0 = 0 。
- [1,2] 。子数组分数为 1 AND 2 = 0 。
分数之和为 0 + 0 + 0 = 0 ，是我们可以得到的最小分数之和。
在分数之和为 0 的前提下，最多可以将数组分割成 3 个子数组。所以返回 3 。

示例 2：

输入：nums = [5,7,1,3]
输出：1
解释：我们可以将数组分割成一个子数组：[5,7,1,3] ，分数为 1 ，这是可以得到的最小总分数。
在总分数为 1 的前提下，最多可以将数组分割成 1 个子数组。所以返回 1 。

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maxSubarrays(vector<int>& nums) { } };

golang 解法, 执行用时: 120 ms, 内存消耗: 9.4 MB, 提交时间: 2023-10-02 00:14:24

func maxSubarrays(nums []int) (ans int) {
	and := -1 // -1 就是 111...1，和任何数 AND 都等于那个数
	for _, x := range nums {
		and &= x
		if and == 0 {
			ans++ // 分割
			and = -1
		}
	}
	return max(ans, 1) // 如果 ans=0 说明所有数的 and>0，答案为 1
}

func max(a, b int) int { if b > a { return b }; return a }

python3 解法, 执行用时: 108 ms, 内存消耗: 26.1 MB, 提交时间: 2023-10-02 00:14:13

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        ans = 0
        a = -1  # -1 就是 111...1，和任何数 AND 都等于那个数
        for x in nums:
            a &= x
            if a == 0:
                ans += 1  # 分割
                a = -1
        return max(ans, 1)  # 如果 ans=0 说明所有数的 and>0，答案为 1

java 解法, 执行用时: 3 ms, 内存消耗: 53.6 MB, 提交时间: 2023-10-02 00:14:01

class Solution {
    public int maxSubarrays(int[] nums) {
        int ans = 0;
        int a = -1; // -1 就是 111...1，和任何数 AND 都等于那个数
        for (int x : nums) {
            a &= x;
            if (a == 0) {
                ans++; // 分割
                a = -1;
            }
        }
        return Math.max(ans, 1); // 如果 ans=0 说明所有数的 and>0，答案为 1
    }
}

cpp 解法, 执行用时: 104 ms, 内存消耗: 102.6 MB, 提交时间: 2023-10-02 00:13:51

class Solution {
public:
    int maxSubarrays(vector<int> &nums) {
        int ans = 0;
        int a = -1; // -1 就是 111...1，和任何数 AND 都等于那个数
        for (int x : nums) {
            a &= x;
            if (a == 0) {
                ans++; // 分割
                a = -1;
            }
        }
        return max(ans, 1); // 如果 ans=0 说明所有数的 and>0，答案为 1
    }
};

rust 解法, 执行用时: 12 ms, 内存消耗: 3.1 MB, 提交时间: 2023-10-02 00:13:39

impl Solution {
    pub fn max_subarrays(nums: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut a = -1; // -1 就是 111...1，和任何数 AND 都等于那个数
        for x in nums {
            a &= x;
            if a == 0 {
                ans += 1; // 分割
                a = -1;
            }
        }
        ans.max(1) // 如果 ans=0 说明所有数的 and>0，答案为 1
    }
}

javascript 解法, 执行用时: 92 ms, 内存消耗: 51.4 MB, 提交时间: 2023-10-02 00:13:28

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubarrays = function(nums) {
    let ans = 0;
    let a = -1; // -1 就是 111...1，和任何数 AND 都等于那个数
    for (const x of nums) {
        a &= x;
        if (a === 0) {
            ans++; // 分割
            a = -1;
        }
    }
    return Math.max(ans, 1); // 如果 ans=0 说明所有数的 and>0，答案为 1
};

上一题

下一题

详情