chapter8-dual-pointer-algorithm

---

chapter8-dual-pointer-algorithm

[TOC]

双指针

1. 有序数组的 Two Sum

Leetcode / 力扣

def twoSum():
    numbers = [2, 7, 11, 15]; target = 9

    # you题意可知
    # 1.有序数组 2. 需要到两个数之和等于target
    # 要利用好有序，单调递增的数组
    # 就需要创建两个指针left,right分别指向头和尾
    # 因为right--，就必定说明之和减少
    # left++， 就必定说明之和增加
    # 就一直找到target即可
    # 代码逻辑如下：
    def slove1():
        left, right = 0, len(numbers) - 1
        while (left < right):
            mid = numbers[ left ] + numbers[ right ]
            if mid == target:
                return [ left + 1, right + 1 ]
            if mid > target:
                right -= 1
            else:
                left += 1
        return [ ]

    # nuenuenue
    def slove2():
        dp = {v:i for i, v in enumerate(numbers)}
        for i, v in enumerate(numbers):
            try:
                if dp[target - v] != i:
                    print(dp[target - v])
                    return [i+1, dp[target - v]+1]
            except:
                continue
        return []


    print(slove2())

print(twoSum())

2. 两数平方和

Leetcode / 力扣

def judgeSquareSum():
    c = 4
    # you题意可知
    # 对于两个数平方之和，这两个值一定是小于等于c开方的（向上取整）
    # 比如c=16 16**0.5=4 因此这两个数是[0,4]，而在这之间组成的平方数之和的数一定是在[0,c**0.5]
    # 因此，只需要在这之间进行判断即可

    import math
    left, right = 0, math.floor(int(c**0.5))
    print(int(c**0.5))
    while(left <= right):
        if left**2 + right**2 == c:
            return [left, right]
        if left**2 + right**2 < c:
            left += 1
        else:
            right -= 1
    return []

print(judgeSquareSum())

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

Leetcode / 力扣

def reverseVowels():
    vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
    s = "hello"

    # you题意可知
    # 要反转元音字符，必须有两个才行
    # 因此 只需要两个指针，一头一尾，分别向上和向下移动搜索元音字符即可
    # 如果都是了，就进行交换
    # 代码逻辑如下：
    s = list(s)
    left, right = 0, len(s) - 1
    while(left < right):
        if s[left] not in vowels:
            left += 1
            continue
        if s[right] not in vowels:
            right -= 1
            continue
        s[right],s[left] = s[left], s[right]
        left += 1
        right -= 1
    print(s)
    return ''.join(s)
reverseVowels()

4. 回文字符串

Leetcode / 力扣

def validPalindrome():
    s = "ebcbb ececabbacec bbcbe"
    # 错误示范，不能够直接通过直接判断上下是否相等来进行转化，
    # 需要穷尽全部选择
    def slove1():
        left, right = 0, len(s) - 1
        cnt = 0
        while (left < right):
            if s[ left ] == s[ right ]:
                right -= 1
                left += 1
            else:
                cnt += 1

                if cnt >= 2:
                    return False
                # 错误就在于这两个if语句
                # 如果这两个if语句都满足，只能算猜一个，没有完成度不够完全
                if s[ left ] == s[ right - 1 ]:
                    right -= 1
                    continue
                if s[ left + 1 ] == s[ right ]:
                    left += 1
                    continue
                left += 1

        return True

    # 回文字符串，就是一个字符串，是对称的
    # 因此只需要前后设置设置一个指针，进行判断是否相同即可
    # 难点就在于当出现第一次不相等时，会有两种情况进行比较
    # 即left不变right-1,和right不变，left+1时
    def slove2():
        def isPalindrome(s, left, right):
            while (left < right):
                if s[ left ] == s[ right ]:
                    right -= 1
                    left += 1
                else:
                    return False
            return True

        left, right = 0, len(s) - 1
        while (left < right):
            if s[ left ] == s[ right ]:
                right -= 1
                left += 1
            else:
                return  (isPalindrome(s, left, right-1) or isPalindrome(s, left+1, right))
        return True
    print(slove2())
validPalindrome()

5. 归并两个有序数组

Leetcode / 力扣

def merge():
    nums1 = [ 1, 2, 3, 0, 0, 0 ]; m = 3
    nums2 = [ 2, 5, 6 ]; n = 3
    # you题意可知
    # nums1保留了与nums2相同大小的空间
    # 所以我们可以大胆从末尾开始计数，nums2和nums1又到大小依次从末尾放入放入
    # 把为0的坑给填满
    # 当都填完后，一定是吧nums1或者nums2的数填到了后面，前面的数字，直接覆盖即可（nums1或者nums2的数）
    # 因此代码逻辑为：

    index1, index2 = m-1, n-1
    indexMerge = m+n-1
    while( index1 >= 0 and index2 >= 0):
        if nums1[index1] > nums2[index2]:
            nums1[ indexMerge ] = nums1[ index1 ]
            index1 -= 1
        else:
            nums1[ indexMerge ] = nums2[ index2 ]
            index2 -= 1
        indexMerge -= 1

    nums1[:index2+1] = nums2[:index2+1]
    print(nums1)
    return nums1
merge()

6. 判断链表是否存在环

Leetcode / 力扣

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # 定义一个慢真正和一个快指针
    # 满指正走一圈的位置和快指针走两圈的位置是一样的
    # 因此快指针每次走两步，而慢指针每次走一步
    # 如果有环，一定能够到达相同的点
    # 如果没有环，那循环结束，遍历的链表的结尾None

    def hasCycle(self, head: ListNode) -> bool:
        if head == None:
           return False
        l1 = head
        l2 = head.next
        while(l1 != None and l2 != None and l2.next != None):
            if l1 == l2:
                return True
            l1 = l1.next
            l2 = l2.next.next
        return False

head = ListNode(1)
head.next = ListNode(3)
# head.next = head
s = Solution()
print(s.hasCycle(head))

7. 最长子序列

Leetcode / 力扣

def findLongestWord():
    s = "bab"; d = [ "ba", "ab", "a", "b" ]
    # you题意可知
    # 1.找到字符串d可以通过删除给定字符串s的某些字符来得到
    # 如果多结果长度相同，返回长度最长且字典顺序最小的字符串(就是那字母小，比如"ba", "ab"，选"ab")
    # 综上所诉，通过对d长度由大到小排序，如果长度相同通过字母大小排序（避免遍历完全部字符串）
    # 然后依次遍历字符串，如果当前字符串能够满足条件，那么就是这个字字符串
    # 因此代码逻辑如下
    d.sort(key = lambda x:(-len(x),x))
    def isSubstr(t, s):
        j = 0
        for c in t:
            index = s.find(c,j)
            if index == -1:
                return False
            j = index + 1
        return True

    for t in d:
        if isSubstr(t,s):
            print(t)
            return t
    return ''
findLongestWord()