双指针是什么意思,双指针排序
1.反向双指针反向式：翻转字符串，判断回文字符串；两个数和型：两个数和，三个数和。
分区类型：快速排序和颜色排序框架
Is回文(s): #两个指针(索引)，一左一右，从中间向左移动，right=0，len (s)-1 # left必须小于right while left right: if s[left]！=s [right]:返回false left=1 #左移一位右-=1 #右移一位返回True1.1验证回文字符串125。验证回文字符串
给定一个字符串，验证它是否是回文。只考虑字母和数字字符，字母的大小写可以忽略。
注意：在本主题中，我们将空字符串定义为有效的回文字符串。
示例1:
输入：“一个人，一个计划，一条运河：巴拿马”
输出：真
解释：“amanaplanacanalpanama”是一个回文。
示例2:
输入：“赛车”
输出：假
解释：“raceacar”不是回文。
1=s.length=2 * 105
的字符串由ASCII字符组成。
解决方案：
类别解决方案：
def isPalindrome(self，s: str) - bool:
好=“”。join([I . lower()for I in s if I . is digit()或i.isalpha()])
左，右=0，len(好)- 1
而左右：
如果好[左]！=好[对]:
返回False
左=1
右-=1
返回True
1.2验证回文字符串II
80.验证回文字符串
给定一个非空字符串s，最多删除一个字符。判断它是否能成为回文字符串。
示例1:
输入：s=aba
输出：真
示例2:
输入：s=abca
输出：真
说明：可以删除C字符。
示例3:
输入：s=abc
输出：假
1=标准长度=105
s由小写英文字母组成。
解决方案：
类别解决方案：
def有效回文(self，s: str) - bool:
如果len(s)==1:
返回True
l，r=0，len(s) - 1
而l r:
如果s[l]==s[r]:
l=1
r -=1
否则：
返回self . is _回文(s，l 1，r)或self . is _回文(s，l，r-1)
返回True
def是_回文(self，s，l，r):
而l r:
如果s[l]！=s[r]:
返回False
l=1
r -=1
返回True
1.3两个数之和
1.两个数的和
给定一个整数数组nums和一个整数目标值target，请找出数组中作为目标值的两个整数，并返回它们的数组下标。
你可以假设每个输入只对应一个答案。但是，数组中的同一个元素不能在答案中重复。
您可以按任意顺序返回答案。
示例1:
输入：nums=[2，7，11，15]，目标=9
输出：[0，1]
说明：因为nums[0] nums[1]==9，所以返回[0，1]。
示例2:
输入：nums=[3，2，4]，目标=6
输出：[1，2]
示例3:
输入：nums=[3，3]，目标=6
输出：[0，1]
2=nums.length=104
-109=nums[i]=109
-109=目标=109
只有一个有效的答案。
问题1:哈希表(时间和空间复杂度为O(n))
类别解决方案：
def twoSum(self，nums: List[int]，target: int) - List[int]:
信息={}
对于索引，我在枚举(nums):
如果目标- i在信息中：
返回[信息[目标-i]，索引]
如果我不在信息中：
信息[i]=索引
return [-1，-1]
解决方案2:排序双指针(时间复杂度O(nlogn)，空间复杂度O(1))
类别解决方案：
def twoSum(self，nums: List[int]，target: int) - List[int]:
num_idx=[(num，i) for i，num in enumerate(nums)]
num _ idx . sort(key=lambda x:x[0])#[(2，0)，(7，1)，(11，2)，(15，3)]
left，right=0，len(nums) - 1
而左右：
if num _ idx[left][0]num _ idx[right][0]==target:
return[数字索引[左][1]，数字索引[右][1]]
elif num _ idx[left][0]num _ idx[right][0]target:
右-=1
否则：
左=1
return [-1，-1]
1.4二分搜索法
74.二进位检索
给定一个整数数组nums，有n个有序元素和一个目标值target，写一个函数在nums中搜索目标，如果目标值有返回下标，返回-1，否则返回。
示例1:
输入：nums=[-1，0，3，5，9，12]，目标=9
输出：4
解释：9出现在nums中，它的下标是4
示例2:
输入：nums=[-1，0，3，5，9，12]，目标=2
输出：-1
说明：2在nums中不存在，所以返回-1。
您可以假设num中的所有元素都不是重复的。
n将介于[1，10000]之间。
nums的每个元素都会在[-9999，9999]之间。
解决方案：
类别解决方案：
def search(self，nums: List[int]，target: int) - int:
left，right=0，len(nums) - 1
而左=右：
mid=(左右)//2
if nums[mid]==目标：
返回mid
elif nums[mid]目标：
右-=1
否则：
左=1
返回-1
1.5反向排列
从输入导入列表
类别解决方案：
def reverse_list(self，nums: List[str]) - List[str]:
left，right=0，len(nums) - 1
而左右：
temp=nums[left]
Nums[left]=nums[right] #交换两个数。
nums[right]=温度
右-=1
左=1
返回数字
if __name__==__main__ :
s=解决方案()
print(s.reverse_list([1 ， 2 ， 3]))
print(s.reverse_list([3 ， 2 ， 1]))
分析：
nums=[1 ， 2 ， 3]
#第一次
左=0，右=2
当0 2:
temp=1
nums[0]=nums[2]=nums=[3 ， 2 ， 3]
nums[2]=1=nums=[3 ， 2 ， 1]
右-=1
左=1
#第二次
左=1，右=1
而1 1:
返回数字
1.6判断字符串回文
定义解决方案(字符串):
left，right=0，len(string) - 1
而左右：
if字符串[left]！=string[right]:
返回False
左=1
右-=1
返回True
if __name__==__main__ :
打印(解决方案( aba ))
打印(解决方案( abac ))
打印(解决方案( 1221 ))
2.回到双指针
2.1最长的回文子串
5.最长的回文子串
给你一个字符串S，求S中最长的回文子串。
示例1:
Enter: s=babad
输出：“bab”
说明：‘ABA’也是问题的答案。
示例2:
输入：s=cbbd
解决方案：
技能：由中心向两端扩散的两分球技能。
因为回文串长度可能是奇数也可能是偶数；如果是奇数，可以中间字符为分界点向两端扩散；如果是偶数，中心两个字符可以向外扩散：
类别解决方案：
def longest回文(self，s: str) - str:
long_sub=
对于范围内的I(透镜):
S1=is _回文(s，I，i) #以s[i]为中心的最长回文子串
S2=is _回文(s，I，i 1) #以s[i]和s[i 1]为中心的最长回文子串
long _ sub=long _ sub if len(long _ sub)len(S1)else S1
long _ sub=long _ sub if len(long _ sub)len(S2)else S2
返回long_sub
def is _回文(s，l，r):
寻找s中以s[l]和s[r]为中心的最长回文字符串
#防止下标越界
当l=0和r len(s)时：
如果s[l]！=s[r]:
破裂
#双手向两边展开
l -=1
r=1
Return s[l 1: r] #返回以s[l]和s[r]为中心的最长的回文字符串
3.同一个方向的双指针
同向双指针又叫快慢指针。
3.1删除有序数组副本
26.删除有序数组中的重复项。
给你一个升序排列的数组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。不需要考虑数组中超出新长度的元素。
解决方案：
从输入导入列表
类别解决方案：
def removeDuplicates(self，nums: List[int]) - int:
如果len(nums)==0:
返回0
慢，快=0，0
打印(数字、慢速、快速)
而快速len(nums):
if nums[快]！=nums[慢速]:
慢速=1
nums[慢速]
快速=1
打印(数字、慢速、快速)
慢速返回1
if __name__==__main__ :
s=解决方案()
print(s.removeDuplicates([1，1，2，3])# 3
print(s.removeDuplicates([0，0，1，1，2，3，4，5，6])# 7
[1, 1, 2, 3] 0 0
[1, 1, 2, 3] 0 1
[1, 1, 2, 3] 0 2
[1, 2, 2, 3] 1 3
[1, 2, 3, 3] 2 4
慢指针走在后面，快指针走在前面，遇到非重复元素会赋给慢，慢向前一步，这样nums[0，slow]就是非重复元素。
3.2删除排序链表中的重复元素
83.删除排序链表中的重复元素。
给定一个有序链表的头，删除所有重复的元素，这样每个元素只出现一次。返回排序后的链表。
输入：head=[1，1，2]
输出：[1，2]
输入：head=[1，1，2，3，3]
输出：[1，2，3]
解决方案：
#单链表的定义。
#类别列表节点：
# def __init__(self，val=0，next=None):
# self.val=val
# self.next=下一个
类别解决方案：
def deleteDuplicates(self，head: ListNode) - ListNode:
如果head==None:
不返回
慢=快=头
一边快！=无：
如果快.瓦尔！=slow.val:
slow.next=fast
慢=慢。下一个
快=快。下一个
Slow.next=None #断开下列重复元素。
回程头
3.3从数组中删除指定的元素。
27.移除元素
给定一个数组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。请注意，这五个元素可以按任意顺序排列。不需要考虑数组中超过新长度的元素。
解决方案：
从输入导入列表
类别解决方案：
def removeElement(self，nums: List[int]，val: int) - int:
如果不是nums:
返回0
慢，快=0，0
print(f nums:{ nums } \ t slow:{ slow } \ t fast:{ fast } \ t val:{ val } )
而快速len(nums):
if nums[快]！=val:
nums[慢速]
慢速=1
快速=1
print(f nums:{ nums } \ t slow:{ slow } \ t fast:{ fast } \ t val:{ val } )
缓慢返回
if __name__==__main__ :
s=解决方案()
# print(s.removeElement([0，1，2，2，3，0，4，2]，2))
print(s.removeElement([0，1，2)，0)) # 2
数字：[0，1，2]慢：0快：0值：0
数字：[0，1，2]慢：0快：1值：0
nums: [1，1，2]慢：1快：2值：0
nums: [1，2，2]慢：2快：3值：0
如果fast的元素与val相同，它将被跳过，fast 1
当fast的元素不同于val时，将当前元素指定为slow，slow前进1。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。