Leetcode双指针法应用

1.双指针法

文章目录

    • 1.双指针法
      • 1.1什么是双指针法?
      • 1.2解题思路
      • 1.3扩展

1.1什么是双指针法?

双指针算法是一种在数组或序列上操作的技巧,实际上是对暴力枚举算法的一种优化,通常涉及到两个索引(或指针)从两端或从某个特定起点开始向中间靠拢,以解决特定问题。这种算法在处理数组中的元素对、查找、排序和去除重复元素等问题上特别有效。

  • 初始化:设定两个指针,它们可以同时从序列的两端开始,也可以从同一端以不同速度移动。
  • 移动规则:根据问题需求定义指针如何移动。比如,在排序数组中查找一对数之和,一个指针可以从左向右移动,另一个从右向左移动,直到两者相遇。
  • 终止条件:当指针相遇、错过彼此或是达到某种特定条件时,算法结束。

典型应用场景:

  1. 查找问题

    • 在排序数组中查找目标对:给定一个排序数组和一个目标值,找到两个数,使它们的和为目标值。如 LeetCode 的 “Two Sum II - Input array is sorted” 问题。
  2. 删除问题

    • 移除数组中的重复元素:例如,给定一个排序数组,原地删除重复出现的元素,使得每个元素最多出现两次。双指针一个用来遍历,另一个用来记录新的非重复元素的位置。
  3. 排序与翻转

    • 反转数组:可以使用双指针快速地原地反转数组的一部分或全部。两个指针一前一后交换元素直至相遇。
  4. 滑动窗口

    • 最大/最小滑动窗口:维护一个大小固定的窗口,在数组上滑动以找到窗口内的最大值或最小值,或某些统计量,如窗口内的最大和。

1.2解题思路

题目原文:

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

示例 2:

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

思路:

对于这个问题,双指针算法可以非常高效地解决。由于原始数组是非递减排序的,我们可以通过双指针从数组两端开始向中间遍历,比较两个指针所指向元素的平方值,将较大的平方值先放入结果数组中。这样可以确保结果数组始终是按非递减顺序排列的。

  1. 初始化两个指针,left指向数组的起始位置,right指向数组的末尾位置。
  2. 初始化一个空数组或列表来存放结果。
  3. left <= right时,执行以下步骤:
    • 计算leftright指针所指向元素的平方值。
    • 比较这两个平方值,将较大的那个平方值添加到结果数组的前端。
    • 移动指向较小原数值的指针。如果平方值相等,可以任选一个指针移动。
  4. left > right时,所有元素都已经处理完毕,返回结果数组。

通过这种方法,我们可以在一次遍历中完成所有计算和排序工作,时间复杂度为O(n),空间复杂度也为O(n),其中n为数组的长度。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int>result(nums.size(),0);int left = 0;int right = nums.size() - 1;int k =  nums.size() - 1;while(left <= right){if(nums[left]*nums[left] < nums[right]*nums[right]){result[k--] = nums[right]*nums[right];right--;}else{result[k--] = nums[left]*nums[left];left++;}}return result;}
};

在这里插入图片描述

1.3扩展

题目原文:

给你两个按 非递减顺序 排列的整数数组 nums1nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 nums2nums1 中,使合并后的数组同样按 非递减顺序 排列。

**注意:**最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

思路:

双指针解题思路在这种合并有序数组的问题中非常有效。这里的关键是利用两个数组已经是非递减顺序的特点,通过两个指针分别从两个数组的末尾开始比较,并将较大的数逆序填入nums1的末尾
解题步骤:

  1. 初始化两个指针 ij,分别指向 nums1nums2 的末尾,即 i = m - 1j = n - 1。同时,设置另一个指针 k 指向 nums1 数组的最后一个有效位置,即 k = m + n - 1

  2. i >= 0j >= 0 时,进行以下操作:

    • 比较 nums1[i]nums2[j] 的值。
    • 将较大的数赋值给 nums1[k],然后对应的指针向前移动一位。如果 nums1[i] 大,则 i--;如果 nums2[j] 大或相等,则 j--
    • k--,因为每次操作都是在数组的末尾进行的。
  3. 如果 j >= 0,说明 nums2 中还有剩余元素,直接将剩余的 nums2[j] 逐个复制到 nums1 的前面,因为 nums2 的元素在 nums1 的末尾已经被正确地放置了。

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> arr(m + n, 0); // 创建一个足够大的临时数组int k = m + n - 1; // 初始化k为新数组的最后一个位置索引m--; // nums1的有效元素索引需要减1,因为m是原始长度n--; // nums2的同理// 注意循环条件应该是 k >= 0,因为我们要从末尾开始填充while (k >= 0) {if (n < 0) { // 如果nums2已经全部处理完了arr[k] = nums1[m];m--;} else if (m < 0) { // 如果nums1已经全部处理完了arr[k] = nums2[n];n--;} else if (nums1[m] > nums2[n]) { // 比较条件arr[k] = nums1[m];m--;} else {arr[k] = nums2[n];n--;}k--; // 移动到下一个待填充的位置}// 最后把合并的结果复制回nums1nums1.swap(arr);}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/380052.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【D3.js in Action 3 精译_020】2.6 用 D3 设置与修改元素样式 + 名人专访(Nadieh Bremer)+ 2.7 本章小结

当前内容所在位置 第一部分 D3.js 基础知识 第一章 D3.js 简介&#xff08;已完结&#xff09; 1.1 何为 D3.js&#xff1f;1.2 D3 生态系统——入门须知1.3 数据可视化最佳实践&#xff08;上&#xff09;1.3 数据可视化最佳实践&#xff08;下&#xff09;1.4 本章小结 第二章…

Chromium CI/CD 之Jenkins实用指南2024-在Windows节点上创建任务(九)

1. 引言 在现代软件开发流程中&#xff0c;持续集成&#xff08;CI&#xff09;和持续交付&#xff08;CD&#xff09;已成为确保代码质量和加速发布周期的关键实践。Jenkins作为一款广泛应用的开源自动化服务器&#xff0c;通过其强大的插件生态系统和灵活的配置选项&#xf…

Spring Boot项目中使用MyBatis Generator (MBG) 自动生成Mapper文件

Spring Boot项目中使用MyBatis Generator (MBG) 自动生成Mapper文件可以很大程度上减少编码。本文着重介绍如何在实战中使用MGB自动生成Mapper文件 1. 添加MyBatis Generator依赖 在pom.xml中添加必要的依赖 <dependency><groupId>org.mybatis.spring.boot</…

如何在Linux上部署Ruby on Rails应用程序

在Linux上部署Ruby on Rails应用程序是一个相对复杂的过程&#xff0c;需要按照一系列步骤进行。下面是一个基本的部署过程&#xff0c;涵盖了从安装所需软件到部署应用程序的所有步骤。 安装必要的软件 在部署Ruby on Rails应用程序之前&#xff0c;需要确保Linux系统上安装了…

【LeetCode】day15:110 - 平衡二叉树, 257 - 二叉树的所有路径, 404 - 左叶子之和, 222 - 完全二叉树的节点个数

LeetCode 代码随想录跟练 Day15 110.平衡二叉树257.二叉树的所有路径404.左叶子之和222.完全二叉树的节点个数 110.平衡二叉树 题目描述&#xff1a; 给定一个二叉树&#xff0c;判断它是否是 平衡二叉树 平衡二叉树的定义是&#xff0c;对于树中的每个节点&#xff0c;其左右…

三、初识C语言(3)

1.操作符 &#xff08;1&#xff09;算术操作符 - * / % 商 余&#xff08;取模&#xff09; 小算法&#xff1a; 若a<b&#xff0c;则a%b a 若a%b c&#xff0c;则0 < c < b-1 若两个int 类型数相除&#xff0c;结果有小数会被舍弃。 保留小数…

阿里云 申请免费ssl 证书

1控制台--数字证书管理服务 2 创建所需域名证书

下载安装VSCode并添加插件作为仓颉编程入门编辑器

VSCode下载地址&#xff1a;下载 Visual Studio Code - Mac、Linux、Windows 插件下载&#xff1a;GitCode - 全球开发者的开源社区,开源代码托管平台 仓颉社区中下载解压 cangjie.vsix 插件 打开VSCode 按 Ctrl Shift X 弹出下图 按照上图步骤依次点击选中我们下…

openstack设置IP直接登录,不需要加dashboard后缀

openstack 实验环境&#xff0c;openstack-t版&#xff0c;centos2009 修改配置文件 [rootcontroller ~]# vim /WEBROOT /etc/openstack-dashboard/local_settings #将dashboard去掉 WEBROOT /dashboard/ #改为 WEBROOT /[rootcontroller ~]# vim /etc/httpd/conf.d/openst…

vscode搭建PyQt + Quick开发环境

VScode搭建PyQt Quick开发环境 目录 环境准备 &#x1f514;安装必要的Python包 &#x1f514;&#x1f50e; PyQt5和PySide2的区别&#x1f4be; 安装PyQt5&#x1f4be; 安装PySide2 配置VScode &#x1f514;&#x1f4bb; 安装扩展 代码示例 &#x1f514;✔ Python调用Qt…

分布式 I/O 系统Modbus TCP 耦合器BL200

BL200 耦合器是一个数据采集和控制系统&#xff0c;基于强大的 32 位微处理器设计&#xff0c;采用 Linux 操作系统&#xff0c;可以快速接入现场 PLC、SCADA 以及 ERP 系统&#xff0c; 内置逻辑控制、边缘计算应用&#xff0c;支持标准 Modbus TCP 服务器通讯&#xff0c;以太…

光耦合器技术的实际应用

光耦合器也称为光隔离器&#xff0c;是现代电子产品中的关键组件&#xff0c;可确保电路不同部分之间的信号完整性和隔离。它们使用光来传输电信号&#xff0c;提供电气隔离和抗噪性。 结构和功能 光耦合器通常由以下部分组成&#xff1a; 1.LED&#xff08;发光二极管&#…

pytorch学习(七)torchvision.datasets的使用

网络上已经有公开的数据集&#xff0c;并且这些数据集被整合到了torchvision.datasets中&#xff0c;使用自带的函数可以直接下载。 1.数据集 具体有哪些数据可直接用torchvision.datasets加载呢&#xff1f;可以查看这个网址&#xff1a; datasets官网&#xff1a;Datasets…

二叉树基础及实现(一)

目录&#xff1a; 一. 树的基本概念 二. 二叉树概念及特性 三. 二叉树的基本操作 一. 树的基本概念&#xff1a; 1 概念 &#xff1a; 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0 &#xff09;个有限结点组成一个具有层次关系的集合。 把它叫做树是因…

debian 更新源

前言 实现一键替换在线源 一键更新源 Debian 全球镜像站以下支持现有debian 11 12 echo "Delete the default source" rm -rf /etc/apt/sources.listecho "Build a new source" cat <<EOF>>/etc/apt/sources.list.d/debian.sources Types:…

将iPad 作为Windows电脑副屏的几种方法(二)

将iPad 作为Windows电脑副屏的几种方法&#xff08;二&#xff09; 1. 前言2. EV 扩展屏2.1 概述2.2 下载、安装、连接教程2.3 遇到的问题和解决方法2.3.1 平板连接不上电脑 3. Twomon SE3.1 概述3.2 下载安装教程 4. 多屏中心&#xff08;GlideX&#xff09;4.1 概述4.2 下载安…

pdf怎么压缩的小一点?PDF压缩变小的6种方法(2024全新)

pdf怎么压缩的小一点&#xff1f;首先&#xff0c;PDF文件可以进行压缩。职场文档传阅还是比较建议PDF压缩&#xff0c;PDF文件可以无障碍访问&#xff0c;保持原始文本、图像和表格&#xff0c;无需担心展示效果差异等等优势&#xff0c;成为我们日常工作中不可或缺的一部分。…

AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理

AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理 目录 AGI 之 【Hugging Face】 的【零样本和少样本学习】之三 [无标注数据] 的简单整理 一、简单介绍 二、零样本学习 (Zero-shot Learning) 和少样本学习 (Few-shot Learning) 1、零样本学…

MF173:将多个工作表转换成PDF文件

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

python多幅图自适应紧致二维排放

有时可视化会要同时放多幅图&#xff0c;如分割的原图、label、pseudo-label 和 prediction。当图很多&#xff0c;简单地排成一行可能会太长&#xff0c;不便观看。考虑将图排成二维网格&#xff08;grid&#xff09;展示&#xff0c;且为方便看&#xff0c;考虑让网格尽可能「…