当前位置: 首页 > 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;返回验证结果称…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...