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

LeetCode分类刷题之双指针(首尾指针)

程序员文章站 2022-06-09 18:12:42
LeetCode题目太多了,每天随便选题刷没有针对性,效率也很低,今天做了明天就忘了解法。分类刷题效率高,且解题思路形成套路可以更好的举一反三,时间有限的情况下非常推荐分类刷题。本文及后面的记录文章,所有解法均使用python。目录1.两数之和-有序数组(python中数组对应列表,栈也可对应列表)2.两数的平方和3.反转字符串中元音字母4.验证回文串5.验证回文字符串(加强版)6.反转字符串7.盛最多水的容器1.两数之和-有序数组(python中数组对应列表,栈也可...

LeetCode题目太多了,每天随便选题刷没有针对性,效率也很低,今天做了明天就忘了解法。分类刷题效率高,且解题思路形成套路可以更好的举一反三,时间有限的情况下非常推荐分类刷题。

本文及后面的记录文章,所有解法均使用python。

暴力解法是所有思路的起点。

目录

1.两数之和-有序数组(python中数组对应列表,栈也可对应列表)

2.两数的平方和

3.反转字符串中元音字母

4.验证回文串

5.验证回文字符串(加强版)

6.反转字符串

7.盛最多水的容器


1.两数之和-有序数组(python中数组对应列表,栈也可对应列表)

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

解题思路:首先题目说给定升序数组,那么肯定有比暴力更好的方法,一般会想到二分法,此题思路类似,用头尾指针来计算两数之和sum,如sum<target,则说明头指针的数值偏小需向右移动,如sum>target则说明尾指针数值偏大需向左移动。两个指针都逐渐向对方移动,也可称为首尾指针。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 特殊情况处理
        if not numbers: return []  

        start, end = 0, len(numbers)-1  #头尾指针

        while start < end:  #保证尾指针在头指针后边
            _sum = numbers[start] + numbers[end]
            if  _sum < target:  #小于目标值,首指针后移
                start += 1
            elif _sum > target: #大于目标值,尾指针前移
                end -= 1
            else:               #等于目标值,返回结果
                return [start + 1, end + 1]
        return []

2.两数的平方和

https://leetcode-cn.com/problems/sum-of-square-numbers/

解题思路:思路与上一题类似,找到两个数的平方和等于target,默认在一个1-n的升序数组中寻找两个数满足条件,问题的关键转化到了n如何确定,观察一下可以发现,n接近target开方的数值,然后就可以采用双指针来确定两个数了。

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        assert c >= 0
        start, end = 0, int(sqrt(c)) #设置首尾指针
        while start <= end:
            _sum = start **2 + end **2
            if _sum > c: end -= 1
            elif _sum < c: start += 1
            else: return True
        return False

3.反转字符串中元音字母

https://leetcode-cn.com/problems/reverse-vowels-of-a-string/

解题思路:此题同样是头尾行动,有一个问题就是如何判断字母是不是元音字母,这里可以创建一个元音字母set集合,用in来判断字母是不是集合中的元素。

class Solution:
    def reverseVowels(self, s: str) -> str:
        if len(s)<1: return s
        s = list(s)
        start, end = 0, len(s)-1
        vowels = set('aeiouAEIOU')
        while start < end:
            if s[start] in vowels and s[end] in vowels:
                s[start], s[end] = s[end], s[start]
                start += 1
                end -= 1
            elif s[start] in vowels: end -= 1
            elif s[end] in vowels: start += 1
            else: 
                start +=1
                end -= 1
        return ''.join(s)

4.验证回文串

https://leetcode-cn.com/problems/valid-palindrome/

解题思路:基本原理与之前题目一样,区别在于对字符串的处理,lower() 方法转换字符串中所有大写字符为小写,isalnum() 方法检测字符串是否由字母和数字组成。先用isalnum() 判断是不是字母,再用lower()忽略大小写。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) <= 1: return True
        start, end = 0, len(s)-1
        while start < end:
            if s[start].isalnum() and s[end].isalnum():
                if s[start].lower() == s[end].lower(): 
                    start += 1
                    end -=1
                    continue
                else: return False
            elif s[start].isalnum(): end -= 1
            elif s[end].isalnum() : start += 1
            else:
                start += 1
                end -= 1
        return True

5.验证回文字符串(加强版)

https://leetcode-cn.com/problems/valid-palindrome-ii/

解题思路:与上一题的区别在于可以删除一个字符再来判断是否为回文字符串,并且删除字符有两种情况,一种是删除头指针的一个字符start+1,一种是删除尾指针的一个字符end-1。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        if len(s) < 2: return True

        def isPalindrome(s, start, end):
            while start < end:
                if s[start] == s[end]:
                    start += 1
                    end -= 1
                    continue
                else: return False
            return True

        start, end = 0, len(s)-1
        while start < end:
            if s[start] == s[end]:
                start += 1
                end -= 1
                continue
            else: 
                return isPalindrome(s, start+1, end) or isPalindrome(s, start, end-1)
        return True

6.反转字符串

解题思路:这题没啥好说的,首尾指针原地交换

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        start, end = 0, len(s)-1

        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

7.盛最多水的容器

https://leetcode-cn.com/problems/container-with-most-water/

解题思路:题目实际上求的是最大面积,思路可以是先使横轴长度最长,也就是双指针end-start,然后依次移动指针高度最小的来更新面积,同时注意更新面积的写法。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        ml = 0 
        start, end = 0, len(height)-1
        while start < end:
            temp = min(height[start], height[end])*(end - start)
            ml = max(temp, ml)
            if height[start] >= height[end]:
                end -= 1
            else:
                start += 1
        return ml

 

本文地址:https://blog.csdn.net/hesongzefairy/article/details/107659722