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

Leetcode 3097. Shortest Subarray With OR at Least K II

  • Leetcode 3097. Shortest Subarray With OR at Least K II
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3097. Shortest Subarray With OR at Least K II

1. 解题思路

这一题是题目3095的一个进阶版本,但也就是增加了序列的复杂度而已,要求我们能够在 O ( N ) O(N) O(N)的算法复杂度内完成而已。

一个直接的思路就是滑动窗口,我们只需要不断地维护一个滑动窗口即可,逐步移动左边界 i i i,然后维护右边界 j j j使得滑动窗口内的或值始终大于等于 k k k即可。

唯一需要注意的是,由于或操作有叠加效果,因此我们需要记录每一个位上出现的 1 1 1的总的次数,确保删除一个数之后依然可以准确获得后续所有值的或操作结果。

2. 代码实现

给出python代码实现如下:

class Solution:def minimumSubarrayLength(self, nums: List[int], k: int) -> int:def num2digit(num):ret = [0 for _ in range(32)]idx = 31while num > 0:ret[idx] = num % 2num = num // 2idx -= 1return retdef is_greater(digit1, digit2):for i in range(32):if digit1[i] > 0 and digit2[i] == 0:return Trueelif digit1[i] == 0 and digit2[i] > 0:return Falsereturn Truei, j, n = 0, 0, len(nums)ans = n+1dk = num2digit(k)digit = [0 for _ in range(32)]while i < n:while j < n and (j ==i or not is_greater(digit, dk)):dj = num2digit(nums[j])digit = [x+y for x, y in zip(digit, dj)]j += 1if is_greater(digit, dk):ans = min(ans, j-i)else:breakdi = num2digit(nums[i])digit = [x-y for x, y in zip(digit, di)]i += 1return ans if ans != n+1 else -1     

提交代码评测得到:耗时3221ms,占用内存38MB。

相关文章:

Leetcode 3097. Shortest Subarray With OR at Least K II

Leetcode 3097. Shortest Subarray With OR at Least K II 1. 解题思路2. 代码实现 题目链接&#xff1a;3097. Shortest Subarray With OR at Least K II 1. 解题思路 这一题是题目3095的一个进阶版本&#xff0c;但也就是增加了序列的复杂度而已&#xff0c;要求我们能够在…...

算法系列--递归,回溯,剪枝的综合应用(2)

&#x1f495;"对相爱的人来说&#xff0c;对方的心意&#xff0c;才是最好的房子。"&#x1f495; 作者&#xff1a;Lvzi 文章主要内容&#xff1a;算法系列–递归,回溯,剪枝的综合应用(2) 大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(2) 一.括号…...

Docker搭建LNMP环境实战(09):安装mariadb

1、编写mariadb部署配置文件 在文件夹&#xff1a;/mnt/hgfs/dockers/test_site/compose下创建文件&#xff1a;test_site_mariadb.yml&#xff0c;内容如下&#xff1a; version: "3.5" services:test_site_mariadb:container_name: test_site_mariadbimage: mari…...

基于Python的微博舆论分析,微博评论情感分析可视化系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

Flutter iOS上架指南

本文探讨了使用Flutter开发的iOS应用能否上架&#xff0c;以及上架的具体流程。苹果提供了App Store作为正式上架渠道&#xff0c;同时也有TestFlight供开发者进行内测。合规并通过审核后&#xff0c;Flutter应用可以顺利上架。但上架过程可能存在一些挑战&#xff0c;因此可能…...

实操:driver.js 实现产品导览、亮点、上下文帮助

官网 https://driverjs.com/ 依赖 <script src"https://cdn.jsdelivr.net/npm/driver.js1.0.1/dist/driver.js.iife.js"></script> <link rel"stylesheet" href"https://cdn.jsdelivr.net/npm/driver.js1.0.1/dist/driver.css"/…...

【JavaWeb】Day29.SpringBootWeb请求响应——请求(二)

请求响应 4.数组集合参数 数组集合参数的使用场景&#xff1a;在HTML的表单中&#xff0c;有一个表单项是支持多选的(复选框)&#xff0c;可以提交选择的多个值。 4.1 数组 数组参数&#xff1a;请求参数名与形参数组名称相同且请求参数为多个&#xff0c;定义数组类型形参即…...

asf是什么格式的文件?用手机怎么打开?

由于手机操作系统和硬件的限制&#xff0c;大部分手机并不直接支持asf文件的播放。因此&#xff0c;如果你想在手机上打开asf文件&#xff0c;你可能需要先将文件转换为手机支持的格式&#xff0c;如MP4。可以通过使用一些视频转换软件来实现&#xff0c;比如野葱视频转换器。 …...

picGo图床搭建gitee和smms(建议使用)

picGoGitee 这个需要下载gitee插件, 因为官方频繁的检索文件类型, 有时候也会失效 如果没有特殊要求平时存个学习的要看图中文字的重要的图片建议就是smms, 免费也够用! 图片存本地不方便, 各种APP中来回传还会失帧损失画质, 所以你值得往下看 picGosmms 建议使用这个, sm…...

LeetCode | 数组 | 二分查找 | 35.搜索插入位置【C++】

题目链接 题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出…...

Linux 给网卡配置ip

ip addr | grep eth9 ifconfig eth9 10.0.0.2 netmask 255.255.255.0 up...

【C语言】翻译环境与运行环境

一、前言 在我们学习C语言的时候&#xff0c;第一个接触的程序就是&#xff1a;在屏幕上打印” hello word! “&#xff0c;可当时的我们却未去深入的理解与感悟&#xff0c;一个程序代码是如何运行的&#xff1b;而这一期的博客&#xff0c;则是带着我们&#xff0c;通过C代码…...

ubuntu20.04执行sudo apt-get update失败的解决方法

参考&#xff1a;执行sudo apt-get update失败的解决方案 1、换源型错误 &#xff08;1&#xff09;编辑/etc/apt/sources.list文件 在命令行中输入&#xff1a; sudo vim /etc/apt/sources.list 或者 sudo gedit /etc/apt/sources.list 推荐使用后者 &#xff08;2&#xf…...

接口调用成功后端却一直返回404

vuespringboot 我在vue.config.js中配置了向后端的反向代理 然后使用了axios向后端发送post请求 可以看到可以接收到前端传来的值 但是前端控制台却报了 “xhr.js:245POST http://localhost:7777/api/login 404 (Not Found)” 最后询问我那智慧的堂哥... ... 解决办法是把C…...

【Vmware】 debian 12 安装教程

1.前提说明 VMware 17.5.1 (自行安装)&#xff0c;参考Debian 12maven 3.8.7git 2.39.2jdk 1.8 / 11 / 17 1.1.Debian 下载 访问(https://www.debian.org/download) 下载 Debian 这是 Debian 12&#xff0c;代号为 bookworm&#xff0c;网络安装&#xff0c;用于 64 位 PC&a…...

YooAssets 使用相关

## 使用 YooAssets 动态加载原生文件时候 > 原生文件&#xff1a;txt&#xff1b;json&#xff1b;等需要直接保存文件内string字符的文件 需要将打包方式设置成为&#xff0c;PackRawFile 并且加载时候使用 API &#xff1a; YooAssets.LoadRawFileSync()YooAssets.LoadRa…...

精准扶贫管理系统|基于Springboot的精准扶贫管理系统设计与实现(源码+数据库+文档)

精准扶贫管理系统目录 目录 基于Springboot的精准扶贫管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 &#xff08;1&#xff09;用户信息管理 &#xff08;2&#xff09;贫困户信息管理 &#xff08;3&#xff09;新闻类型管理 &a…...

Flutter与iOS和Android原生页面交互

一、Flutter 与原生页面交互的重要性和应用场景 Flutter 是一个由 Google 开发的开源框架&#xff0c;用于创建跨平台的移动、Web 和桌面应用程序。Flutter 允许开发者使用一套代码库为 Android 和 iOS 等平台构建美观、高性能的应用程序。然而&#xff0c;尽管 Flutter 提供了…...

Chrome安装Vue插件vue-devtools

直接通过网站&#xff1a; Home | Vue Devtools (vuejs.org) chrome扩展商城中搜索&#xff1a;Vue.js devtools 参考下面edge扩展商城的图&#xff0c;两者流程相近...

内存和网卡压力测试

1.内存压力测试 1.1测试目的 内存压力测试的目的是评估开发板中的内存子系统性能和稳定性&#xff0c;以确保它能够满足特定的应用需求。开发板通常用于嵌入式系统、物联网设备、嵌入式智能家居等场景&#xff0c;这些场景对内存的要求通常比较高。 其内存压力测试的主要目的…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...