[数据结构与算法]python3-算法刷题-数组-双指针-更新中

双指针有两种：1）快慢指针：两个指针向同一个方向前进，一快一慢；2）左右指针：两个指针相向或相背移动

快慢指针

【简单】26. 删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

思路：使用下标作为指针。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow = fast = 0
        while fast < len(nums):
            if nums[slow] != nums[fast]:
                # +1 是为了让[0,slow]都没有重复，修改的是后一个位置
                slow += 1
                nums[slow] = nums[fast]
            fast += 1
        # 要求返回修改后数组的长度 
        return slow + 1

【简单】83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
思路：跟数组这个完全一样！！！

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head == None or head.next == None: 
            return head
        fast = slow = head
        while fast != None:
            if fast.val != slow.val:
                slow.next = fast
                slow = slow.next
            fast = fast.next
        # 此时已经slow后面是重复元素了，所以给它连到None上去
        # 比如1→2→2，slow最后停在第一个2上
        slow.next = None
        return head

【简单】27. 移除元素

https://leetcode.cn/problems/remove-element
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

思路：双指针。快指针一路向前，如果是val，那么直接跳过去；如果不是val，将快指针值赋值到慢指针位置，然后移动慢指针。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if len(nums) == 0: return 0
        fast = slow = 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1    
        return slow

【简单】283. 移动零

https://leetcode.cn/problems/move-zeroes/
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路：这题直接复用上面的代码，使val=0即可。然后再将slow后面的元素设为0

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 1: return
        fast = slow = 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1 
        while slow < len(nums):
            nums[slow] = 0 
            slow += 1

左右指针

二分查找：基础版

def binarySearch(nums:list[int], target:int)->int:
    left = 0
    right = len(nums) - 1
    # 注意这里有个=
    while left <=right:
        mid = (right + left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

其中计算mid可以换成： left+(right-left)//2 这样可以防止数值过大时溢出

【中等】167. 两数之和 II - 输入有序数组

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

思路：看到非递减、有序之类的字眼立刻想到能不能用二分查找。。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        # 不能重复使用
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left + 1, right + 1]
            elif s < target:
                left += 1
            else:
                right -= 1   

就地反转数组or字符串，判断回文串都是利用相向的双指针。不再赘述。

二分查找-找到左边界版

def binarySearchLeftBound(nums:list[int], target:int)->int:
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            right = mid - 1 # 不断向左收缩，找左边界
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if left == len(nums): return -1
    if nums[left] == target: return left
    else: return -1 

二分查找-找到右边界版

def binarySearchLeftBound(nums:list[int], target:int)->int:
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1 # 不断向右
        else:
            right = mid - 1
    if left -1 < 0: return -1
    if nums[left-1] == target: return left-1
    else: return -1 

【中等】34. 在排序数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路：直接调用上面的函数即可。另外加对[]的判断。

class Solution:
    def searchLeftBound(self, nums: List[int], target: int) -> int:
        if nums == []: return -1
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= target:
                right = mid -1
            else:
                left = mid + 1
        if left == len(nums) or nums[left] != target: return -1
        return left

    def searchRightBound(self, nums: List[int], target: int) -> int:
        if nums == []: return -1
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        if left < 1 or nums[left-1] != target: return -1
        return left-1

    def searchRange(self, nums: List[int], target: int) -> List[int]:
        return [self.searchLeftBound(nums, target), self.searchRightBound(nums, target)]

【简单】剑指 Offer 53 - I. 在排序数组中查找数字 I

https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

思路：还是直接复用二分查找左右边界的函数。这里直接写主函数了。

	def search(self, nums: List[int], target: int) -> int:
        left = self.searchLeftBound(nums, target)
        # 如果左边界已经找不到，那没必要继续查找右边界了
        if left == -1: return 0
        right = self.searchRightBound(nums, target)
        return right - left + 1

【简单】278. 第一个错误的版本

https://leetcode.cn/problems/first-bad-version/

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        while left < right:
            mid = left + (right - left) // 2
            # 答案在[left, mid]
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1
        return left 

【中等】5. 最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

思路：这次是从中心向两侧扩展。相背而行的双指针。

class Solution:
    # 计算以[left,right]为中心的最长回文子串
    def findWithBound(self, s:str, left:int, right:int) -> str:
        # 下标合法且满足回文要求，则向两侧扩展子串
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left+1:right]

    def longestPalindrome(self, s: str) -> str:
        ans = ""
        for i in range(len(s)):
            # 如果字串长度为奇数，中心就是自己
            odds = self.findWithBound(s, i, i)
            # 如果字符串长度为偶数，那么输入相邻的两个
            evens = self.findWithBound(s, i, i + 1)
            # 选择长度最长的那个更新ans值
            if len(odds) > len(ans):
                ans = odds
            if len(evens) > len(ans):
                ans = evens
        return ans  

【中等】647. 回文子串

https://leetcode.cn/problems/palindromic-substrings/
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

思路：照着上题的改，只不过每次得到回文的时候都+1

class Solution:
    def findWithBound(self, s:str, left:int, right:int) -> int:
        cnt = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
            # 表示此时有一个回文子串
            cnt += 1
        return cnt

    def countSubstrings(self, s: str) -> int:
        cnt = 0
        for i in range(len(s)):
            cnt += self.findWithBound(s,i,i) + self.findWithBound(s,i,i+1)
        return cnt