公路水运建设质量安全监督网站,郑州定制网站建设,h5网站怎么做的,开发公司补偿物业公司物业费协议欢迎大家订阅【蓝桥杯Python每日一练】 专栏#xff0c;开启你的 Python数据结构与算法 学习之旅#xff01; 文章目录 前言1 同向扫描2 反向扫描3 同向扫描与反向扫描的对比4 例题分析2.1 回文判定2.2 美丽的区间2.3 挑选子串 前言
双指针是一种常用于数组和链表类问题中开启你的 Python数据结构与算法 学习之旅 文章目录 前言1 同向扫描2 反向扫描3 同向扫描与反向扫描的对比4 例题分析2.1 回文判定2.2 美丽的区间2.3 挑选子串 前言
双指针是一种常用于数组和链表类问题中指的是用两个指针在问题的输入数据结构中进行遍历。根据应用的场景和指针的运动方向双指针可以分为同向扫描和反向扫描两种类型。
1 同向扫描
同向扫描指的是两个指针从同一位置或相近的位置开始向相同的方向移动。常见的应用场景包括
滑动窗口问题通过一个窗口的左右边界来实现对区间的处理。寻找数组中满足某些条件的子数组。合并两个已排序的数组例如合并两个有序链表。
优点
使用双指针的技术可以在 O(n) 时间内完成遍历。避免了暴力搜索的 O(n²) 时间复杂度。 2 反向扫描
反向扫描指的是两个指针从不同的位置开始分别向相反的方向移动。这种方法通常用于
排序问题寻找两个数的和等于某个目标值通常应用于已排序的数组。双端队列问题需要同时从两端处理数据的场景。快排快速排序算法通过反向扫描来处理左右子数组的元素。
优点
反向扫描减少了重复计算快速找到符合条件的解。适用于有序数据结构的情境利用有序性减少搜索空间。 3 同向扫描与反向扫描的对比
特性同向扫描Same Direction反向扫描Opposite Directions初始位置两个指针通常从相同的地方开始例如同一个位置或相邻位置两个指针通常从相反的地方开始例如数组的两端指针移动方向指针沿着相同的方向逐步推进两个指针沿相反方向逐步推进应用场景滑动窗口问题、子数组和问题、数组合并等排序数组中寻找目标和、快排、双端队列等复杂度O(n)可以高效处理多个子数组和的情况O(n)适用于排序数组和快速排除不符合条件的解 4 例题分析
2.1 回文判定 题目地址https://www.lanqiao.cn/problems/1371/learning/
样例输入
abcba样例输出
Y【示例代码】
s input()
# 初始化左右指针 l 和 rl 指向字符串的开始r 指向字符串的结束
l, r 0, len(s) - 1
ok Y
# 循环直到左右指针交错即 l r
while l r: # 如果左右指针对应的字符相等if s[l] s[r]: l 1 # 左指针向右移动r - 1 # 右指针向左移动else: # 如果ok N break
print(ok)
【运行结果】
2.2 美丽的区间 题目地址https://www.lanqiao.cn/problems/1372/learning/
样例输入
5 6
1 2 3 4 5样例输出
2【示例代码】
# 读取两个整数 n 和 S。n 是数组的长度S 是最小和的阈值
n, S map(int, input().split())
# 读取一个数组 a数组的长度是 n包含 n 个整数
a list(map(int, input().split())) # 初始化左右指针均指向数组的开始位置
left, right 0, 0
# 初始化 tot 变量为 0用于记录当前区间 [left, right) 的和
tot 0
# 初始化 min_len 为 n1一个大于数组长度的值用于记录最小子数组长度
min_len n 1 # 进入循环通过左指针遍历每个子数组的起始位置
while left n:# 不断拓展右端点直到子数组的和大于或等于 Swhile right n and tot S:tot a[right] # 将右端点元素加入 totright 1 # 右端点向右移动# 如果当前区间的和满足大于或等于 Sif tot S:# 更新最小长度right - left 是当前区间的长度min_len min(min_len, right - left) # 左端点右移一位缩小区间继续寻找下一个合法区间# 将左端点元素从 tot 中移除tot - a[left] # 左端点右移left 1 # 如果没有找到满足条件的子数组min_len 会保持为 n1
if min_len n 1:min_len 0 # 如果没有找到合法区间设置 min_len 为 0# 输出最小子数组长度
print(min_len)
【执行流程】 ①初始化
n 5S 6。a [1, 2, 3, 4, 5]。left 0right 0。tot 0min_len n 1 6。
②循坏处理
第一轮left 0
进入 while left n 循环。内层 while right n and tot S 开始 right 0tot 0tot S因此进入循环 tot a[0] 0 1 1right 1right 1。 right 1tot 1tot S继续循环 tot a[1] 1 2 3right 1right 2。 right 2tot 3tot S继续循环 tot a[2] 3 3 6right 1right 3。 right 3tot 6此时 tot S跳出内层循环。 tot S 时更新 min_len min_len min(min_len, right - left) min(6, 3 - 0) 3。 然后缩小区间tot - a[0] 6 - 1 5left 1left 1。
第二轮left 1
进入 while left n 循环。内层 while right n and tot S 继续执行 right 3tot 5tot S继续循环 tot a[3] 5 4 9right 1right 4。 right 4tot 9此时 tot S跳出内层循环。 tot S 时更新 min_len min_len min(min_len, right - left) min(3, 4 - 1) 3。 然后缩小区间tot - a[1] 9 - 2 7left 1left 2。
第三轮left 2
进入 while left n 循环。内层 while right n and tot S 继续执行 right 4tot 7tot S继续循环 tot a[4] 7 5 12right 1right 5。 right 5tot 12此时 tot S跳出内层循环。 tot S 时更新 min_len min_len min(min_len, right - left) min(3, 5 - 2) 3。 然后缩小区间tot - a[2] 12 - 3 9left 1left 3。
第四轮left 3
进入 while left n 循环。内层 while right n and tot S 不再执行因为 right 已经达到数组的末尾。tot S 时更新 min_len min_len min(min_len, right - left) min(3, 5 - 3) 2。 然后缩小区间tot - a[3] 9 - 4 5left 1left 4。
第五轮left 4
进入 while left n 循环。内层 while right n and tot S 不再执行因为 right 已经达到数组的末尾。此时min_len 2退出外层循环。
③结果输出 最终 min_len 2即最小的子数组长度为 2。
【运行结果】
2.3 挑选子串 题目地址https://www.lanqiao.cn/problems/1621/learning/
样例输入
7 4 2
4 2 7 7 6 5 1样例输出
18【示例代码】
# 读取三个整数 n (数组长度), m (阈值), k (至少有 k 个数 m)
n, m, k map(int, input().split())
# 读取数组 a包含 n 个整数
a list(map(int, input().split()))
# 初始化左右指针均指向数组的起始位置
left, right 0, 0 ans 0 # 用来记录满足条件的子数组数量
cnt 0 # 记录当前窗口中大于等于 m 的元素个数# 主循环左指针从0到n遍历数组
while left n:# 内循环扩展右指针直到窗口中有至少 k 个元素大于等于 mwhile right n and cnt k:if a[right] m: # 如果右指针指向的元素大于等于 mcnt 1 # 计数窗口中大于等于 m 的元素数量right 1 # 右指针向右移动扩大窗口# 当窗口中有至少 k 个大于等于 m 的元素时if cnt k:# 计算从 left 到 right-1 的子数组的数量# 窗口为 [left, right-1][left, right], [left, right1], ..., [left, n-1]这些子数组都满足条件ans n - right 1 # right 已经移动到不满足条件的位置所有从 left 到 [right, n-1] 的子数组都满足条件# 向右移动左指针缩小窗口准备进入下一轮if a[left] m: # 如果左指针指向的元素大于等于 mcnt - 1 # 移除左边界元素更新窗口中大于等于 m 的元素数量left 1 # 左指针右移# 输出满足条件的子数组数量
print(ans)
【执行流程】
①初始化 left 0, right 0, cnt 0, ans 0
②循坏处理 第一轮外循环 (left 0)
内循环拓展右指针直到 cnt 2 right 0: a[right] 4 4, cnt 1right 1: a[right] 2 4, cnt 1right 2: a[right] 7 4, cnt 2 → 窗口 [0, 2] 满足条件。 当前 cnt 2 2则有 n - right 1 7 - 3 1 5 个符合条件的子数组ans 5。左指针右移left 1cnt 减少 1。
第二轮外循环 (left 1)
内循环继续拓展右指针直到 cnt 2 right 3: a[right] 7 4, cnt 3 → 窗口 [1, 3] 满足条件。 当前 cnt 3 2则有 n - right 1 7 - 4 1 4 个符合条件的子数组ans 5 4 9。左指针右移left 2cnt 减少 1。
第三轮外循环 (left 2)
内循环继续拓展右指针直到 cnt 2 right 4: a[right] 6 4, cnt 3 → 窗口 [2, 4] 满足条件。 当前 cnt 3 2则有 n - right 1 7 - 5 1 3 个符合条件的子数组ans 9 3 12。左指针右移left 3cnt 减少 1。
第四轮外循环 (left 3)
内循环继续拓展右指针直到 cnt 2 right 5: a[right] 5 4, cnt 3 → 窗口 [3, 5] 满足条件。 当前 cnt 3 2则有 n - right 1 7 - 6 1 2 个符合条件的子数组ans 12 2 14。左指针右移left 4cnt 减少 1。
第五轮外循环 (left 4)
内循环继续拓展右指针直到 cnt 2 right 6: a[right] 1 4, cnt 2 → 窗口 [4, 6] 满足条件。 当前 cnt 2 2则有 n - right 1 7 - 7 1 1 个符合条件的子数组ans 14 1 15。左指针右移left 5cnt 减少 1。
第六轮外循环 (left 5)
右指针不再需要移动cnt 少于 k继续右移左指针直到遍历结束。
③最终输出
18【运行结果】
