Leetcode题解-数据结构-双指针(python版)

小灰灰 2023-01-22 12:53 11阅读 0赞

### 文章目录 ###

*   *  1、有序数组中找两个数和等于某数
     *  2、两数平方和
     *  3、翻转字符串中的元音字符
     *  4、判断是不是回文字符串（最多可以删一个字符）
     *  5、归并两个有序数组
     *  6、判断链表是否存在环
     *  7、最长子序列

## 1、有序数组中找两个数和等于某数 ##

[167. 两数之和 II - 输入有序数组(Easy)][167. _ II - _Easy]

class Solution(object):
        def twoSum(self, numbers, target):
            low, high = 0, len(numbers)-1
            while low < high:
                sum = numbers[low] + numbers[high]
                if sum == target:
                    return [low+1, high+1]
                if sum > target:
                    high -= 1
                else:
                    low += 1
            return [-1, -1]

## 2、两数平方和 ##

[633. 平方数之和(Easy)][633. _Easy]

class Solution(object):
        def judgeSquareSum(self, c):
            low = 0
            high = int(pow(c, 0.5))
            while low <= high:
                res = pow(low, 2) + pow(high, 2)
                if res == c:
                    return True
                elif res > c:
                    high -= 1
                else:
                    low += 1
            return False

## 3、翻转字符串中的元音字符 ##

[345. 反转字符串中的元音字母(Easy)][345. _Easy]

左右双指针遍历，把 str 转换成 list 处理，最后再 join 转回 str

class Solution(object):
        def reverseVowels(self, s):
            left, right = 0, len(s)-1
            vowel = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
            s_list = list(s)
            while left < right:
                if s_list[left] in vowel and s_list[right] in vowel:
                    s_list[left], s_list[right] = s_list[right], s_list[left]
                    left +=1
                    right -= 1
                if s[left] not in vowel:
                    left +=1
                if s[right] not in vowel:
                    right -= 1
            return "".join(s_list)

## 4、判断是不是回文字符串（最多可以删一个字符） ##

[680. 验证回文字符串 Ⅱ][680. _]

问题分析：两个指针分别指向头和尾，遇见不相等的字符时，跳过一个字符，判断剩下的是不是回文字符串。

class Solution(object):
        def validPalindrome(self, s):
            def is_palindrome(s, left, right):
                while left < right:
                    if s[left] != s[right]:
                        return False
                    left += 1
                    right -= 1
                return True
    
            begin, end = 0, len(s) - 1
            print(begin, end)
            while begin < end:
                if s[begin] != s[end]:
                    return is_palindrome(s, begin + 1, end) or is_palindrome(s, begin, end - 1)
                begin += 1
                end -= 1
            return True

## 5、归并两个有序数组 ##

[88. 合并两个有序数组][88.]

方法：逆向双指针  
指针从后向前遍历，每次取两者之中的较大者放进 nums1 的最后面

class Solution(object):
        def merge(self, nums1, m, nums2, n):
            p1, p2 = m - 1, n - 1
            tail = m + n - 1
            while p1 >=0 and p2 >= 0:
                if nums1[p1] > nums2[p2]:
                    nums1[tail] = nums1[p1]
                    p1 -= 1
                else:
                    nums1[tail] = nums2[p2]
                    p2 -=1
                tail -= 1
            while p1 >= 0:
                nums1[tail] = nums1[p1]
                p1 -= 1
                tail -= 1
            while p2 >= 0:
                nums1[tail] = nums2[p2]
                p2 -=1
                tail -= 1

## 6、判断链表是否存在环 ##

使用快慢两个指针，快指针每次移动两个节点，慢指针每次移动一个节点，如果存在环，这两个指针一定会相遇。

[141. 环形链表][141.]

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def hasCycle(self, head):
            if head == None:
                return False
            slow, fast = head, head
            while fast != None and fast.next != None:
                slow = slow.next
                fast = fast.next.next
                if fast == slow:
                    return True
            return False

## 7、最长子序列 ##

[524. 通过删除字母匹配到字典里最长单词][524.]

对于集合中的每个字符串，判断是否可以由指定字符串删除一些字符得到，如果可以，再判断与前面也符合该条件的字符串相比，是否长度更长，如果长度相等，再比较字典序大小

class Solution:
        def findLongestWord(self, s: str, dictionary: List[str]) -> str:
            def fun(s, target):
                len_s, len_target = len(s), len(target)
                p1, p2 = 0, 0
                while p1 < len_s and p2 < len_target:
                    if s[p1] == target[p2]:
                        p2 += 1
                    p1 += 1
                return p2 == len_target
    
            res = ""
            for target in dictionary:
                if fun(s, target):
                    if len(target) > len(res):
                        res = target
                    elif len(target) == len(res) and target < res:
                        res = target
            return res

[167. _ II - _Easy]: https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
[633. _Easy]: https://leetcode-cn.com/problems/sum-of-square-numbers/
[345. _Easy]: https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
[680. _]: https://leetcode-cn.com/problems/valid-palindrome-ii/
[88.]: https://leetcode-cn.com/problems/merge-sorted-array/
[141.]: https://leetcode-cn.com/problems/linked-list-cycle/
[524.]: https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/