如何巧妙地利用双指针求最小路径？

在计算机科学中，双指针技巧（Two Pointers Technique）是一种常用的算法技巧，尤其适用于处理有序数组或链表中的问题。它通过使用两个指针（或索引）在数据结构上进行遍历，从而达到优化时间复杂度的目的。在求解最小路径问题时，双指针技巧也可以大显身手。下面是一个使用双指针技巧求解最小路径的示例。

假设你有两个有序数组 A 和 B，需要找到两个元素，一个来自 A，一个来自 B，使得它们的和最接近目标值 target。这是一个典型的双指针应用场景。

双指针算法步骤

1. 初始化指针：

   • 一个指针 i 指向数组 A 的起始位置（即 0）。
   • 另一个指针 j 指向数组 B 的末尾位置（即 len(B) - 1）。

2. 遍历数组：

   • 计算当前指针所指位置的两个元素的和 current_sum = A[i] + B[j]。
   • 比较 current_sum 与 target 的差值，并更新最小差值及其对应的元素对。
   • 根据 current_sum 与 target 的比较结果，移动指针：
     • 如果 current_sum 小于 target，则移动 i 指针向右（即 i++），以增加和的值。
     • 如果 current_sum 大于 target，则移动 j 指针向左（即 j--），以减小和的值。
   • 重复上述步骤，直到两个指针交错。

代码示例

def find_closest_pair(A, B, target):
    i, j = 0, len(B) - 1
    closest_sum = float('inf')
    closest_pair = (None, None)
    
    while i < len(A) and j >= 0:
        current_sum = A[i] + B[j]
        
        # 更新最小差值及其对应的元素对
        if abs(current_sum - target) < abs(closest_sum - target):
            closest_sum = current_sum
            closest_pair = (A[i], B[j])
        
        # 移动指针
        if current_sum < target:
            i += 1
        elif current_sum > target:
            j -= 1
        else:
            break  # 如果 current_sum == target，直接返回结果
    
    return closest_pair

# 示例用法
A = [1, 4, 5, 7]
B = [10, 20, 30, 40]
target = 32
print(find_closest_pair(A, B, target))  # 输出 (7, 30)

解析

1. 初始化：指针 i 从数组 A 的起始位置开始，指针 j 从数组 B 的末尾位置开始。
2. 遍历和比较：通过使用双指针，逐步缩小搜索范围，以找到最接近目标值的元素对。
3. 时间复杂度：由于每次循环中至少有一个指针会移动，因此总的时间复杂度为 O(n + m)，其中 n 和 m 分别是数组 A 和 B 的长度。

这种方法不仅高效，而且简单明了，非常适合处理类似的问题。

话不多说，来上真题：

​

 区分黑球与白球[中等]

题目：

桌子上有 n 个球，每个球的颜色不是黑色，就是白色。

给你一个长度为 n 、下标从 0 开始的二进制字符串 s，其中 1 和 0 分别代表黑色和白色的球。

在每一步中，你可以选择两个相邻的球并交换它们。

返回「将所有黑色球都移到右侧，所有白色球都移到左侧所需的 最小步数」。

示例 1：

输入：s = "101"
输出：1
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "011"。
最开始，1 没有都在右侧，需要至少 1 步将其移到右侧。

示例 2：

输入：s = "100"
输出：2
解释：我们可以按以下方式将所有黑色球移到右侧：
- 交换 s[0] 和 s[1]，s = "010"。
- 交换 s[1] 和 s[2]，s = "001"。
可以证明所需的最小步数为 2 。

示例 3：

输入：s = "0111"
输出：0
解释：所有黑色球都已经在右侧。

提示：

• 1 <= n == s.length <= 105
• s[i] 不是 '0'，就是 '1'。

题目分析：

         题目意思就是把字符串内的所有1都放到右边，所有0都放到左边，那这里的话我们就可以利用一个双指针去遍历整个字符串s，相当于是快速排序的算法思路，左边去找1，找到之后停下；同时右边去找0，找到之后停下；然后两个指针指的元素交换位置，此时需要的步数就是      尾指针re减去头指针pr，即 re-pr；直到遍历到re==pr为止。

代码实现：

class Solution:
    def minimumSteps(self, s: str) -> int:
        n=len(s)
        s=list(s)
        if n==1: return 0
        pr,re=0,n-1
        ans=0
        while pr<re:
            while s[pr]=='0' and pr<re:
                pr+=1
            while s[re]=='1' and re>pr:
                re-=1
            ans+=(re-pr)
            s[pr],s[re]=s[re],s[pr]
            pr+=1
            re-=1
        return ans

 总结：

        这段代码的核心思想是通过双指针将字符串按照交替模式中 ‘0’ 和 ‘1’ 的位置进行交换，以达到最小步数的目的。详细解释如下：

1. 将输入字符串 s 转换为列表 s，并获取字符串的长度 n。
2. 如果输入字符串长度为 1，则直接返回 0。
3. 初始化两个指针 pr 和 re，分别指向字符串的开头和末尾。
4. 初始化变量 ans 记录最小步数。
5. 在 pr < re 的情况下，开始一个 while 循环：
   • 内层 while 循环将 pr 指向的元素为 ‘0’ 且 pr 小于 re 时，pr 向后移动，直到找到第一个不为 ‘0’ 的位置。
   • 内层 while 循环将 re 指向的元素为 ‘1’ 且 re 大于 pr 时，re 向前移动，直到找到第一个不为 ‘1’ 的位置。
   • 将 ans 增加 re - pr，即当前位置需要交换的步数。
   • 交换 pr 和 re 指向的元素，然后将 pr 前进一步，re 后退一步。
6. 最终返回 ans，即将字符串转换为 0101… 这种交替模式所需的最小步数。

​