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

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第五题思路代码第六题思路代码第七题思路代码这里介绍双指针在数组中的第二类题型&#xff1a;两端夹击。 第五题 977. 有序数组的平方 题目描述&#xff1a; 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的…...

线性杂双功能peg化试剂——HS-PEG-COOH,Thiol-PEG-Acid

英文名称&#xff1a;HS-PEG-COOH&#xff0c;Thiol-PEG-Acid 中文名称&#xff1a;巯基-聚乙二醇-羧基 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&#xff08;57&#xff09; 3.2.6 运行web项目 3.2.7 安装tomcat 三、 …...

SpringBoot07:SpringSecurity

Security是什么&#xff1f; 是一个安全框架。可以用来做认证和授权 官网&#xff1a;Spring Security SpringSecurity环境搭建 1、创建一个新的project 2、导入thymeleaf依赖 <dependency><groupId>org.thymeleaf</groupId><artifactId>thymeleaf…...

C++ 浅谈之 STL Vector

C 浅谈之 STL Vector HELLO&#xff0c;各位博友好&#xff0c;我是阿呆 &#x1f648;&#x1f648;&#x1f648; 这里是 C 浅谈系列&#xff0c;收录在专栏 C 语言中 &#x1f61c;&#x1f61c;&#x1f61c; 本系列阿呆将记录一些 C 语言重要的语法特性 &#x1f3c3;&…...

【个人作品】非侵入式智能开关

一、产品简介 一款可以通过网络实现语音、APP、小程序控制&#xff0c;实现模拟手动操作各种开关的非侵入式智能开关作品。 非侵入式&#xff0c;指的是不需要对现有的电路和开关做任何改动&#xff0c;只需要将此设备使用魔术无痕胶带固定在旁边即可。 以下为 ABS 材质的渲…...

数据存储技术复习(三)未完

module4智能存储系统是功能丰富且可提供高度优化的I/o处理能力的RAID阵列。请绘制智能存储系统架构&#xff0c;并说明其各个关键组件的主要功能。前端缓存后端物理磁盘2&#xff0e;智能存储系统中&#xff0c;使用缓存进行的写入操作与直接写入到磁盘相比&#xff0c;可以带来…...

ThinkPHP数据库迁移工具

安装 composer require topthink/think-migration 创建迁移工具文件 //执行命令,创建一个操作文件,一定要用大驼峰写法,如下 php think migrate:create AnyClassNameYouWant //执行完成后,会在项目根目录多一个database目录,这里面存放类库操作文件 //文件名类似/database/m…...

代理模式(Proxy Pattern)

代理模式定义&#xff1a; 提供了对目标对象另外的访问方式&#xff1b;即通过代理对象访问目标对象。举个例子&#xff1a;猪八戒去找高翠兰结果是孙悟空变的&#xff0c;可以这样理解&#xff1a;把高翠兰的外貌抽象出来&#xff0c;高翠兰和孙悟空都实现了这个接口&#xff…...

Elasticesearch内存详解

1.ES基本概念 为了更好的理解内存,我们先看一下ES的基本概念。 1.1 cluster 集群 多个节点组合在一起就形成了一个集群,在每个ES节点中,我们可以通过配置集群的名称来使各个节点组合在一起,成为一个集群。当某些节点的集群名称一样,ES会自动根据配置文件中的地址找到这些…...

SpringCloud之断路器聚合监控

一、Hystrix Turbine简介 看单个的Hystrix Dashboard的数据并没有什么多大的价值&#xff0c;要想看这个系统的Hystrix Dashboard数据就需要用到Hystrix Turbine。Hystrix Turbine将每个服务Hystrix Dashboard数据进行了整合。Hystrix Turbine的使用非常简单&#xff0c;只需要…...

凭借这份《2022测试八股文》候选者逆袭面试官,offer拿到手软

《2023测试面试八股文》800 道软件测试面试真题&#xff0c;高清打印版打包带走&#xff0c;横扫软件测试面试高频问题&#xff0c;涵盖测试理论、Linux、MySQL、Web 测试、接口测试、App 测试、Python、Selenium、性能测试、LordRunner、计算机网络、数据结构与算法、逻辑思维…...

【i2c协议介绍】

文章目录协议简单介绍五种速度模式master/slave和transmitter/receiver关系第一种情况&#xff1a;master作为transmitter&#xff0c;slave作为receiver第二种情况&#xff1a;当master作为receiver&#xff0c;slave作为transmitteri2c基本信号start产生stop信号数据传输有效…...

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers &#xff0c;该数组已按 非递减顺序排列 &#xff0c;请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] &#xff0c;则 1 < index1 < index2 < numbers…...

编译与链接------《程序员的自我修养》

本篇整理于《程序员的自我修养》一书中编译与链接相关知识&#xff0c;整理的目的是为了更加深入的了解编译于链接的更多底层知识&#xff0c;面对程序运行时种种性能瓶颈我们束手无策。我们看到的是这些问题的现象,但是却很难看清本质&#xff0c;所有这些问题的本质就是软件运…...

5分钟搞懂 强缓存与协商缓存

Ⅰ、http缓存 HTTP 缓存策略 分为 > 「强制缓存」 和 「协商缓存」 为什么需要 HTTP 缓存 呢 ? &#x1f447; 直接使用缓存速度 >> 远比重新请求快 缓存对象有那些呢 &#xff1f;&#x1f447; 「图片」 「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启动过程 参考文献&#xff1a; startActivity启动过程分析 Activity启动流程(Android 12) 概述 Activity启动发起后&#xff0c;是通过Binder最终交由system进程中的AMS来完成。 一、启动流程 frameworks/base/core/java/android/app/Activity.java f…...

VCS®/VCSi™User Guide

VCS是一种高性能、高容量的Verilog模拟器&#xff0c;它将先进的高级抽象验证技术集成到一个开放的本地平台中。VCS是一个编译代码模拟器。它使您能够分析、编译和模拟Verilog、SystemVerilog、OpenVera和SystemC设计描述。它还为您提供了一组模拟和调试功能&#xff0c;以验证…...

MongoDB简介及SpringBoot整合

一、概述MongoDB中的记录是一个文档&#xff0c;它是一个数据结构组成 字段和值对。MongoDB文档类似于JSON。对象。字段的值可能包括其他文档、数组、 和文档数组&#xff1a;数据库&#xff08;Database&#xff09;&#xff1a;和关系型数据库一样&#xff0c;每个数据库中有…...

BetterRTX终极指南:三步免费提升Minecraft画质的完整方案

BetterRTX终极指南&#xff1a;三步免费提升Minecraft画质的完整方案 【免费下载链接】BetterRTX-Installer The Powershell Installer for BetterRTX! BetterRTX is a Ray-Tracing mod for Minecraft Bedrock. 项目地址: https://gitcode.com/gh_mirrors/be/BetterRTX-Insta…...

第57篇:Vibe Coding时代:LangGraph + 代码所有者规则实战,解决 Agent 修改核心模块无人负责的问题

第57篇:Vibe Coding时代:LangGraph + 代码所有者规则实战,解决 Agent 修改核心模块无人负责的问题 一、问题场景:Agent 修改了核心文件,但没有找到该找谁审 在团队项目中,不同模块通常有不同负责人: auth 模块:安全团队 payment 模块:支付团队 database 模块:平台团…...

Android本地AI智能家居框架:ZeroClaw架构设计与工程实践

1. 项目缘起与核心愿景几年前&#xff0c;我还在为一个智能家居项目焦头烂额&#xff0c;试图让家里的灯光、空调和音箱能听懂人话&#xff0c;而不是只会执行预设的“回家模式”或“睡眠模式”。当时市面上主流的方案&#xff0c;要么是依赖某个封闭的云平台&#xff0c;所有指…...

Chlorophyll印相稀缺资源包泄露!含19世纪银盐配方数字化映射表、327张原生植物扫描底片及MJ v6.2专用--style raw参数集(限今日领取)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Chlorophyll印相的技术起源与美学范式 Chlorophyll印相&#xff08;叶绿素印相&#xff09;并非传统摄影术的延伸&#xff0c;而是一种融合植物生物化学、光敏反应与数字图像处理的跨媒介实践。其技术雏…...

从“鸡尾酒会”到手机通话:用生活场景图解CDMA码分多址到底是怎么“听清”你的

鸡尾酒会里的通信密码&#xff1a;用生活场景拆解CDMA如何从噪音中识别你的声音 1. 当鸡尾酒会遇见通信技术 想象你站在一个嘈杂的鸡尾酒会现场&#xff0c;四周充斥着数十人同时进行的对话。神奇的是&#xff0c;尽管声波在空气中混杂叠加&#xff0c;你的大脑却能自动过滤无关…...

5分钟搞定专业神经网络图:Draw.io开源模板库终极指南

5分钟搞定专业神经网络图&#xff1a;Draw.io开源模板库终极指南 【免费下载链接】Neural-Network-Architecture-Diagrams Diagrams for visualizing neural network architecture 项目地址: https://gitcode.com/gh_mirrors/ne/Neural-Network-Architecture-Diagrams 你…...

大核小核架构的演进:从DVFS到异构计算,应对先进制程挑战

1. 项目概述&#xff1a;大核小核架构的十字路口在移动计算和嵌入式领域&#xff0c;ARM的“大核小核”&#xff08;big.LITTLE&#xff09;架构在过去十年里几乎成了高性能低功耗的代名词。从智能手机到平板电脑&#xff0c;再到如今的物联网边缘设备&#xff0c;这套将高性能…...

别再让专利证书变废纸!手把手教你用6步法写出能维权的权利要求书

从技术到法律&#xff1a;6步打造高价值专利权利要求的实战指南 刚拿到专利证书的工程师小王&#xff0c;在展会上发现竞争对手的产品几乎照搬了自己的发明。他信心满满地提起诉讼&#xff0c;却因权利要求书中"数据传输模块"的表述过于宽泛而败诉——法院认为该描述…...

告别LSMW!SAP S/4HANA数据迁移新宠:手把手激活Migration Cockpit (LTMC/LTMOM)服务

SAP S/4HANA数据迁移革命&#xff1a;Migration Cockpit全流程实战指南 在SAP生态系统中&#xff0c;数据迁移一直是项目实施过程中最关键的环节之一。传统LSMW工具虽然功能强大&#xff0c;但随着S/4HANA的推出&#xff0c;其局限性日益凸显。本文将带您深入探索SAP官方推荐的…...

STM32+EMMC+GL3227E固件调试:从扇区偏移到数据同步的实战解析

1. 问题现象与背景分析 最近在调试一个嵌入式存储系统时遇到了奇怪的现象&#xff1a;STM32主控将数据写入EMMC存储后&#xff0c;通过GL3227E桥接芯片连接电脑却无法识别。更诡异的是&#xff0c;电脑格式化后的EMMC&#xff0c;STM32写入的数据在电脑端又"消失"了。…...