第11-12天打卡,附上学习链接
1 学习内容
1.1 双指针(Two Pointers)
双指针指的是在遍历元素的过程中,使用两个指针,方向相反称之为对撞指针,方向相同则称之快慢指针,如果属于不同的数组/链表,则称之为分离双指针。在数组的区间问题上,双指针可以将暴力算法的时间复杂度O(n2)降低到O(n)。
1.2 对撞指针
实现步骤:
(1)left指针指向第一个元素,right指针指向最后一个元素;
(2)循环体中,满足条件A,left指针右移;满足条件B,right指针左移;
(3)直到left==right,即相撞时,或其他条件,跳出循环体。
试用范围:
查找有序数组中满足某些约束条件的一组元素:如二分查找/数字之和等问题;
字符串反转问题,如反转字符串、回文数、颠倒二进制等问题。
示例习题1:0167 两数之和II - 输入有序数组 *
题目描述:给一个已按照非递减顺序排列的整数数组numbers,从数组中找出两个数满足相加之和等于目标数target。函数应该以长度为2的整数数组的形式返回这两个数的下标值。numbers的下标从1开始计数,所以答案数组应当满足1<=answer[0]<answer[1]<=numbers.length。可假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。 样例1:输入为numbers=[2, 7, 11, 15],target=9,输出为[2, 7]; 样例2:输入为numbers=[2, 3, 4],target=6,输出为[1, 3]; 样例3:输入为numbers=[-1, 0],target=-1,输出为[1, 2]。
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left+1, right+1]
elif total < target:
left += 1
else:
right -= 1
return [-1, -1]
示例习题2:0125 验证回文串 *
题目描述:给定一个字符串,判断是否为回文串(只考虑字符串中的字母和数字字符,且忽略字母的大小写)。回文串指正读和反读是一样的。 样例1:输入为“A man, a plan, a canal: Panama",输出为true; 样例2:输入为“race a car”, 输出为false。
解题思路:left指针 == right指针,相等则left+1, right-1,否则返回false。
class Solution:
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
return False
return True
示例习题3:0011 盛最多水的容器 **
题目描述:给定n个非负整数a1, a2, a3, ..., an, 每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线,垂直线i的两个端点分别为(i, ai)和(i, 0)。要求找出其中的两条垂直线,使得它们与x轴共同构成的容器可以容纳最多的水。 样例1:输入为[1, 8, 6, 2, 5, 4, 8, 3, 7],输出为49。
解题思路:水量的大小直接受两条线中较低的那条(比较left和right的高度),循环体内计算面积值时,同时维护更新最大面积值。
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
ans = 0
while left <= right:
area = min(height[left], height[right]) * (right - left)
ans = max(ans, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return ans
1.4 快慢指针
快慢指针指的是两个指针从同一侧开始遍历,但移动步长一个快(fast)一个慢(slow),停止的条件可以是快指针移动到数组尾端,也可以是两个指针相交,也可以是满足其他特殊条件。
实现步骤:
(1)slow一般指向第一个元素,即slow=0;fast一般指向第二个元素,即fast=1;
(2)循环体内,满足条件A,slow+1,满足条件B或者无条件,fast+1;
(3)结束条件,停止循环。
适用范围:
- 一般用于处理数组的移动、删除元素等问题,或者链表中的判断是否有环、长度问题。
示例习题1:0026 删除有序数组中的重复项 *
题目描述:给一个有序数组nums,原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。 样例1:输入为nums=[1, 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]。
解题思路:slow表示去除重复元素后的数组的末尾位置,slow=0,fast指向当前元素, fast=1。比较slow和fast上的元素是否相等,如果不等,则slow后移动1位,fast指向的元素复制到slow位置上,fast右移一位。重复,直到fast等于数组长度,返回slow+1即为新数组的长度。
class Solution:
def removeDuplicates(self, nums= List[int]) -> int:
if len(nums) <= 1:
return len(nums)
slow, fast = 0, 1
while fast < len(nums):
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1
1.5 分离双指针
实现步骤:
(1)left_1指向第一个数组的第一个元素,left2指向第二个数组的第一个元素;
(2)满足条件A,left_1 + 1, left_2 + 1;
(3)满足条件B,left_1 + 1;
(4)满足条件C,left_2 + 1;
(5)遍历结束一个数组或其他条件,结束循环。
适用范围:
- 一般用于处理有序数组合并,求交集、并集问题。
示例习题1:0349 两个数组的交集 *
题目描述:给定两个数组,编写函数实现计算它们的交集。 样例1:输入为nums1=[1, 2, 2, 1],nums2=[2, 2],输出为[2]; 样例2:输入为nums1=[4, 9, 5], nums2=[9, 4, 9, 8, 4],输出为[9, 4]。
解题思路:排序;left_1=0, left_2=0;当相等时,去重并加入输出答案数组,left_1+1,left_2+1;left_1<left_2,则left_1+1;left_1>left_2,则left_2+1;输出。
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1.sort()
nums2.sort()
left_1 = 0
left_2 = 0
res = []
while left_1 < len(nums1) and left_2 < len(nums2):
if nums1[left_1] == nums2[left_2]:
if nums1[left_1] not in res:
res.append(nums1[left_1])
left_1 += 1
left_2 += 1
elif nums1[left_1] < nums2[left_2]:
left_1 += 1
elif nums1[left_1] > nums2[left_2]:
left_2 += 1
return res
2 练习题目
2.1 0344 反转字符串 *
题目描述:将输入的字符串反转。 样例1:输入为s=["h", "e", "l", "l", "o"],输出为["o", "l", "l", "e", "h"]; 样例2:输入为s=["H", "a", "n", "n", "a", "h"],输出为["h", "a", "n", "n", "a", "H"]。
解题思路: 交换前后的字符。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
2.2 0015 三数之和 **
题目描述:给一个包含n个整数的数组nums,判断nums中是否存在三个元素a, b, c,使得a+b+c=0,找出所有和为0且不重复的三元组。 样例1:输入为nums=[-1, 0, 1, 2, -1, -4],输出为[[-1, -1, 2], [-1, 0, 1]]; 样例2:输入为nums=[],输出为[]; 样例3:输入为nums=[0],输出为[]。
解题思路:没有想明白。待填空。
2.3 0080 删除有序数组中的重复项 II **
题目描述:与0026类似,但允许每个元素最多出现两次。 样例1:输入为nums = [1,1,1,2,2,3],输出为5, nums = [1,1,2,2,3]; 样例2:输入为nums = [0,0,1,1,1,1,2,3,3],输出为7, nums = [0,0,1,1,2,3,3]。
解题思路:数量进行了限制,比较的时候需要加上前一项。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)
slow = 2
fast = 2
while fast < len(nums):
if nums[slow - 2] != nums[fast]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
2.4 0283 移动零 *
题目描述:给定一个数组nums,将所有0移动到数组的末尾,同时保持非零元素的相对顺序。 样例1:输入为[0, 1, 0, 3, 12],输出为[1, 3, 12, 0, 0]。
解题思路:左指针左边都为非零数,左指针到右指针间都为0。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
left = right = 0
while right < n:
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
时间复杂度:O(n);空间复杂度:O(1)。