Leetcode - double pointers (Chinese)

167. Two Sum II - Input array is sorted

题目描述

首先分别定义头尾指针, 因为输入序列已经有序, 若指针对应元素之和大于目标值, 前移尾指针, 反之后移头指针. 相等则返回结果, 因为答案要求位置从 1 开始, 故返回是要 +1. 当然第一题中使用哈希表的思想依然适用.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        if not numbers: return []
        hp =  0
        tp = len(numbers)-1
        while hp < tp:
            tmp_sum = numbers[hp] + numbers[tp]
            if tmp_sum > target:
                tp -= 1
            elif tmp_sum < target:
                hp += 1
            else:
                return [hp+1, tp+1]

        return []

633. Sum of Square Numbers

题目描述

和上一题思路相同, 比较有趣的是 a*a 的效率比 a**2 高很多.

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        assert c >= 0
        a = 0
        b = int(sqrt(c))
        while a <= b:
            tmp_sum = a*a + b*b
            if tmp_sum < c:
                a += 1
            elif tmp_sum > c:
                b -= 1
            else:
                return True
        return False

345. Reverse Vowels of a String

题目描述

同样是头尾指针的思路, 只是多了一些要处理的细节. 使用 set() 来生成元音集可以提高检索效率, 返回结果时要变回字符串.

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

125. Valid Palindrome

题目描述 使用 isalnum() 方法来判断元素是否为数字或字母, 然后统一使用小写来比对即可.

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