力扣665. 非递减数列 475.供暖屋

ops/2025/3/16 20:19:39/

给你一个长度为 n 的整数数组 nums ,请你判断在 最多 改变 1 个元素的情况下,该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的: 对于数组中任意的 i (0 <= i <= n-2),总满足 nums[i] <= nums[i + 1]

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

提示:

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums[i] <= 105

思路:

当我们遇见nums[i]<=nums[i+1],且nums[i+1]>nums[i+2]时

1.如果nums[i+2]<nums[i],为了能变成不递减序列,我们只能将nums[i+2]变大,且nums[i+2]要>=nums[i+1]才能将序列变为非递减序列

举例:[2,3,1,4]->[2,3,3,4]

2.如果nums[i+2]>=nums[i],那么我们可以选择增加nums[i+2]或者减小nums[i+1],我们要选择减小nums[i+1],这样会让后面的序列更容易变成递增序列,特别注意 i=0时,nums[i]>nums[i+1],选择将nums[i]减小

举例:[2,4,3,5]->[2,3,3,5]| [2,4,4,5]

代码参考:

class Solution {public boolean checkPossibility(int[] nums) {int cnt=0;for(int i=0;i<nums.length-1;i++){int x=nums[i];int y=nums[i+1];if(x>y){if(cnt>0){return false;}cnt++;if(i>0&&y<nums[i-1]){nums[i+1]=x;}else{nums[i]=y;}}}return true;}}

475. 供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在,给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置,请你找出并返回可以覆盖所有房屋的最小加热半径。

注意:所有供暖器 heaters 都遵循你的半径标准,加热的半径也一样。

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1,那么所有房屋就都能得到供暖。

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1,这样所有房屋就都能得到供暖。

示例 3:

输入:houses = [1,5], heaters = [2]
输出:3

提示:

  • 1 <= houses.length, heaters.length <= 3 * 104
  • 1 <= houses[i], heaters[i] <= 109

思路:

本题使用双指针,先将房屋和供暖期从小到大排序,对于每个房屋,得到它与周围供暖器的最近距离,这些最近距离中的最大值就为最小加热半径

class Solution {public int findRadius(int[] houses, int[] heaters) {int maxR=0;Arrays.sort(houses);Arrays.sort(heaters);for(int i=0,j=0;i<houses.length;i++){int curDistance=Math.abs(houses[i]-heaters[j]);while(j<heaters.length-1&&Math.abs(heaters[j]-houses[i])>=Math.abs(heaters[j+1]-houses[i])){j++;//寻找离当前房屋最近的供暖器curDistance=Math.min(curDistance,Math.abs(houses[i]-heaters[j]));}maxR=Math.max(maxR,curDistance);}return maxR;}}

文章来源:https://blog.csdn.net/2301_76352996/article/details/146094183
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/ops/166307.html

相关文章

SAP Commerce(Hybris)营销模块(一):商城产品折扣配置

基于Hybris的Backoffice后台管理系统&#xff0c;创建一个基于模板的营销规则&#xff0c;并配置上对应的优惠活动。 架构设计 先从一张架构图说起 Hybris的促销模块&#xff0c;是基于Promotion引擎来实现的&#xff0c;可以通过Backoffice来进行配置。 通过上面的架构图又可…

在 CentOS 上安装 Oracle 数据库

文章目录 **1. 系统准备****1.1 检查系统要求****1.2 更新系统****1.3 安装必要的依赖包****1.4 创建 Oracle 用户和组****1.5 配置内核参数****1.6 配置用户限制****1.7 配置 PAM 模块****1.8 创建 Oracle 安装目录** **2. 下载 Oracle 数据库安装包****2.1 访问 Oracle 官方网…

理解 Retrofit 请求头与 GsonConverterFactory 的自动处理机制

在现代 Web 开发中&#xff0c;特别是在与 RESTful API 进行交互时&#xff0c;我们经常会遇到 JSON 格式的数据交换。为了确保请求的正确解析和响应的准确返回&#xff0c;通常需要通过 HTTP 请求头明确指定请求体的数据类型。而 Content-Type: application/json 就是用来告诉…

【蓝桥】模拟

一、引言 在算法学习的道路上&#xff0c;模拟算法是基础且重要的一环。它就像编程世界里的“模仿大师”&#xff0c;通过还原现实场景解决问题。无论是编程新手还是竞赛选手&#xff0c;掌握模拟算法都能提升对问题的拆解能力与代码实现细节的把控。今天&#xff0c;就让我们深…

ps简单替换icon颜色操作

适合前端小白, 这里使用 ps 2023, ps cc 2019 版本来简单修改一下颜色 有如下的icons背景图片, 需要将高亮的图标颜色替换一下 在ps中打开图片 Ctrl Shift N 打开"新建图层"(或使用菜单: 图层 -> 新建 -> 图层) 选择 “使用前一图层创建剪贴蒙版”, 然后确…

[CISSP] [3] 人员安全与社会工程

#AUP # NDA # UBA # UEBA # 风险管理 # 社会工程 # 钓鱼邮件前置词 # Spear Phishing # Whaling Phishing # Smishing # Vishing # Shoulder Surfing # 发票诈骗 # Tailgating # Piggybacking # Dumpster Diving AUP AUP的关键内容 AUP 主要包括以下方面&#xff1a; 目的和…

Java中的深拷贝与浅拷贝

在Java中&#xff0c;深拷贝和浅拷贝是两种不同的对象复制方式&#xff0c;主要区别在于它们如何处理对象内部的引用类型字段。 浅拷贝&#xff08;Shallow Copy&#xff09; 浅拷贝创建一个新对象&#xff0c;并将原对象的字段值复制到新对象中。如果字段是基本类型&#xf…

本地知识库RAG总结

目录 RAG流程: 知识库的要求&#xff1a; 知识抽取&#xff1a; 知识存储: 向量化: 知识检索: 应用客户端: RAG智能问答应用几个痛点&#xff1a; 如何提升召回率改进思路&#xff1a; 如何提升回答专业性&#xff1a; RAG评测&#xff1a; 总结&#xff1a; 参考…