【算法题】100019. 将数组分割成最多数目的子数组
  FTGOknwdYkLB 2023年11月02日 32 0

题目:

给你一个只包含 非负 整数的数组 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^5
0 <= nums[i] <= 10^6

java代码:

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
    }
}


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
FTGOknwdYkLB