美文网首页
【算法题】100019. 将数组分割成最多数目的子数组

【算法题】100019. 将数组分割成最多数目的子数组

作者: 程序员小2 | 来源:发表于2023-10-01 09:16 被阅读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
    }
}

相关文章

  • 三路快排算法-求中位数问题(4)

    算法面试高频题,求前K个数,或者求中位数 三路快排算法思路 将数组分为三部分,随机选择数组中的一个数,使数组左边都...

  • 最小翻转数组

    问题描述 寻找数组的子数组,通过对该子数组进行排序,从而使得整个数组达到有序状态 算法1:确定边界法 首先确定子数...

  • golang实现堆排序

    算法题:给定一个整型数组,将数组的中的元素按升序排序。 基本思路:操作:排序输入:无序整型数组输出:有序整型数组 ...

  • 3.数组中最大子数组和

    一、相关概念 子数组:数组中连续出现的数 二、题目 题目 思路 1. 枚举O(nnn) 将数组所有的子数组列举出来...

  • 快速排序

    快速排序是一种分治算法。它是将一个数组分割成两个子数组,与归并排序不同的是:快速排序保证左边的数组元素都要小于右边...

  • 差分算法原理及代码模板

    1.一维差分算法 1.给定原始数组a = {a[1]、a[2]、...、a[n]} 2.目的:构造出数组b = {...

  • 算法:快速排序

    快速排序 快速排序是一种高效的排序算法,它基于将数据列划分为更小的数组。比如将一个数组分割成两个更小的数据。然后重...

  • js 对数组的处理

    concat() 用于连接两个数组,返回一个新数组,不改变原数组 join('.') 将数组通过指定的分隔符分割成...

  • 30-seconds-of-code

    Array(数组相关函数) chunk 将数组分割成指定长度的新数组。 使用Array.from()方法从一个类似...

  • JavaScript String.prototype.spli

    split用于将字符串分割成字符串数组

网友评论

      本文标题:【算法题】100019. 将数组分割成最多数目的子数组

      本文链接:https://www.haomeiwen.com/subject/widjbdtx.html