算法长征（5）双指针

双指针

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

• 双指针、队列

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 回溯 + set
        n = len(s)
        que = collections.deque()
        if len(s) == 0:
            return 0
        que.append(s[0])
        res = 1
        tmp = 1
        for i in range(1, n):
            if s[i] not in que:
                tmp += 1
            else:
                while que and que.popleft() != s[i]:
                    tmp -= 1
            que.append(s[i])
            res = max(res, tmp)
        return res
    def lengthOfLongestSubstring(self, s: str) -> int:
      	# 双指针 + 哈希表
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 哈希表记录
            res = max(res, j - i) # 更新结果
        return res

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        cur = dummy = ListNode(0, head)
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
                break
            else:
                cur = cur.next
        return dummy.next

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast, slow = head, head
        for _ in range(k):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        while l1 and l2:
            if l1.val > l2.val:
                cur.next, l2 = l2, l2.next
            else:
                cur.next, l1 = l1, l1.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next

输入两个链表，找出它们的第一个公共节点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p1, p2 = headA, headB
        while p1 != p2:
            p1 = p1.next if p1 else headB
            p2 = p2.next if p2 else headA
        return p1

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums)-1
        while left < right:
            while nums[left]%2 == 1 and left < right: 
              	left += 1
            while nums[right]%2 == 0 and left < right: 
              	right -= 1
            nums[left], nums[right] = nums[right], nums[left]
        return nums
    def exchange(self, nums: List[int]) -> List[int]:
    		return sorted(nums, key = lambda x: x%2, reverse = True)

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

解题思路：

• 利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N)；

• 注意本题的 nums 是排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1)。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ndict = defaultdict(int)
        for i in range(len(nums)):
            if target-nums[i] in ndict:
                return [target-nums[i], nums[i]]
            ndict[nums[i]] = 1
        return []
        
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums)-1
        while left < right:
            s = nums[left] + nums[right]
            if s > target:
                right -= 1
            elif s < target:
                left += 1
            else:
                return [nums[left], nums[right]]
        return []

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.strip().split()))

    def reverseWords(self, s: str) -> str:
        s = s.strip() # 删除首尾空格
        i = j = len(s) - 1
        res = []
        while i >= 0:
            while i >= 0 and s[i] != ' ': i -= 1 # 搜索首个空格
            res.append(s[i + 1: j + 1]) # 添加单词
            while s[i] == ' ': i -= 1 # 跳过单词间空格
            j = i # j 指向下个单词的尾字符
        return ' '.join(res) # 拼接并返回