备战蓝桥杯————双指针技巧巧解数组2

2024-02-24 08:44

本文主要是介绍备战蓝桥杯————双指针技巧巧解数组2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

利用双指针技巧来解决七道与数组相关的题目。

  1. 两数之和 II - 输入有序数组: 给定一个按升序排列的数组,找到两个数使它们的和等于目标值。可以使用双指针技巧,在数组两端设置左右指针,根据两数之和与目标值的大小关系移动指针。

  2. 删除有序数组中的重复项: 给定一个有序数组,原地删除重复出现的元素,使每个元素只出现一次,并返回新的长度。利用双指针技巧,一个指针用于遍历数组,另一个指针指向新数组的末尾。

  3. 移除元素: 给定一个数组和一个值,原地移除数组中所有等于该值的元素,返回新数组的长度。同样利用双指针技巧,一个指针用于遍历数组,另一个指针用于记录非目标值的位置。

  4. 移动零: 给定一个数组,将所有的 0 移动到数组的末尾,同时保持非零元素的相对顺序。使用双指针技巧,一个指针遍历数组,另一个指针记录非零元素的位置,并将非零元素依次移到前面。

  5. 反转字符串: 反转给定的字符串。利用双指针技巧,一个指针从数组的开头向后移动,另一个指针从数组的末尾向前移动,依次交换两个指针指向的元素。

  6. 最长回文子串: 找到给定字符串中的最长回文子串。作者通过介绍中心扩散法,结合双指针技巧,在遍历过程中寻找回文子串的中心点。

  7. 删除排序链表中的重复元素: 删除排序链表中重复的元素,使得每个元素只出现一次。使用双指针技巧,一个指针遍历链表,另一个指针负责删除重复元素

一、移除零

问题描述

        给定一个数组 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

解题思路及代码

  • 使用快慢指针技巧,将慢指针 slow 指向数组中的第一个元素,将快指针 fast 指向数组中的第一个元素。
  • 开始遍历数组,如果 nums[fast] == 0,说明遇到了目标元素,快指针 fast 继续向前移动,直到找到一个不是目标的元素。
  • 将这个元素复制到慢指针 slow 的位置,然后慢指针 slow 前进一步。
  • 重复上述步骤,直到快指针 fast 遍历完整个数组。
  • 最终,慢指针 slow 之前的部分就是去除目标元素后的数组,返回慢指针的位置加一即可得到去重后的数组长度。
class Solution {public void moveZeroes(int[] nums) {int l=0,r=0;while(r<nums.length){if(nums[r]!=0){int temp=nums[l];nums[l]=nums[r];nums[r]=temp;l++;}r++;}}
}

结果展示

二、移除元素

题目描述

        给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}

示例 1:

输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例 2:

输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

解题思路及代码

  • 使用快慢指针技巧,将慢指针 slow 指向数组中的第一个元素,将快指针 fast 指向数组中的第一个元素。
  • 开始遍历数组,如果 nums[fast] == target,说明遇到了目标元素,快指针 fast 继续向前移动,直到找到一个不是目标的元素。
  • 将这个元素复制到慢指针 slow 的位置,然后慢指针 slow 前进一步。
  • 重复上述步骤,直到快指针 fast 遍历完整个数组。
  • 最终,慢指针 slow 之前的部分就是去除目标元素后的数组,返回慢指针的位置加一即可得到去重后的数组长度。

这种方法的时间复杂度为 O(N),其中 N 为数组的长度,因为每个元素最多只被遍历一次。这样的算法实现既节省了空间,又能高效地实现原地删除重复元素

class Solution {public int removeElement(int[] nums, int val) {int l=0,r=0;if(nums.length==0)return 0;while(r<nums.length){if(nums[r]!=val){nums[l]=nums[r];l++;}r++;}return l;}
}

结果展示

这篇关于备战蓝桥杯————双指针技巧巧解数组2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/741582

相关文章

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

电脑报错cxcore100.dll丢失怎么办? 多种免费修复缺失的cxcore100.dll文件的技巧

《电脑报错cxcore100.dll丢失怎么办?多种免费修复缺失的cxcore100.dll文件的技巧》你是否也遇到过“由于找不到cxcore100.dll,无法继续执行代码,重新安装程序可能会解... 当电脑报错“cxcore100.dll未找到”时,这通常意味着系统无法找到或加载这编程个必要的动态链接库

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

如何关闭 Mac 触发角功能或设置修饰键? mac电脑防止误触设置技巧

《如何关闭Mac触发角功能或设置修饰键?mac电脑防止误触设置技巧》从Windows换到iOS大半年来,触发角是我觉得值得吹爆的MacBook效率神器,成为一大说服理由,下面我们就来看看mac电... MAC 的「触发角」功能虽然提高了效率,但过于灵敏也让不少用户感到头疼。特别是在关键时刻,一不小心就可能触

前端bug调试的方法技巧及常见错误

《前端bug调试的方法技巧及常见错误》:本文主要介绍编程中常见的报错和Bug,以及调试的重要性,调试的基本流程是通过缩小范围来定位问题,并给出了推测法、删除代码法、console调试和debugg... 目录调试基本流程调试方法排查bug的两大技巧如何看控制台报错前端常见错误取值调用报错资源引入错误解析错误

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常

Apache伪静态(Rewrite).htaccess文件详解与配置技巧

《Apache伪静态(Rewrite).htaccess文件详解与配置技巧》Apache伪静态(Rewrite).htaccess是一个纯文本文件,它里面存放着Apache服务器配置相关的指令,主要的... 一、.htAccess的基本作用.htaccess是一个纯文本文件,它里面存放着Apache服务器

Spring中@Lazy注解的使用技巧与实例解析

《Spring中@Lazy注解的使用技巧与实例解析》@Lazy注解在Spring框架中用于延迟Bean的初始化,优化应用启动性能,它不仅适用于@Bean和@Component,还可以用于注入点,通过将... 目录一、@Lazy注解的作用(一)延迟Bean的初始化(二)与@Autowired结合使用二、实例解