IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> python3-算法刷题-数组-双指针-更新中 -> 正文阅读

[数据结构与算法]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
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-10-22 21:39:02  更:2022-10-22 21:42:55 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 2:01:36-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计