Skip to content

Latest commit

 

History

History
176 lines (137 loc) · 4.54 KB

File metadata and controls

176 lines (137 loc) · 4.54 KB
comments difficulty edit_url rating source tags
true
中等
1749
第 114 场双周赛 Q3
贪心
位运算
数组

English Version

题目描述

给你一个只包含 非负 整数的数组 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 <= 105
  • 0 <= nums[i] <= 106

解法

方法一:贪心 + 位运算

我们初始化一个变量 $score$,用来记录当前子数组的分数,初始时 $score = -1$。然后我们遍历数组,对于每个元素 $num$,我们将 $score$$num$ 进行按位与运算,然后将结果赋值给 $score$。如果 $score = 0$,说明当前子数组的分数为 $0$,我们就可以将当前子数组分割出来,然后将 $score$ 重置为 $-1$。最后我们返回分割出的子数组的个数。

时间复杂度 $O(n)$,其中 $n$ 是数组的长度。空间复杂度 $O(1)$

Python3

class Solution:
    def maxSubarrays(self, nums: List[int]) -> int:
        score, ans = -1, 1
        for num in nums:
            score &= num
            if score == 0:
                score = -1
                ans += 1
        return 1 if ans == 1 else ans - 1

Java

class Solution {
    public int maxSubarrays(int[] nums) {
        int score = -1;
        int ans = 1;
        for (int num : nums) {
            score &= num;
            if (score == 0) {
                ans++;
                score = -1;
            }
        }
        return ans == 1 ? 1 : ans - 1;
    }
}

C++

class Solution {
public:
    int maxSubarrays(vector<int>& nums) {
        int score = -1, ans = 1;
        for (int num : nums) {
            score &= num;
            if (score == 0) {
                --score;
                ++ans;
            }
        }
        return ans == 1 ? 1 : ans - 1;
    }
};

Go

func maxSubarrays(nums []int) int {
	ans, score := 1, -1
	for _, num := range nums {
		score &= num
		if score == 0 {
			score--
			ans++
		}
	}
	if ans == 1 {
		return 1
	}
	return ans - 1
}

TypeScript

function maxSubarrays(nums: number[]): number {
    let [ans, score] = [1, -1];
    for (const num of nums) {
        score &= num;
        if (score === 0) {
            --score;
            ++ans;
        }
    }
    return ans == 1 ? 1 : ans - 1;
}