3

Double Pointer and Binary Search Algorithm

 2 years ago
source link: https://xfliu1998.github.io/2023/03/19/Double-Pointer-and-Binary-Search-Algorithm/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一直进步 做喜欢的

Double Pointer and Binary Search Algorithm

Created2023-03-19|Updated2023-03-19|Data Structures and Algorithms
Word count:2.2k|Reading time:7min|Post View:1|Comments:
  • 基本思想：使用两个指针分别指向数组或链表的头部、尾部或中间位置，并移动指针，解决问题。
  • 类型：
    • 快慢指针：快指针每次移动两个元素，慢指针每次移动一个元素，快慢指针常用于链表的中间节点查找、链表是否有环等问题。
    • 左右指针：左指针从数组或链表的左侧开始移动，右指针从数组或链表的右侧开始移动，左右指针通常用于解决数组或链表中的查找、排序等问题。
  • 复杂度：时间复杂度通常为O(n)，空间复杂度为O(1)。
  • 应用场景：数组或链表中元素的查找、排序、去重、合并、分割等问题。常见的问题有两数之和、三数之和、反转链表等。
  • 注意：注意指针的初始位置、指针移动的条件和方向、循环退出的条件等。

主要解决链表中的问题。
快慢指针⼀般都初始化指向链表的头结点 head，前进时快指针 fast 每次走2步在前，慢指针 slow 每次走1步在后。

双指针——快慢指针
题目 技巧 难度
✅19. 删除链表的倒数第 N 个结点 寻找链表倒数第k元素：fast先走k步，fast到尾部是slow的位置；需在初始化slow时添加一个首结点，否则删除的是倒数第n-1个结点 🌟🌟
✅61. 旋转链表 fast先走k步找到倒数第k结点 🌟🌟
✅141. 环形链表 🌟
✅142. 环形链表 II 已知链表有环，返回环的起始位置：相遇时slow返回head，再相遇时为环起点 🌟🌟
✅160. 相交链表 互相走一遍，再相遇时为交点 🌟
✅876. 链表的中间结点 🌟
✅2095. 删除链表的中间节点 🌟🌟

主要解决数组或字符串的问题。二分查找也是典型的左右指针问题。
左右指针实际是两个索引值，一般初始化left, right = 0, len(nums) - 1

双指针——左右指针
题目 技巧 难度
✅5. 最长回文子串 中心扩展法，向两边移动指针判断是否为回文 🌟🌟
✅11. 盛最多水的容器 典型的左右指针 🌟🌟
✅26. 删除有序数组中的重复项 🌟
✅27. 移除元素 🌟
❌42. 接雨水 🌟🌟🌟
✅75. 颜色分类 除了左右指针还需要中间变量帮助遍历数组 🌟🌟
✅82. 删除排序链表中的重复元素 II 左右指针 🌟🌟
✅86. 分隔链表 注意要将链表最后的指针指向None 🌟🌟
✅283. 移动零 🌟
✅344. 反转字符串 🌟
❌407. 接雨水 II 🌟🌟🌟

滑动窗口算法是一种基于双指针的算法，通常用于解决字符串和数组相关的问题。其基本思想是维护一个固定大小的窗口，通过移动窗口的左右边界来寻找目标值。

  • 窗口的大小：窗口的大小通常是固定的，可以根据问题要求进行调整。
  • 窗口的移动：窗口的移动是通过移动左右指针来实现的。左指针通常指向窗口的起始位置，右指针指向窗口的结束位置。
  • 窗口的维护：在移动窗口的过程中，需要维护窗口中的元素，可以使用哈希表或者数组等数据结构来维护。
  • 窗口的更新：在窗口移动的过程中，需要更新窗口内的元素以及相关的数据结构。
  • 窗口的判断：在滑动窗口算法中，需要判断当前窗口是否满足题目要求，如果满足则更新结果，如果不满足则继续移动窗口。
  • 应用场景：滑动窗口算法通常用于求解最长子串、最短子串、子数组等问题。

时间复杂度：O(N)。虽然滑动窗口代码框架中有一个嵌套的 while 循环，但字符串/数组中的每个元素都只会进入窗口一次，然后被移出窗口一次，不会有某些元素多次进入和离开窗口，所以算法的时间复杂度就和字符串/数组的长度成正比。

初始化left = right = 0，把索引左闭右开区间[left, right)称为一个「窗口」，左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

def slidingWindow(s: str):
    window = {}
    left, right = 0, 0
    while right < len(s):
        # c 是将移入窗口的字符
        c = s[right]
        # 增大窗口
        right += 1
        # 进行窗口内数据的一系列更新
        ...

# debug 输出的位置
        # 注意在最终的解法代码中不要 print
        # 因为 IO 操作很耗时，可能导致超时
        print("window: [{}, {})".format(left, right))

# 判断左侧窗口是否要收缩
        while window needs shrink:
            # d 是将移出窗口的字符
            d = s[left]
            # 缩小窗口
            left += 1
            # 进行窗口内数据的一系列更新
            ...
双指针——滑动窗口
题目 技巧 难度
✅3. 无重复字符的最长子串 没啥好说的，直接AC 🌟🌟
✅76. 最小覆盖子串 需要用字典defaultdict(int)记录 🌟🌟🌟
❌187. 重复的DNA序列 需要位运算，到时候在做一遍 🌟🌟
✅209. 长度最小的子数组 没啥好说的，直接AC 🌟🌟
✅219. 存在重复元素 II 固定一个k大小的窗口 🌟
❌220. 存在重复元素 III 需要使用有序集合 🌟🌟🌟
❌239. 滑动窗口最大值 仍然需要借助特殊数据结构 🌟🌟🌟
✅438. 找到字符串中所有字母异位词 注意缩小窗口时更新valid方式 🌟🌟
✅567. 字符串的排列 前面几个会了这个闭眼写 🌟🌟
  • 简介：二分查找也叫折半查找，是一种在有序数组中查找目标元素的算法。该算法每次查找时将目标值与数组中间位置的元素进行比较，如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找；如果目标值等于中间元素，则直接返回中间位置的元素下标。通过不断地将查找范围缩小一半，最终找到目标元素或者确认目标元素不存在于数组中。
  • 时间复杂度：O(logn)，其中n表示数组的长度。因为每次查找可以将查找范围缩小一半，所以最多需要查找logn次。
  • 前提条件：数组必须是有序的。因为二分查找是通过比较目标元素和数组中间位置的元素来确定查找范围的，如果数组是无序的，那么就无法保证每次缩小查找范围。
  • 局限性：只能用于查找有序数组中的元素。如果数据不是有序的，需要先进行排序，时间复杂度会变为O(nlogn)；另外，二分查找也无法处理数组中存在重复元素的情况，需要使用变体来处理。
def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # 防止left+right太大导致溢出，python中不会有这个问题
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        elif nums[mid] == target:
            return mid  # 直接返回索引
            # left = mid + 1   # 如果寻找target的索引右边界，缩小左边界
            # right = mid - 1  # 如果寻找target的索引左边界，缩小右边界
    return -1
    # # 如果寻找target的索引右边界，判断右边界是否越界
    # if right < 0 or nums[right] != target:
    #     return -1
    # # 如果寻找target的索引左边界，判断左边界是否越界
    # if left >= len(nums) or nums[left] != target:
    #     return -1
二分查找
题目 技巧 难度
❌4. 寻找两个正序数组的中位数 🌟🌟🌟
✅33. 搜索旋转排序数组 判断哪部分有序再二分 🌟🌟
✅34. 在排序数组中查找元素的第一个和最后一个位置 两次二分查找左右边界 🌟🌟
✅35. 搜索插入位置 典型二分 🌟
✅69. x 的平方根 注意判断返回边界 🌟
✅74. 搜索二维矩阵 二维转换为一维进行二分 🌟🌟
✅81. 搜索旋转排序数组 II 多处理一步：缩小相等边界 🌟🌟
✅153. 寻找旋转排序数组中的最小值 注意处理边界 🌟🌟
✅154. 寻找旋转排序数组中的最小值 II 多处理一步：缩小相等边界 🌟🌟🌟
✅162. 寻找峰值 假设nums[n]=-inf 🌟🌟
✅240. 搜索二维矩阵 II 矩阵以右上角为起点为二叉搜索树，z字查找 🌟🌟
✅1167. 两数之和 II - 输入有序数组 求和问题都可以转换为二分查找target-其中一个数 🌟🌟

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK