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

leetcode100----双指针

283. 移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶:你能尽量减少完成的操作次数吗?

class Solution {
public void moveZeroes(int[] nums) {int n = nums.length;int slow = 0;int fast = 0;// 将非零元素前移while (fast < n) {if (nums[fast] != 0) {nums[slow] = nums[fast];slow++;}fast++;}// 将剩余元素置为零while (slow < n) {nums[slow] = 0;slow++;}
}}

思路:快慢指针

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

在这里插入图片描述

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:输入:height = [1,1]
输出:1

提示:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

class Solution {
public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int maxArea = 0;while (left < right) {int area = Math.min(height[left], height[right]) * (right - left);maxArea = Math.max(maxArea, area);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}
}

思路:双指针法:头尾指针,每次短的一端往中间靠近,(因为短的一端到另外一端已经是最大容量)

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1][-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0

要解决这个问题,可以使用双指针的方法来找到和为0的三元组。首先,对数组进行排序,然后固定一个数,使用双指针在剩余的区间内查找另外两个数,使得三个数的和为0。

以下是解决该问题的具体步骤:

1、对数组进行排序,以便于后续双指针的操作。

2、遍历排序后的数组,固定第一个数 nums[i]:

  • 若 nums[i] > 0,则说明后面的数都大于0,不可能存在和为0的三元组,直接返回结果。
  • 若 i > 0 且 nums[i] == nums[i-1],则说明当前数与前一个数相同,为了避免重复的三元组,跳过当前数。

3、使用双指针解决剩下的两数之和问题:

  • 初始化左指针 left 为 i+1,右指针 right 为数组末尾索引。
  • 在 left < right 的条件下,执行以下操作:
    • 计算三个数的和 sum = nums[i] + nums[left] + nums[right]。
    • 若 sum == 0,则将三个数加入结果列表中,并移动指针 left 和 right,同时跳过重复的元素。
    • 若 sum > 0,则说明右指针指向的数较大,需要将右指针向左移动。
    • 若 sum < 0,则说明左指针指向的数较小,需要将左指针向右移动。

4、返回结果列表。

public class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();int n = nums.length;Arrays.sort(nums);for (int i = 0; i < n; i++) {if (nums[i] > 0) {break;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;int right = n - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳过重复的元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;} else if (sum > 0) {right--;} else {left++;}}}return result;}
}

思路:定一移二

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

在这里插入图片描述

输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 
示例 2:输入:height = [4,2,0,3,2,5]
输出:9

提示:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

public class Solution {public int trap(int[] height) {int left = 0;int right = height.length - 1;int maxLeft = 0;int maxRight = 0;int result = 0;while (left <= right) {if (height[left] <= height[right]) {if (height[left] >= maxLeft) {maxLeft = height[left];} else {result += maxLeft - height[left];}left++;} else {if (height[right] >= maxRight) {maxRight = height[right];} else {result += maxRight - height[right];}right--;}}return result;}
}

在这里插入图片描述

相关文章:

leetcode100----双指针

283. 移动零 给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 1:输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2:输入: nums …...

ORM基本操作

ORM基本操作 基本操作包括增删改查操作&#xff0c;即(CRUD操作) CRUD是指在做计算处理时的增加(Create)、读取查询(Read)、更新Update)和删除(Delete) ORM CRUD 核心-> 模型类管理器对象 每个继承自 models.Model 的模型类&#xff0c;都会有一个 objects 对象被同样继…...

c语言进阶部分详解(指针进阶2)

大家好&#xff01;我快马加鞭接着写出指针部分part2部分。第一部分见&#xff1a;c语言进阶部分详解&#xff08;指针进阶1&#xff09;_总之就是非常唔姆的博客-CSDN博客 指针初阶部分见&#xff1a;c语言进阶部分详解&#xff08;指针初阶&#xff09;_总之就是非常唔姆的博…...

Java基础(一)——Hello World,8种数据类型,键盘录入

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…...

JAVA学习笔记(IF判断结构)

/*** 学习JAVA单分支结构* 掷骰子游戏* 1.如果三个随机数的和大于15&#xff0c;则手气不错&#xff1b;* 2.如果三个随机数的和在10-15之间&#xff0c;手气一般&#xff1b;* 3.如果三个随机数的和1在0以下&#xff0c;手气不太好。*/public class TestIf01 {public static v…...

【跟小嘉学 PHP 程序设计】二、PHP 基本语法

系列文章目录 【跟小嘉学 PHP 程序设计】一、PHP 开发环境搭建 【跟小嘉学 PHP 程序设计】二、PHP 基本语法 文章目录 系列文章目录@[TOC](文章目录)前言一、PHP基本语法1.1、hello,world1.2、PHP语法的其他形式1.2.1、简短形式(了解即可)1.2.2、Script 风格1.2.3、ASP 风格1…...

面试总结之微服务篇

一、概览 1、微服务常用组件 微服务给系统开发带来了诸多问题和挑战&#xff0c;如服务间通信和调用的复杂性、数据一致性和事务管理、服务治理和版本管理等&#xff0c;为解决应对这些问题和挑战&#xff0c;各种微服务组件应运而生微服务的常见组件和实现&#xff1a; 1…...

ElementUI之登陆+注册

一.什么是ElementUI 二.ElementUI完成用户注册登录界面搭建 使用命令npm install element-ui -S&#xff0c;添加Element-UI模块 导依赖 建立登录和注册页面 ​编辑 配置样式 编写登录页面&#xff08;Login&#xff09; 编写注册页面&#xff08;reginter&#xff09; …...

新版kafka可视化界面组件

二、安装kafka可视化客户端工具&#xff08;kafka tool 2&#xff09; 1、下载安装 在官网中找到对应自己电脑系统的版本&#xff1a; kafka Tool2官网下载地址&#xff1a; Offset Explorer 这个方案是为Kafka依赖zookeeper提供的可视化解决方案。 前言 在早期使用kafka的…...

​P1102 A-B 数对 【双指针(尺取法)】​

P1102 A-B 数对 【双指针&#xff08;尺取法&#xff09;】 题目描述 给出一串正整数数列以及一个正整数 C&#xff0c;要求计算出所有满足 A−BC 的数对的个数&#xff08;不同位置的数字一样的数对算不同的数对&#xff09;。 输入格式 输入共两行。 第一行&#xff0c;两个…...

Flutter绘制拖尾效果

演示&#xff1a; 代码&#xff1a; import dart:ui;import package:flutter/material.dart; import package:kq_flutter_widgets/widgets/chart/ex/extension.dart;class TrailingView extends StatelessWidget {const TrailingView({super.key});overrideWidget build(Build…...

【Newman+Jenkins】实施接口自动化测试

一、是什么Newman Newman就是纽曼手机这个经典牌子&#xff0c;哈哈&#xff0c;开玩笑啦。。。别当真&#xff0c;简单地说Newman就是命令行版的Postman&#xff0c;查看官网地址。 Newman可以使用Postman导出的collection文件直接在命令行运行&#xff0c;把Postman界面化运…...

kr 第三阶段(六)C++ 逆向

结构体 结构体对齐 设置结构体对齐值 方法1&#xff1a;在 Visual Studio 中可以在 项目属性 -> 配置属性 -> C/C -> 所有选项 -> 结构体成员对齐 中设置结构体对齐大小。方法2&#xff1a;使用 #pragma pack(对齐值) 来设置&#xff0c;不过要想单独设置一个结…...

医药行业安全生产信息化建设分享

随着科技的快速发展和全球化进程的推进&#xff0c;医药行业作为人类健康和安全的重要组成部分&#xff0c;面临着日益严峻的安全生产挑战。近年来&#xff0c;医药企业对于安全生产的需求越来越强烈&#xff0c;安全生产信息化建设成为了医药行业发展的重要趋势。本文将探讨医…...

C 语言简单入门

C 语言发展历史|标准 1972年&#xff0c;丹尼斯里奇&#xff08;Dennis Ritch&#xff09;和肯汤普逊&#xff08;Ken Tompson&#xff09;在贝尔实验室开发 UNIX 操作系统时基于 B 语言设计出 C 语言。 1987年&#xff0c;布莱恩柯林汉&#xff08;Brian Kernighan&#xff…...

Levels - UE5中的建模相关

一些日常的笔记&#xff1b; 可以使用Shapes面板建立基础模型&#xff1a; 可以在PolyModel中继续细分模型&#xff1a; UE5中的建模有PolyGroups概念&#xff0c;可以在Attributes面板中直接编辑&#xff1a; 使用GrpPnt方式可以直接用笔刷设定新的PolyGroups&#xff0c;这样…...

数据中心与数据仓库的区别

在数字化时代&#xff0c;数据已经成为企业竞争的核心资源&#xff0c;数据处理和数据管理也变得越来越重要。在数据处理方面&#xff0c;数据中台和数据仓库是两种常见的数据处理方式&#xff0c;它们有着不同的特点和适用场景。本文将从技术角度对数据中台和数据仓库的区别进…...

[2023.09.18]: Rust中类型转换在错误处理中的应用解析

随着项目的进展&#xff0c;关于Rust的故事又翻开了新的一页&#xff0c;今天来到了服务器端的开发场景&#xff0c;发现错误处理中的错误类型转换有必要分享一下。 Rust抽象出来了Result<T,E>&#xff0c;T是返回值的类型&#xff0c;E是错误类型。只要函数的返回值的类…...

前端工作日常

机缘 记录和遇到的问题作为记录 收获 收获代码提高和认知 日常 使用js去操作数组或者对象 空闲时间可以多学学基础算法 比如&#xff08;冒泡&#xff0c;倒序&#xff0c;去重&#xff0c;笛卡尔积算法&#xff0c;各种各样的排序方法等等等&#xff09; 正确良好的使用循环…...

C++:C++哪些时候用到const

声明常量&#xff1a;使用const关键字定义一个常量&#xff0c;不允许对其进行更改。例如&#xff1a; const int PI 3.1415926;修饰函数参数&#xff1a;加上const限定符可以确保函数不会修改传入的参数值。例如&#xff1a; void print(const int num) {// num不能在函数内…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

MyBatis中关于缓存的理解

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