欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode: 2 pointers

程序员文章站 2024-02-29 08:20:52
...

算法分析

该类题型是很好理解,应该先刷,双指针一般会遇到两种类型,一类是数组双指针在两端,一类是链表指针在两端。如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