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

Leetcode.2601 质数减法运算

题目链接

Leetcode.2601 质数减法运算 Rating : 1779

题目描述

给你一个下标从 0 开始的整数数组 nums,数组长度为 n

你可以执行无限次下述运算:

  • 选择一个之前未选过的下标 i ,并选择一个 严格小于 nums[i]的质数 ppp ,从 nums[i]中减去 ppp
    如果你能通过上述运算使得 nums成为严格递增数组,则返回 true;否则返回 false

严格递增数组 中的每个元素都严格大于其前面的元素。

示例 1:

输入:nums = [4,9,6,10]
输出:true
解释:
在第一次运算中:选择 i = 0 和 p = 3 ,然后从 nums[0] 减去 3 ,nums 变为 [1,9,6,10] 。
在第二次运算中:选择 i = 1 和 p = 7 ,然后从 nums[1] 减去 7 ,nums 变为 [1,2,6,10] 。
第二次运算后,nums 按严格递增顺序排序,因此答案为 true 。

示例 2:

输入:nums = [6,8,11,12]
输出:true
解释:nums 从一开始就按严格递增顺序排序,因此不需要执行任何运算。

示例 3:

输入:nums = [5,8,3]
输出:false
解释:可以证明,执行运算无法使 nums 按严格递增顺序排序,因此答案是 false 。

提示:

  • 1<=nums.length<=10001 <= nums.length <= 10001<=nums.length<=1000
  • 1<=nums[i]<=10001 <= nums[i] <= 10001<=nums[i]<=1000
  • nums.length==nnums.length == nnums.length==n

解法:筛素数 + 贪心 + 二分

由于 nums[i]nums[i]nums[i] 最大都只有 10310^3103,所以我们可以把 100010001000以内的素数预处理出来,存入 primesprimesprimes 数组中。

从后往前开始贪心,假设当前遍历到 nums[i]nums[i]nums[i] 了(i>0i > 0i>0):

  • 如果 nums[i]>nums[i−1]nums[i] > nums[i-1]nums[i]>nums[i1],符合递增的要求,之间跳过本次循环
  • 否则 nums[i]≤nums[i−1]nums[i] \leq nums[i-1]nums[i]nums[i1],我们将 nums[i−1]−nums[i]nums[i-1] - nums[i]nums[i1]nums[i] 的差值,记作 ddd
    • 我们通过 二分 的方式,从 primesprimesprimes 中找到第一个大于 ddd 的质数 ppp
    • nums[i−1]>pnums[i-1] > pnums[i1]>p 的情况下,nums[i−1]nums[i-1]nums[i1] 才能减去 ppp ,否则返回 falsefalsefalse
  • 循环结束返回 truetruetrue

时间复杂度: O(nlogn)O(nlogn)O(nlogn)

C++代码:

vector<int> primes;
const int N = 1e3+10;auto get_prime = [](){bool st[N + 1] = {};for(int i = 2;i <= N;i++){if(!st[i]) primes.push_back(i);for(auto p:primes){if(i * p > N) break;st[i * p] = true;if(i % p == 0) break;}}return 0;
}();class Solution {
public:bool primeSubOperation(vector<int>& nums) {int n = nums.size();for(int i = n - 1;i > 0;i--){if(nums[i] > nums[i-1]) continue;int d = nums[i-1] - nums[i];int idx = upper_bound(primes.begin(),primes.end(),d) - primes.begin();if(nums[i-1] > primes[idx]) nums[i - 1] -= primes[idx];else return false;}return true;}
};

相关文章:

Leetcode.2601 质数减法运算

题目链接 Leetcode.2601 质数减法运算 Rating &#xff1a; 1779 题目描述 给你一个下标从 0 开始的整数数组 nums&#xff0c;数组长度为 n 。 你可以执行无限次下述运算&#xff1a; 选择一个之前未选过的下标 i &#xff0c;并选择一个 严格小于 nums[i]的质数 ppp &…...

DP7416国产192K数字音频接收芯片兼容替代CS8416

目录192K 数字音频应用DP7416简介芯片特性192K 数字音频应用 采样率192khz&#xff0c;能将192,000hz以下的频率都录下来&#xff0c;而且对声波每秒连续采样192,000次。在回放的时候&#xff0c;这192,000个采样点按顺序播放&#xff0c;从而还原原来的声音。   过采样技术除…...

全球土壤湿度数据获取方法

土壤湿度亦称土壤含水率&#xff0c;表示土壤干湿程度的物理量。是土壤含水量的一种相对变量。通常用土壤含水量占干土重的百分数是示&#xff0c;亦称土壤质量湿度&#xff0c;如用土壤水分容积占土壤总容积的百分数表示&#xff0c;则称土壤容积湿度。通常说的土壤湿度&#…...

在proteus中仿真arduino实现矩阵键盘程序

矩阵键盘是可以解决我们端口缺乏的问题&#xff0c;当然&#xff0c;如果我们使用芯片来实现矩阵键盘的输入端口缺乏的问题将更加划算了&#xff0c;本文暂时不使用芯片来解决问题&#xff0c;而使用纯朴的8根线来实现矩阵键盘&#xff0c;目的是使初学者掌握原理。想了解使用芯…...

【ROS2指南-5】理解ROS2服务

目标&#xff1a;使用命令行工具了解 ROS 2 中的服务。 教程级别&#xff1a;初学者 时间&#xff1a; 10分钟 内容 背景 先决条件 任务 1 设置 2 ros2服务列表 3 ros2服务类型 4 ros2 服务查找 5 ros2界面展示 6 ros2 服务调用 概括 下一步 相关内容 背景 服务是 …...

探索Apache Hudi核心概念 (3) - Compaction

Compaction是MOR表的一项核心机制&#xff0c;Hudi利用Compaction将MOR表产生的Log File合并到新的Base File中。本文我们会通过Notebook介绍并演示Compaction的运行机制&#xff0c;帮助您理解其工作原理和相关配置。 1. 运行 Notebook 本文使用的Notebook是&#xff1a;《A…...

100Wqps异地多活,得物是怎么架构的?

说在前面 在40岁老架构师尼恩的数千读者群中&#xff0c;一直在指导大家简历和职业升级&#xff0c;前几天&#xff0c;指导了一个华为老伙伴的简历&#xff0c;小伙伴的优势在异地多活&#xff0c;但是在简历指导的过程中&#xff0c;尼恩发现&#xff1a; 异地多活的概念、异…...

35岁的测试工程师被公司强行辞退,感叹道:我以前就该好好努力了

曾经的高薪软件测试工程师&#xff0c;今年35岁了&#xff0c;被公司劝退了&#xff0c;外卖跑到凌晨&#xff0c;很累&#xff0c;但还是有一种想诉说的冲动。哪怕让大家觉得已经说得太多了&#xff0c;烦了&#xff0c;都成祥林嫂了&#xff0c;但是&#xff0c;我是真的想说…...

ASP.NET动态Web开发技术第5章

第5章数据验证一.预习笔记 1.验证控件概述&#xff1a; 2.RequiredFieldValidator&#xff08;必填验证&#xff09; 常用属性1&#xff1a;ControlToValidator:被验证的输入控件的ID 常用属性2&#xff1a;Text&#xff1a;验证失败时&#xff0c;验证控件显示的文本 常用…...

【数据结构与算法篇】时间复杂度与空间复杂度

目录 一、数据结构和算法 1.什么是数据结构&#xff1f; 2.什么是算法&#xff1f; 3.数据结构和算法的重要性 二、算法的时间复杂度和空间复杂度 1.算法效率 2.算法的复杂度 3.复杂度在校招中的考察 4.时间复杂度 5.空间复杂度 6.常见复杂度对比 7.复杂度的OJ练…...

HTTP API接口设计规范

1. 所有请求使用POST方法 使用post&#xff0c;相对于get的query string&#xff0c;可以支持复杂类型的请求参数。例如日常项目中碰到get请求参数为数组类型的情况。 便于对请求和响应统一做签名、加密、日志等处理 2. URL规则 URL中只能含有英文&#xff0c;使用英文单词或…...

数据一致性校验(pt-table-checksum)

介绍 pt-table-checksum 和 pt-table-sync 是 percona 公司发布的、检查 MySQL 主从数据库数据一致性校验的工具。pt-table-checksum 利用 MySQL 复制原理&#xff0c;在主库执行校验和计算&#xff0c;并对比主从库校验和&#xff0c;由此判断主从库数据是否一致。如果发现数…...

Talk预告 | 新加坡国立大学郑奘巍 AAAI‘23 杰出论文:大批量学习算法加速推荐系统训练

本期为TechBeat人工智能社区第486期线上Talk&#xff01; 北京时间3月30日(周四)20:00&#xff0c;新加坡国立大学二年级博士生——郑奘巍的Talk将准时在TechBeat人工智能社区开播&#xff01; 他与大家分享的主题是: “大批量学习算法加速推荐系统训练”&#xff0c;届时将分…...

肖 sir_就业课__004项目流程(H模型)

项目流程&#xff1a; 一、面试提问&#xff08;h模型&#xff09; 1、你说下你们公司测试流程&#xff1f; 2、给你一个需求你会怎么做? 3、你讲下你的工作&#xff1f; 4、谈谈你是如何去测试&#xff1f; 答案&#xff1a;h模型 要求第一人称来写 讲解简化文字流程&#x…...

snipaste 截图工具——可以使图片悬浮在任何软件上,方便对比

一、下载 官网下载地址&#xff1a;Snipaste Downloads &#xff08;需要梯子&#xff09; CSDN下载地址&#xff1a;https://download.csdn.net/download/weixin_43042683/87671809 1. 下载 压缩包后&#xff0c;免安装&#xff0c;直接解压后既可以使用。 2. 点击Snipaste.…...

Docker 快速部署Springboot项目

编写Dockerfile文件 # Docker image for springboot file run # VERSION 0.0.1 # Author: # 基础镜像使用java FROM openjdk:8 # 作者 MAINTAINER laihx # VOLUME 指定了临时文件目录为/tmp。 # 其效果是在主机 /var/lib/docker 目录下创建了一个临时文件&#xff0c;并链接到…...

【LeetCode: 剑指 Offer II 112. 最长递增路径 | 递归 | DFS | 深度优先遍历 | 记忆化缓存表】

&#x1f34e;作者简介&#xff1a;硕风和炜&#xff0c;CSDN-Java领域新星创作者&#x1f3c6;&#xff0c;保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享&#x1f48e;&#x1f48e;&#x1f48e; &#x1f34e;座右…...

hive 入门 一般用于正式环境 修改元数据(二)

安装配置可参考 https://blog.csdn.net/weixin_43205308/article/details/130020674 1、如果启动过derby&#xff0c;最小初始化过 在安装路径下删除 derby.log metastore_db rm -rf derby.log metastore_db此处省略安装mysql数据库 2、配置MySQL 登录mysql mysql -uroot …...

在RedHat系统上使用firewall-cmd命令可以将端口打开

在RedHat系统上使用firewall-cmd命令可以将端口打开&#xff0c;具体操作如下&#xff1a; 首先&#xff0c;检查当前系统使用的防火墙服务&#xff0c;比如firewalld或iptables&#xff0c;使用以下命令&#xff1a; systemctl status firewalld # 检查firewalld服务 system…...

分享(五):免费可用的多种类 API 大全集合整理

前言 搜罗了各大平台整理了一波免费可以用的 API &#xff0c;有需要的收藏起来啦。 实名认证 运营商二要素 API &#xff1a;运营商校验此姓名、手机号码是否一致。 运营商三要素 API&#xff1a;运营商验证姓名、身份证号码、手机号码是否一致&#xff0c;返回验证结果称…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

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

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

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...