LeetCode算法题解——双指针2
LeetCode算法题解——双指针2
- 第五题
- 思路
- 代码
- 第六题
- 思路
- 代码
- 第七题
- 思路
- 代码
这里介绍双指针在数组中的第二类题型:两端夹击。
第五题
977. 有序数组的平方
题目描述:
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
思路
因为是排序每个数字的平方,根据二次函数图像y=x^2开口向上可得,最大值在两端,最小值在中间。所以,最左和最右进行比较,两端夹击,看谁的平方值更大。
代码
class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int[] result = new int[n];int l = 0;int r = n - 1;int k = n - 1;while(l <= r){if(nums[l] * nums[l] > nums[r] * nums[r]){result[k] = nums[l] * nums[l];l++;k--;}else{result[k] = nums[r] * nums[r];r--;k--;}}return result;}
}
第六题
167. 两数之和 II - 输入有序数组
题目描述:
给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
示例1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
思路
可以先考虑边界情况。升序数组中任意两个元素求和,最小为nums[0]+nums[1],最大为nums[n-2]+nums[n-1]。target的范围一定在这两者之间,否则找不到答案。所以,我们可以两端夹击,一直手抓nums[0],另一只手抓nums[n-1]。如果是最小的情况,那么让nums[n-1]向nums[1]靠拢;如果是最大的情况,那么让nums[1]向nums[n-2]靠拢。
代码
class Solution {public int[] twoSum(int[] numbers, int target) {int l = 0, r = numbers.length - 1;int[] result = new int[]{0, 0};while(l < r){int sum = numbers[l] + numbers[r];if(sum == target){result[0] = l + 1;result[1] = r + 1;break;}else if(sum < target){l++;}else{r--;}}return result;}
}
第七题
633. 平方数之和
题目描述:
给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a^2 + b^2 = c 。
示例1:
输入:c = 5
输出:true
解释:1 * 1 + 2 * 2 = 5
思路
上一题是两个数的和是否为target,这道题是两个数的平方和是否为target。一样的思路,考虑最大最小值。若两个数的平方和为target,则最小为0,最大为target的平方根。同样的,两端夹击。
代码
class Solution {public boolean judgeSquareSum(int c) {long l = 0;long r = (long) Math.sqrt(c);while(l <= r){long m = l * l + r * r;if(m == c){return true;}else if(m < c){l++;}else{r--;}}return false;}
}
下一篇博客LeetCode算法题解——双指针3中,我将分享LeetCode中关于字符串的双指针问题。
参考:
Leetcode 题解 - 双指针
相关文章:
LeetCode算法题解——双指针2
LeetCode算法题解——双指针2第五题思路代码第六题思路代码第七题思路代码这里介绍双指针在数组中的第二类题型:两端夹击。 第五题 977. 有序数组的平方 题目描述: 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的…...
线性杂双功能peg化试剂——HS-PEG-COOH,Thiol-PEG-Acid
英文名称:HS-PEG-COOH,Thiol-PEG-Acid 中文名称:巯基-聚乙二醇-羧基 HS-PEG-COOH是一种含有硫醇和羧酸的线性杂双功能聚乙二醇化试剂。它是一种有用的带有PEG间隔基的交联或生物结合试剂。巯基或SH、巯基或巯基选择性地与马来酰亚胺、OPSS、…...
Linux第三讲
目录 三、 磁盘和文件管理和使用检测和维护 3.1 磁盘目录 3.2 安装软件 3.2.1 rpm命令 3.2.2 克隆虚拟机 3.2.3 yum或压缩包方式安装jdk 3.2.4 使用虚拟机运行SpringBoot项目 3.2.5 安装mysql80(57) 3.2.6 运行web项目 3.2.7 安装tomcat 三、 …...
SpringBoot07:SpringSecurity
Security是什么? 是一个安全框架。可以用来做认证和授权 官网:Spring Security SpringSecurity环境搭建 1、创建一个新的project 2、导入thymeleaf依赖 <dependency><groupId>org.thymeleaf</groupId><artifactId>thymeleaf…...
C++ 浅谈之 STL Vector
C 浅谈之 STL Vector HELLO,各位博友好,我是阿呆 🙈🙈🙈 这里是 C 浅谈系列,收录在专栏 C 语言中 😜😜😜 本系列阿呆将记录一些 C 语言重要的语法特性 🏃&…...
【个人作品】非侵入式智能开关
一、产品简介 一款可以通过网络实现语音、APP、小程序控制,实现模拟手动操作各种开关的非侵入式智能开关作品。 非侵入式,指的是不需要对现有的电路和开关做任何改动,只需要将此设备使用魔术无痕胶带固定在旁边即可。 以下为 ABS 材质的渲…...
数据存储技术复习(三)未完
module4智能存储系统是功能丰富且可提供高度优化的I/o处理能力的RAID阵列。请绘制智能存储系统架构,并说明其各个关键组件的主要功能。前端缓存后端物理磁盘2.智能存储系统中,使用缓存进行的写入操作与直接写入到磁盘相比,可以带来…...
ThinkPHP数据库迁移工具
安装 composer require topthink/think-migration 创建迁移工具文件 //执行命令,创建一个操作文件,一定要用大驼峰写法,如下 php think migrate:create AnyClassNameYouWant //执行完成后,会在项目根目录多一个database目录,这里面存放类库操作文件 //文件名类似/database/m…...
代理模式(Proxy Pattern)
代理模式定义: 提供了对目标对象另外的访问方式;即通过代理对象访问目标对象。举个例子:猪八戒去找高翠兰结果是孙悟空变的,可以这样理解:把高翠兰的外貌抽象出来,高翠兰和孙悟空都实现了这个接口ÿ…...
Elasticesearch内存详解
1.ES基本概念 为了更好的理解内存,我们先看一下ES的基本概念。 1.1 cluster 集群 多个节点组合在一起就形成了一个集群,在每个ES节点中,我们可以通过配置集群的名称来使各个节点组合在一起,成为一个集群。当某些节点的集群名称一样,ES会自动根据配置文件中的地址找到这些…...
SpringCloud之断路器聚合监控
一、Hystrix Turbine简介 看单个的Hystrix Dashboard的数据并没有什么多大的价值,要想看这个系统的Hystrix Dashboard数据就需要用到Hystrix Turbine。Hystrix Turbine将每个服务Hystrix Dashboard数据进行了整合。Hystrix Turbine的使用非常简单,只需要…...
凭借这份《2022测试八股文》候选者逆袭面试官,offer拿到手软
《2023测试面试八股文》800 道软件测试面试真题,高清打印版打包带走,横扫软件测试面试高频问题,涵盖测试理论、Linux、MySQL、Web 测试、接口测试、App 测试、Python、Selenium、性能测试、LordRunner、计算机网络、数据结构与算法、逻辑思维…...
【i2c协议介绍】
文章目录协议简单介绍五种速度模式master/slave和transmitter/receiver关系第一种情况:master作为transmitter,slave作为receiver第二种情况:当master作为receiver,slave作为transmitteri2c基本信号start产生stop信号数据传输有效…...
167. 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 < index1 < index2 < numbers…...
编译与链接------《程序员的自我修养》
本篇整理于《程序员的自我修养》一书中编译与链接相关知识,整理的目的是为了更加深入的了解编译于链接的更多底层知识,面对程序运行时种种性能瓶颈我们束手无策。我们看到的是这些问题的现象,但是却很难看清本质,所有这些问题的本质就是软件运…...
5分钟搞懂 强缓存与协商缓存
Ⅰ、http缓存 HTTP 缓存策略 分为 > 「强制缓存」 和 「协商缓存」 为什么需要 HTTP 缓存 呢 ? 👇 直接使用缓存速度 >> 远比重新请求快 缓存对象有那些呢 ?👇 「图片」 「JS文件」 「CSS文件」 等等 文章目录Ⅰ、http缓存Ⅱ…...
Ts笔记第一天
文章目录安装 ts运行环境 nodeTS类型数字 、字符串 和布尔类型字面量any 和unknown类型断言void和neverobjectArraytuple 元组enum 枚举安装 ts运行环境 node node-v看版本号 2. 安装ts -g全局安装 npm i -g typescript // 这里全局安装 -s安装无法使用tsc 创建一个01.ts文…...
Android 12 Activity启动流程
Android 12 Activity启动过程 参考文献: startActivity启动过程分析 Activity启动流程(Android 12) 概述 Activity启动发起后,是通过Binder最终交由system进程中的AMS来完成。 一、启动流程 frameworks/base/core/java/android/app/Activity.java f…...
VCS®/VCSi™User Guide
VCS是一种高性能、高容量的Verilog模拟器,它将先进的高级抽象验证技术集成到一个开放的本地平台中。VCS是一个编译代码模拟器。它使您能够分析、编译和模拟Verilog、SystemVerilog、OpenVera和SystemC设计描述。它还为您提供了一组模拟和调试功能,以验证…...
MongoDB简介及SpringBoot整合
一、概述MongoDB中的记录是一个文档,它是一个数据结构组成 字段和值对。MongoDB文档类似于JSON。对象。字段的值可能包括其他文档、数组、 和文档数组:数据库(Database):和关系型数据库一样,每个数据库中有…...
Neovim涂抹光标插件:提升编码体验的动态轨迹设计
1. 项目概述:一个为Neovim设计的“涂抹光标”插件 如果你和我一样,是个重度Neovim用户,每天有超过8小时的时间泡在终端和代码编辑器里,那你肯定对光标的“存在感”有要求。默认的方块或下划线光标,在长时间编码后&…...
3步解锁联想刃7000k BIOS隐藏功能:安全提升硬件性能的完整指南
3步解锁联想刃7000k BIOS隐藏功能:安全提升硬件性能的完整指南 【免费下载链接】Lenovo-7000k-Unlock-BIOS Lenovo联想刃7000k2021-3060版解锁BIOS隐藏选项并提升为Admin权限 项目地址: https://gitcode.com/gh_mirrors/le/Lenovo-7000k-Unlock-BIOS 联想刃7…...
大部分 App 没准备好被 Agent 操作——这是设计缺陷,不是功能缺失
大部分 App 没准备好被 Agent 操作——这是设计缺陷,不是功能缺失 2025 年被很多人称为「AI Agent 元年」。 Claude Code、Cursor、Windsurf……一批 agentic 工具密集涌现,Agent 不再只是聊天框里的助手,它开始真正「做事」:自己…...
云原生 Kubernetes 核心概念与组件详解
目录 一、Kubernetes 是什么? 核心功能概览 二、部署演进:从物理机到容器 1. 传统部署时代 2. 虚拟化部署时代 3. 容器部署时代 三、Kubernetes 集群架构 1. 控制平面组件(集群大脑) (1)kube-apise…...
【Portal实战指南】STEP 7 Basic许可证丢失排查与一键修复
1. 问题现象与紧急处理 当你满心欢喜地打开TIA Portal准备开始一天的工作,突然弹出一个令人窒息的提示框:"找不到许可证STEP 7 Basic"。这种情况我遇到过不下十次,每次都能让工程师血压瞬间飙升。别慌,我们先来快速判断…...
Ciao故障排除终极指南:10个常见问题与解决方案大全
Ciao故障排除终极指南:10个常见问题与解决方案大全 【免费下载链接】ciao HTTP checks & tests (private & public) monitoring - check the status of your URL 项目地址: https://gitcode.com/gh_mirrors/ci/ciao Ciao是一款强大的HTTP(S) URL监控…...
告别乱码!手把手教你用LvglFontTool v0.4为LVGL 8.x生成精简中文字库
嵌入式UI开发实战:用LvglFontTool v0.4打造极简中文字库 在嵌入式UI开发中,中文显示一直是开发者面临的挑战之一。尤其是当项目采用LVGL这样的轻量级图形库时,如何在有限的ROM空间内实现清晰、稳定的中文显示,成为许多开发者头疼的…...
Linux I2C设备驱动避坑指南:以MPU6050为例,解决i2c_transfer返回EIO错误
Linux I2C设备驱动深度排障:MPU6050的EIO错误全解析 调试嵌入式设备时,最令人沮丧的莫过于那些间歇性出现的错误。它们像幽灵一样时隐时现,让开发者陷入无尽的猜测和试错循环。MPU6050作为一款广泛使用的运动传感器,其I2C接口的稳…...
自研系统与Odoo ERP数据集成中间件设计与实现
1. 项目概述:连接两个世界的桥梁最近在折腾企业信息化系统集成时,遇到了一个挺典型的场景:公司内部有一套自研的、基于特定业务逻辑的微服务应用(我们内部戏称为“雾系统”),同时又在使用Odoo这套成熟的ERP…...
军用270V电源系统设计与模块化解决方案
1. 军用270V电源系统的核心挑战在军用电子设备领域,270V直流电源系统已成为现代战机、舰载设备和地面作战系统的标准配置。作为一名在军工电源领域工作十余年的工程师,我深刻理解这类系统设计面临的独特挑战。军用环境对电源的要求远高于商业应用&#x…...
