美文网首页
【算法题】或值至少 K 的最短子数组 I

【算法题】或值至少 K 的最短子数组 I

作者: 程序员小2 | 来源:发表于2024-03-30 09:59 被阅读0次

题目:

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ,那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空
子数组
的长度,如果特别子数组不存在,那么返回 -1 。

示例 1:

输入:nums = [1,2,3], k = 2

输出:1

解释:

子数组 [3] 的按位 OR 值为 3 ,所以我们返回 1 。

示例 2:

输入:nums = [2,1,8], k = 10

输出:3

解释:

子数组 [2,1,8] 的按位 OR 值为 11 ,所以我们返回 3 。

示例 3:

输入:nums = [1,2], k = 0

输出:1

解释:

子数组 [1] 的按位 OR 值为 1 ,所以我们返回 1 。

提示:

1 <= nums.length <= 50
0 <= nums[i] <= 50
0 <= k < 64

思路:

穷举,
将数组里的每个元素或运算,用shorts记录最小的或运算结果,然后和k比较大小。

java代码:

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int shorts = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int temp = 0;
            for (int j = i; j < nums.length; j++) {
                temp = temp|nums[j];
                if (temp>=k){
                    shorts = Math.min(shorts,j-i+1);
                    break;
                }

            }
        }
        if (shorts==Integer.MAX_VALUE){
            return -1;
        }
        return shorts;
    }
}

相关文章

  • LeetCode 862. 和至少为 K 的最短子数组

    返回 A 的最短的非空连续子数组的长度,该子数组的和至少为 K 。如果没有和至少为 K 的非空子数组,返回 -1。...

  • 最短路径 - Floyd算法

    算法思想 Floyd算法是一种动态规划算法,查找i到j之间的最短距离,我们可以找一个中间点k,然后变成子问题,i到...

  • 【教3妹学算法-每日3题(3)】 和至少为 K 的最短子数组

    插: 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。[http...

  • 2.2.3 无序数组需要排序的最短子数组

    对于一个无序数组A,请设计一个算法,求出需要排序的最短子数组的长度。 给定一个整数数组A及它的大小n,请返回最短子...

  • 最短路径(Floyd算法)

    最短路径:两顶点之间经过的边上权值之和最小的路径。 Floyd算法:使用两个数组,数组P记录起点v到其他顶点的最短...

  • floyd算法解析

    floyd算法可求得多源点间的最短路径算法使用动态规划求解: 状态转移方程 dp[i][j][k]=min(dp[...

  • 二维数组定位

    在一维数组或二维数组中取k1-k2区间的值

  • 《剑指Offer》-42.连续子数组的最大和

    题干 输入一个整形数组,数组里有正数也有负数。数组中的一个或连续多个正数组成一个子数组。求所有子数组的和的最大值。...

  • 区间---RMQ区间最值查询

    RMQ区间最值查询,对于长度为n的数组A[]。RMQ(i,j),返回数组A区间[i , j]内的最大值或最小值。 ...

  • LeetCode

    原题 给定一个包含非负数的数组和一个目标整数 k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,...

网友评论

      本文标题:【算法题】或值至少 K 的最短子数组 I

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