Python蓝桥杯训练:基本数据结构 [数组]——双指针法
admin
2024-05-13 06:44:57
0

Python蓝桥杯训练:基本数据结构 [数组]——双指针法

文章目录

  • Python蓝桥杯训练:基本数据结构 [数组]——双指针法
    • 一、力扣上面一些关于数组的题目练习
      • 1、双指针法

本次博客我是通过Notion软件写的,转md文件可能不太美观,大家可以去我的原笔记中查看:Python蓝桥杯训练:基本数据结构 [数组],持续更新中,另外这是我创建的编程学习小组频道,想一起学习的朋友可以一起!!!

一、力扣上面一些关于数组的题目练习

1、双指针法

双指针法介绍:
双指针法(Two Pointers)是一种在数组或链表等数据结构中移动两个指针来查找或遍历特定元素的算法。两个指针分别从首尾开始遍历,根据题目要求不断移动指针来缩小查找范围。
双指针法常用于解决数组或链表中的滑动窗口问题、快慢指针问题、双指针问题等。其时间复杂度通常为O(n),空间复杂度为O(1)。
双指针法常见应用场景如:

  • 双指针法可以很好地解决链表中的快慢指针问题,如找到链表中间节点或倒数第 k 个节点。
  • 双指针法可以很好地解决数组中的滑动窗口问题,如在数组中找到最大/小子数组、最长不重复子串等。
  • 双指针法可以很好地解决回文字符串问题。
  • 题目一:[移除元素](https://leetcode.cn/problems/remove-element/)
📖 给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例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,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示:

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

🤔 这道题考察的是双指针的方法,我们可以通过双指针法而不用进行删除操作解决移除数组中指定元素的问题,具体思路如下:给你一个数组

首先定义两个快慢指针,一个指针 fast 指向当前遍历到的位置,另一个指针 slow 指向新数组的尾部,初始化 fast 和 slow 指针都为0,意思是开始都指向索引为0的位置,定义一个变量size为nums的长度,然后使用while循环进行判断当 fast 指针没有遍历完整个数组时,比对当前的nums[fast] 和 val

  • 如果不等于,把当前的nums[fast] 移动到nums[slow], 并且把 slow 向后移动一位
  • 如果相等,则不做任何操作
  • fast 指针每次遍历结束时,指针向后移动一位

最后 return slow, 返回新数组的长度
这样我们就在原地移除了所有数值等于 val 的元素,时间复杂度为 O(n),空间复杂度为 O(1)。


✍🏻 代码实现:
class Solution:def removeElement(self, nums, val):fast, slow = 0, 0size = len(nums)while fast < size:if nums[fast] != val:nums[slow] = nums[fast]slow += 1fast += 1return slow

也可以这样写:

class Solution:def removeElement(self, nums, val):if not nums:return 0slow = 0for fast in range(len(nums)):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return slow

B站上面卡尔老师对于这道题的思路讲得很不错,在这里推荐大家去看看他的教学视频:

https://www.bilibili.com/video/BV12A4y1Z7LP/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=eae0406d86828f39f6ac3a3b0e8a2a34


  • 题目二:[移动零](https://leetcode.cn/problems/move-zeroes/)
📖 给定一个数组 `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

🤔 本题有个专门的要求:必须在不复制数组的情况下原地对数组进行操作,所以我们可以联想到使用双指针法进行替换操作,上一个题我们是删除元素,将要删除的元素移动到数组最后,跟这个题目思路差不多,具体思路如下:
  1. 创建两个指针 i 和 j,i 指向当前遍历到的元素,j 指向下一个非零元素
  2. 从数组的第一个元素开始遍历
  3. 当 i 指向的元素为0时,将j指向的元素复制到i指向的元素位置,i和j都后移一位。
  4. 如果i指向的元素不是0,i和j都后移一位
  5. 遍历完整个数组后,所有的0都会被移到数组的末尾

我们只需要遍历一遍数组原地操作即可。


✍🏻 代码实现:
class Solution:def moveZeroes(self, nums):i = 0j = 0while j < len(nums):if nums[j] != 0:nums[i] = nums[j]i += 1j += 1while i < len(nums):nums[i] = 0i += 1

🤔 这个题目也可以不使用双指针的方法,可以采用状态转移方程,代码会更简洁一点,具体思路如下:
  1. 创建一个变量 zero,用来记录0的位置
  2. 从数组的第一个元素开始遍历
  3. 如果当前遍历到的元素不是0,就将它与zero位置的元素交换,并将zero位置后移一位
  4. 遍历完整个数组后,所有的0都会被移到数组的末尾

✍🏻 代码实现:
class Solution:def moveZeroes(self, nums):zero = 0  # 记录“0”的位置for i in range(len(nums)):if nums[i] != 0:nums[i], nums[zero] = nums[zero], nums[i]zero += 1

  • 题目三:[删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/)
📖 给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例1:

输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2:

输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示:

1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

🤔 题目的意思就是数组去重,但是我们不能使用集合的方法,所以需要转换思路,我们第一个题目做的就是移除元素,所以实现思路方面也是类似的,由于数组已经排好序,所以可以使用双指针来做,具体思路如下:
  1. 创建两个指针 i 和 j,i 指向当前遍历到的元素,j 指向下一个元素
  2. 从数组的第二个元素开始遍历
  3. 当 j 指向的元素和 i 指向的元素不同时,就将 j 指向的元素赋值给 i+1的位置,i和j都后移一位
  4. 如果j指向的元素和 i 指向的元素相同,j 后移一位
  5. 遍历完整个数组后,所有重复项都会被删除。

这种思路只需要遍历一遍数组,并且是原地操作,不需要额外的空间。


✍🏻 代码实现:
class Solution:def removeDuplicates(self, nums):if not nums:return 0i = 0for j in range(1, len(nums)):if nums[j] != nums[i]:i += 1nums[i] = nums[j]return i + 1

  • 题目四:[有序数组的平方](https://leetcode.cn/problems/squares-of-a-sorted-array/)
📖 给你一个按 **非递减顺序**排序的整数数组 `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]

提示:

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

🤔 这道题也是考察的我们对双指针法的理解和使用,我们使用双指针法,左指针指向最左边,右指针指向最右边。 我们每次比较两个指针指向的数的绝对值的大小,将较大的数的平方放入答案数组中。因为题目要求结果是非递减排序,所以每次将较小的数平方放入答案数组的最右边。具体的解题思路如下:
  1. 创建一个结果数组result,并初始化为0。
  2. 创建三个指针,i,j,k。 i 指向数组最左边,j指向数组最右边,k指向结果数组最右边
  3. 使用while循环,当i小于等于j时循环,比较i指向的数和j指向的数的绝对值的大小。
  4. 如果i指向的数的绝对值大于j指向的数的绝对值,就将i指向的数的平方放入result中,并将i指针后移一位。否则将j指向的数的平方放入result中,并将j指针前移一位。
  5. 最后返回result

这种思路只需要遍历一遍数组,并且是原地操作,不需要额外的空间。


✍🏻 代码实现:
class Solution:def sortedSquares(self, nums):n = len(nums)result = [0] * ni, j = 0, n - 1k = n - 1while i <= j:if abs(nums[i]) > abs(nums[j]):result[k] = nums[i] ** 2i += 1else:result[k] = nums[j] ** 2j -= 1k -= 1return result

也可以这样去写:

class Solution:def sortedSquares(self, nums):reslut = [-1] * len(nums)k = len(nums) - 1i = 0j = len(nums) - 1while i <= j: if nums[i] ** 2 > nums[j] **2:reslut[k] = nums[i] ** 2i += 1else:reslut[k] = nums[j] ** 2j -= 1k -= 1return reslut

⚠️ 在使用双指针法解决数组问题时,需要注意以下几点:
  1. 了解题目要求,判断是否适用双指针法。
  2. 确定指针的初始位置和移动规则。
  3. 注意每次移动指针时的边界条件。
  4. 注意在循环中进行的比较和赋值操作。
  5. 注意结果数组的初始化和最终返回结果。
  6. 注意空间复杂度,尽量使用原地算法。
  7. 多加思考,多加练习。

使用双指针法解决数组问题时需要多加思考和观察,通过不断练习来提高自己的编程能力。


🏆 力扣上面有许多使用双指针法解决的数组问题,以下是一些经典题目的序号:
  • 第26题:删除排序数组中的重复项
  • 第27题:移除元素
  • 第75题:颜色分类
  • 第88题:合并两个有序数组
  • 第67题:两数之和 II - 输入有序数组
  • 第9题:长度最小的子数组
  • 第53题:会议室 II
  • 第45题:反转字符串中的元音字母
  • 第67题:字符串的排列
  • 第81题:最短无序连续子数组
  • 第77题:有序数组的平方

这些题目都是双指针的经典题目,可以帮助你更好的理解双指针的思想。

相关内容

热门资讯

解锁“新风景”!重庆国际生物城... 7月3日,重庆国际生物城开展了“小小科学家”研学营暨国家工业旅游示范基地精品线路启幕活动。重庆巴南育...
胡斌到松花湖风景名胜区调研 7月8日,市委书记胡斌率队来到松花湖风景名胜区,专题调研生态环境保护整改工作。他强调,要深入贯彻习近...
四姑娘山修改未成年人登山规定:... 本文转自【九派新闻】; 6月30日,一名16岁男孩在攀登四川四姑娘山时,在海拔约5276米的二峰垭口...
江苏上半年外籍旅客增长近三成,... 7月5日,韩国游客李成贤只用一个半小时航程,就从首尔“飞”抵盐城。落地后,他形容通关流程快得“只够喝...
走进杭州,当一回“大学声” 暮色浸染杭州清河坊,青砖黛瓦间传出强劲的电子音浪,浙江警察学院电声乐队改编的《黑猫警长》主题曲引发全...
西北青甘大环线全攻略,景点+路... 2025 年的夏天,我终于踏上了心心念念的西北之旅,选择了青甘大环线及甘南地区这条充满魅力的线路。这...
喵侦探 青春有你密室答案是谁? 喵侦探 青春有你密室答案是谁?不知不觉,《青春有你》这档节目也马上要迎来尾声了。在各位练习生选手们紧...
篮海青天指的什么意思? 篮海青天指的什么意思?篮海青天你说的这个应该是碧海青天吧,这个所指的意思就是指天空瓦蓝瓦蓝的,而大海...
从小就没有妈妈的女孩子的心理是... 从小就没有妈妈的女孩子的心理是如何样的应当会有恋父情结或者很欲望有一个照顾本身的女性长辈对男性依赖性...
爱过了,伤过了,该怎么做? 爱过了,伤过了,该怎么做?爱过伤过结局不完美也无所谓 坦然接受在伤之前有过爱幸福快乐的爱过已足够收起...
历史上的刘禅真的很没用吗 历史上的刘禅真的很没用吗错...历史上刘禅是一个很聪明的人,你可以找下正史,一开始刘禅是很聪明的一个...
如何彻底关闭小爱音箱啊? 如何彻底关闭小爱音箱啊?小爱音箱可以通过拔掉电源适配器实现关机。如果担心被语音误唤醒打扰,建议您按一...
我想当阴阳师,请问如何才能当? 我想当阴阳师,请问如何才能当?我不是开玩笑的,我想当阴阳师。如果有人认识阴阳师的话,请帮忙介绍。拜托...
英国经典文学作品列表 英国经典文学作品列表比较全面的哈,谢谢圣诞故事集(狄更斯的)还有沙士比亚的……呼啸山庄。简爱。其他可...
怎么开发客户 怎么开发客户1、重视客户的兴趣,与意愿与客户进行充分有效的沟通,实现厂商价值观念的一致性和认同性,树...
金鸡湖在苏州哪个区 金鸡湖在苏州哪个区工业园区,简称园区
美剧回生剧情 美剧回生剧情 《回生》是一部关于女孩死后,灵魂寻找被害真相的悬疑剧。这部改编自神秘系列剧《BeauS...
我和天蝎男交往!每天提醒我早点... 我和天蝎男交往!每天提醒我早点睡!叫我不要睡太晚!他是关心我!还是不想和我聊天!自从我们相互约定!我...
魔力泥巴 魔力泥巴年入百万,一个丫头的泥巴传奇
水浒传里谁最讲义气?要有事例的... 水浒传里谁最讲义气?要有事例的!一打祝家庄——林冲为第二拨人马领军统帅。 2、二打祝家庄——林冲神速...