双指针

Thursday, April 9, 2020

two-point

双指针思想的相关题目

有序数组的 Two Sum

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

因为已经排好序了,使用双指针即可,相加与 target 比较,比 target 小就将 lo 指针向右移,反之则将 hi 指针向前移

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        lo, hi = 0, (len(numbers) - 1)
        while lo < hi:
            if target < (numbers[lo] + numbers[hi]):
                # print(lo)
                hi -= 1
            elif target > (numbers[lo] + numbers[hi]):
                lo += 1
            else:
                return [lo+1, hi+1]
        return []

两数平方和

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

将 hi 指针设为数值的开方,然后用双指针解法即可

    def judgeSquareSum(self, c: int) -> bool:
        lo, hi = 0, int(sqrt(c))
        while lo <= hi:
            value = lo * lo + hi * hi
            if value > c:
                hi -= 1
            elif value < c:
                lo += 1
            else:
                return True
        return False

反转字符串中的元音字符

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

用一个数组记录所有的元音字符,然后用双指针遍历字符串,记录左右两边的元音字符位置,然后进行交换

    def reverseVowels(self, s: str) -> str:
        dic = ["A","E","I","O","U", "a","e", "i", "o", "u"]
        lo, hi = 0, len(s)-1
        s = list(s)
        while lo < hi:
            while lo < hi and s[lo] not in dic:
                lo += 1
            while lo < hi and s[hi] not in dic:
                hi -= 1
            if lo < hi:
                s[lo], s[hi] = s[hi], s[lo]
                lo += 1
                hi -= 1
        return ''.join(s)

判断是否是回文字符串

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

用双指针两头对比即可,但要注意可以删除一个字符的条件,所以可以用两个对比函数去对比。

    def validPalindrome(self, s: str) -> bool:
        lo, hi = 0, len(s) - 1
        while lo < hi:
            if s[lo] == s[hi]:
                lo += 1
                hi -= 1
            else:
                l1 = lo + 1
                h2 = hi - 1
                return self.vailPal(s, l1, hi) | self.vailPal(s, lo, h2)
        return True
    
    def vailPal(self, s: str, lo: int, hi: int) -> bool:
        while lo < hi:
            if s[lo] == s[hi]:
                lo += 1
                hi -= 1
            else:
                return False
        return True

归并两个有序数组

https://leetcode.com/problems/merge-sorted-array/description/

两个数组已排序,所以可以用尾部对比,然后一个个对比大小后填充进去即可,最后记得判断 nums2 是否全部对比完,没有的话需要将剩余的数字搬运到前面去

    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nlen = m + n - 1
        n2 = n - 1
        n1 = m - 1
        while n2 >= 0 and n1 >= 0:
            if nums2[n2] > nums1[n1]:
                nums1[nlen] = nums2[n2]
                n2 -= 1
            else:
                nums1[nlen] = nums1[n1]
                n1 -=1
            nlen -= 1
        if n2 >= 0:
            nums1[:n2+1] = nums2[:n2+1]

判断链表是否有环

https://leetcode.com/problems/linked-list-cycle/description/

用快慢指针即可,如果有环,则必会相遇

    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

最长子序列

https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/description/

首先构造一个是否为子字符串的函数来对比,这个函数用双指针思想,将两个字符串一个个的对比,相等的时候,两个指针均+1,不符合的时候主字符串+1,最后比较字符的长度是否等于筛检过的指针长度,如果相等,则说明主字符串通过删减确实可以变成对比的字符串。

筛检出来符合的字符串之后,再对比长度和字母的排序即可

    def findLongestWord(self, s: str, d: List[str]) -> str:
        result = None
        for d1 in d:
            if self.longestWord(s, d1):
                if result == None:
                    result = d1
                elif len(result) < len(d1):
                    result = d1
                elif len(result) == len(d1) and d1 < result:
                    result = d1
        if result:
            return result
        else:
            return ""
        
    
    def longestWord(self, s: str, d: str) -> bool:
        i, j = 0, 0
        while i < len(s) and j < len(d):
            if s[i] == d[j]:
                i += 1
                j += 1
            else:
                i += 1
        return j == len(d)
数据结构-算法LeetCode

栈和队列

App启动速度优化