双指针的题,即利用两个指针去遍历数组。往往涉及到有序的范围,可以通过左右的加减来减少暴力遍历的次数。
11. Container With Most Water(Medium)
该题就是一个两边最优解的问题,暴力O(n2)会超时,双指针O(n)就很稳。
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
if len(s) <= 1 or numRows == 1:
return s
res = [''] * numRows
num = (numRows - 1) * 2
for i,item in enumerate(s):
if i % num >= numRows:
res[num - i % num] += item
else:
res[i % num] += item
return ''.join(res)
15. 3Sum(Medium)
与此题相似的还有16. 3Sum Closest 和 18. 4Sum,会做15题后后面两题就轻松了,第一次做3Sum的时候非常吃力,用了O(n^3)的算法,无论怎么优化都会超时。
后来看发现先排序凑成有序序列后,用双指针的办法O(n^2)可以通过很巧妙,除此之外还要注意一下去重的问题。
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# O(n^2)
res = []
nums.sort()
for start in range(len(nums)-2):
if start > 0 and nums[start] == nums[start-1]:
continue
l, r = start + 1, len(nums) - 1
while l < r:
if nums[start] + nums[l] + nums[r] == 0 and [nums[start], nums[l], nums[r]] not in res:
res.append([nums[start], nums[l], nums[r]])
r -= 1
l += 1
#去重
while l < r and nums[l] == nums[l-1]:
l += 1
while l < r and nums[r] == nums[r+1]:
r -= 1
elif nums[start] + nums[l] + nums[r] < 0:
l += 1
else:
r -= 1
return res
26. Remove Duplicates from Sorted Array(Easy)
刚开始看题题目意思没有理解,需要in-place原地修改数组,返回数组修改后需要取的长度,与此题相似的还有27. Remove Element,加一个size指针存储即可。
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
size = 0
for i in range(len(nums)):
if nums[i] == val:
continue
nums[size] = nums[i]
size += 1
return size
80. Remove Duplicates from Sorted Array II(Medium)
26题的升级版,解法也差不多,空间复杂度O(1)。
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
for n in nums:
if i < 2 or n > nums[i-2]:
nums[i] = n
i += 1
return i
网友评论