当前位置: 首页 > article >正文

【Leetcode 每日一题 - 扩展】3097. 或值至少为 K 的最短子数组 II

问题背景

给你一个 非负 整数数组 n u m s nums nums 和一个整数 k k k
如果一个数组中所有元素的按位或运算 O R OR OR 的值 至少 k k k,那么我们称这个数组是 特别的
请你返回 n u m s nums nums最短特别非空 子数组的长度,如果特别子数组不存在,那么返回 − 1 -1 1

数据约束

  • 1 ≤ n u m s . l e n g t h ≤ 2 × 1 0 5 1 \le nums.length \le 2 \times 10 ^ 5 1nums.length2×105
  • 0 ≤ n u m s [ i ] ≤ 1 0 9 0 \le nums[i] \le 10 ^ 9 0nums[i]109
  • 0 ≤ k ≤ 1 0 9 0 \le k \le 10 ^ 9 0k109

解题过程

和 模板题 很像,只是改成了求长度,同样可以用 LogTrick 或是滑窗来解决。

具体实现

LogTrick

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            // 由于单个数字是结果最小的情形,可以直接返回避免后续的冗余计算
            if(cur >= k) {
                return 1;
            }
            // 和暴力解的区别就在于多进行了一个判断,去掉了不必要的遍历
            for(int j = i - 1; j >= 0 && (nums[j] | cur) != nums[j]; j--) {
                nums[j] |= cur;
                if(nums[j] >= k) {
                    res = Math.min(res, i - j + 1);
                }
            }
        }
        // 注意要根据 res 是否被更新过来判断返回的结果
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

滑动窗口

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int bottom = 0;
        int rightOr = 0;
        for(int left = 0, right = 0; right < nums.length; right++) {
            // 元素从窗口右侧进入
            rightOr |= nums[right];
            while(left <= right && (nums[left] | rightOr) >= k) {
                // 更新结果,注意 left 指针要自增,如果觉得不直观分开写也是可以的
                res = Math.min(res, right - left++ + 1);
                // bottom 始终指向栈底,它在窗口之外表示 rightOr 的结果没有被 nums 数组记录
                if(bottom < left) {
                    // 遍历并把结果更新到 nums 数组中
                    for(int i = right - 1; i >= left; i--) {
                        nums[i] |= nums[i + 1];
                    }
                    // 更新栈底指针
                    bottom = right;
                    // 重置右侧或运算结果
                    rightOr = 0;
                }
            }
        }
        // 注意要根据 res 是否被更新过来判断返回的结果
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

http://www.kler.cn/a/506574.html

相关文章:

  • 最佳股票买卖时机问题
  • Redis Cluster和Sentinel模式,如何选择?
  • 【HarmonyOS NAPI 深度探索6】使用 N-API 创建第一个 Hello World 原生模块
  • 前端开发:盒子模型、块元素
  • 【机器学习实战入门项目】使用Python创建自己的表情符号
  • 鸿蒙UI开发——基于onTouch事件实现表情选择胶囊
  • 如何学习网络安全?有哪些小窍门?
  • 计算机网络(五)——传输层
  • 【Linux入门】一、权限的理解
  • 使用vnstat监控网络流量和带宽占用
  • <OS 有关>Ubuntu 24 安装 openssh-server, tailscale+ssh 慢增加
  • 大模型WebUI:Gradio全解11——Chatbots:融合大模型的多模态聊天机器人(3)
  • 文件上传 分片上传
  • HarmonyOS命令行工具
  • 【学习路线】Python自动化运维 详细知识点学习路径(附学习资源)
  • Java List过滤 Stream API filter() 应用
  • Ubuntu升级Linux内核教程
  • 基于Web的宠物医院看诊系统设计与实现(源码+定制+开发)在线预约平台、宠物病历管理、医生诊疗记录、宠物健康数据分析 宠物就诊预约、病历管理与健康分析
  • 【C/C++】#pragma pack(1)与#pragma pack(push,1)的区别
  • Linux基本指令(3)