leetcode: 2 pointers
算法分析
该类题型是很好理解,应该先刷,双指针一般会遇到两种类型,一类是数组双指针在两端,一类是链表指针在两端。如leetcode 11, 15,16,18等等。使用双指针可以把时间从O(n^2)提高到O(n), 一般能减小一个n次方。觉得也没有必要完全按照标签来做,因为如果能用一种其他的方法解题也可以不考虑双指针,目的是解题,方法用自己最擅长的就可以。没有必要为了某一个解题方法重复做太多的题。关键是知道这样的方法。
11. Container With Most Water
1 lo: left pointer, hi: right pointer, at both side
2 this may have the largest value, then i to right, j to left
3 until lo >= hi, stop loops and return result
class Solution:
def maxArea(self, height: List[int]) -> int:
lo, hi = 0, len(height) - 1
res = 0
while lo < hi:
res = max(res, min(height[lo], height[hi]) * (hi - lo))
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return res
15. 3Sum
1 prepare a set:为了避免重复
2 sort the array:为了利用双指针
3 for each i loop, use 2 pointers to reduce time in sorted array
4 use set to avoid repeating
5 if i > 0 and nums[i] == nums[i-1]:为了加快速度
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = set()
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue # if already use i, no need to use any more
low, high = i + 1, len(nums) - 1
while low < high:
three = nums[i] + nums[low] + nums[high]
if three == 0:
res.add((nums[i], nums[low], nums[high]))
low += 1
high -= 1
elif three < 0:
low += 1
else:
high -= 1
return res
16. 3Sum Closest
1 prepare a res = infinity
2 sort the array
3 for each i in loop, use 2 pointers to find the closest
4 if equals to target, return target
5 else return closest
6 if low >= high, output res
补充一句话加快速度
if i > 0 and nums[i] == nums[i-1]:
continue
因为已经遍历过的元素没有必要再次遍历,再次遍历是的结果一定是他的子集
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
res = float('inf')
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
three = nums[i] + nums[lo] + nums[hi]
if three == target:
return target
if abs(three - target) < abs(res - target):
res = three
if three < target:
lo += 1
else:
hi -= 1
return res
18. 4Sum
加上一句:if i > 0 and nums[i] == nums[i-1]: continue, 加快速度。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
num_set = set()
nums.sort()
for i in range(len(nums) - 1):
if i > 0 and nums[i] == nums[i-1]: continue
for j in range(i + 1, len(nums)):
lo, hi = j + 1, len(nums) - 1
while lo < hi:
four = nums[i] + nums[j] + nums[lo] + nums[hi]
if four == target:
num_set.add((nums[i], nums[j], nums[lo], nums[hi]))
lo += 1
hi -= 1
elif four < target:
lo += 1
else:
hi -= 1
return num_set
26. Remove Duplicates from Sorted Array
这是双指针的另一种写法, idx是一个慢指针, i是一个快指针。因为是排好序的数组,只要快指针遇到不一样的数字,那么把这个数字放到慢指针的位置上即可。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
idx = 1
for i in range(1, len(nums)):
if nums[i-1] != nums[i]:
nums[idx] = nums[i]
idx += 1
return idx
151. Reverse Words in a String
既然用python, 必然会用到各种的库,没有必要想加入用其他的程序语言怎么写,split, 怎么写join, 我们需要做的就是如何用,毕竟我们不是C++算法高手。本题用到双指针就可以了,当然可以直接用reverse. 但是接下来的问题是in place,所以解法1, 2不行。方法3才是in place,这样就得用到C++的方法了。
方法1:
class Solution:
def reverseWords(self, s: str) -> str:
lst = s.split()
lo, hi = 0, len(lst) - 1
while lo < hi:
lst[lo], lst[hi] = lst[hi], lst[lo]
lo += 1
hi -= 1
return " ".join(lst)
方法2:
class Solution:
def reverseWords(self, s: str) -> str:
lst = s.split()
lst.reverse()
return " ".join(lst)
方法3:全部双指针
class Solution:
def reverseWords(self, s: str) -> str:
res, i, n = '', 0, len(s)
while i < n: # if i out of loop, stop
while i < n and s[i] == ' ':
i += 1
if i >= n:
break
j = i + 1
while j < n and s[j] != ' ':
j += 1
sub = s[i: j]
if len(res) == 0:
res = sub # the first word: hello
else:
res = sub + " " + res # reverse
i = j + 1 # next word: world
return res
上一篇: 2021暑假Leetcode刷题——Two Pointers(2)
下一篇: 141.环形链表。2星