备战蓝桥杯————双指针技巧巧解数组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

相关文章

快速修复一个Panic的Linux内核的技巧

《快速修复一个Panic的Linux内核的技巧》Linux系统中运行了不当的mkinitcpio操作导致内核文件不能正常工作,重启的时候,内核启动中止于Panic状态,该怎么解决这个问题呢?下面我们就... 感谢China编程(www.chinasem.cn)网友 鸢一雨音 的投稿写这篇文章是有原因的。为了配置完

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Java Optional的使用技巧与最佳实践

《JavaOptional的使用技巧与最佳实践》在Java中,Optional是用于优雅处理null的容器类,其核心目标是显式提醒开发者处理空值场景,避免NullPointerExce... 目录一、Optional 的核心用途二、使用技巧与最佳实践三、常见误区与反模式四、替代方案与扩展五、总结在 Java

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

Java Optional避免空指针异常的实现

《JavaOptional避免空指针异常的实现》空指针异常一直是困扰开发者的常见问题之一,本文主要介绍了JavaOptional避免空指针异常的实现,帮助开发者编写更健壮、可读性更高的代码,减少因... 目录一、Optional 概述二、Optional 的创建三、Optional 的常用方法四、Optio

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.