分享｜双序列双指针

14 小时前

发布于河南

双指针 C C++Java Python3 算法和数据结构

双序列双指针

单序列双指针主要分为：双指针和判断子序列

核心思想

双序列双指针涉及到两个独立的序列（通常是两个数组或两个字符串），并在每个序列上各放置一个指针，通过两个指针的协同移动来解决问题。

双指针

题目一

来源：力扣2109. 向字符串添加空格

给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。

数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值之前。

例如，s = "EnjoyYourCoffee" 且 spaces = [5, 9] ，那么我们需要在 'Y' 和 'C' 之前添加空格，这两个字符分别位于下标 5 和下标 9 。因此，最终得到 "Enjoy Your Coffee" 。

请你添加空格，并返回修改后的字符串。

思路

初始化 $j = 0$ 。遍历 $s$ ，把 $s [i]$ 加到答案中。如果 $s p a ces [j]$ 等于当前下标 $i$ ，那么先加空格，再加 $s [i]$ ，然后把 $j$ 加一。

代码实现

Python

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        ans = []
        j, n = 0, len(spaces)
        for i, c in enumerate(s):
            if j < n and i == spaces[j]:
                ans.append(" ")
                j += 1
            ans.append(c)

        return "".join(ans)

Python特殊解法

Python

class Solution:
    def addSpaces(self, s: str, spaces: List[int]) -> str:
        s = list(s)
        for i in spaces:
            s[i] = ' ' + s[i]
            
        return ''.join(s)

题目二

来源：力扣88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

思路

由于数组已按非递减顺序排列，可以使用双指针，初始化 $i = j = 0$ ， $i$ 指向 $n u m s 1$ 最前端， $j$ 指向 $n u m s 2$ 最前端，

创建一个中间数组， $i 、 j$ 指向中谁小就把谁加进中间数组。最后把中间数组的值赋给 $n u m s 1$ 即可。

优化一

倒序双指针，从右往左地把 $n u m s 2$ 合并到 $n u m s 1$ 中。

代码实现

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        res = []
        i = j = 0

        while i < m and j < n:
            if nums1[i] < nums2[j]:
                res.append(nums1[i])
                i += 1
            else:
                res.append(nums2[j])
                j += 1

        if i < m:
            res.extend(nums1[i:m])
        if j < n:
            res.extend(nums2[j:n])

        nums1[:] = res

Python优化一

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        j1, j2, i = m - 1, n - 1, m + n - 1
        while j2 >= 0:
            if j1 >= 0 and nums1[j1] > nums2[j2]:
                nums1[i] = nums1[j1]
                j1 -= 1
            else:
                nums1[i] = nums2[j2]
                j2 -= 1

            i -= 1

题目三

来源：力扣809. 情感丰富的文字

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 s = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = s。

输入一组查询单词，输出其中可扩张的单词数量。

思路

我们可以依次判断数组 $w or d s$ 中的每一个字符串是否可以扩张成给定的字符串 $s$ 。

假设我们需要判断 $t$ 是否可以扩张成 $s$ ，我们可以使用双指针来解决这个问题。两个指针 $i$ 和 $j$ 初始时分别指向字符串 $s$ 和 $t$ 的首个位置。在双指针遍历的过程中：

首先我们需要保证 $s [i] = t [j]$ ，否则这两部分不是相同的字母，无法进行扩张；

随后我们不断地向右移动两个指针，直到移动到与之前不同的字母，或者超出字符串的边界。假设字符串 $s$ 有 $c n t_{i}$ 个相同的字母， $t$ 有 $c n t_{j}$ 个相同的字母，那么我们必须保证 $c n t_{i} \geq c n t_{j}$ ，因为扩张不可能减少字符的数量。当 $c n t_{i} = c n t_{j}$ 时，我们无需进行扩张，这样也是满足要求的； $c n t_{i} > c n t_{j}$ ，由于扩张至少会达到长度 $3$ 及以上，因此需要保证 $c n t_{i} \geq 3$ 即可。

当某一个指针超出边界时，我们就可以退出上述的遍历过程。此时，如果另一个指针也超出边界，说明两个字符串同时遍历完成，即 $t$ 可以扩张成 $s$ 。

代码实现

Python

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        ans, n = 0, len(s)

        for w in words:
            i, j, m = 0, 0, len(w)
            while i < n and j < m:
                if s[i] != w[j]:
                    break

                cnt1 = cnt2 = 1
                while i + 1 < n and s[i + 1] == s[i]:
                    cnt1, i = cnt1 + 1, i + 1
                while j + 1 < m and w[j + 1] == w[j]:
                    cnt2, j = cnt2 + 1, j + 1

                if cnt1 < cnt2 or cnt1 < 3 and cnt1 != cnt2:
                    break

                i, j = i + 1, j + 1

            ans += i == n and j == m

        return ans

题目四

来源：力扣777. 在 LR 字符串中交换相邻字符

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 result，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 result 时，返回 True。

思路

替换操作可以转换成，把 $L$ 往左移动（需要左边是 $X$ ），把 $R$ 往右移动（需要右边是 $X$ ）。

那么无论怎么移动，由于 $L$ 和 $R$ 无法互相穿过对方，那么去掉 $X$ 后的剩余字符应该是相同的，否则返回 $f a l se$ 。

然后用双指针遍历 $s t a r t [i]$ 和 $t a r g e t [j]$ ，分类讨论：

如果当前字符为 $L$ 且 $i < j$ ，那么这个 $L$ 由于无法向右移动，返回 $f a l se$ ；
如果当前字符为 $R$ 且 $i > j$ ，那么这个 $R$ 由于无法向左移动，返回 $f a l se$ 。
遍历完，若中途没有返回 $f a l se$ 就返回 $t r u e$ 。

代码实现

Python

class Solution:
    def canTransform(self, start: str, result: str) -> bool:
        i, j = 0, 0
        n = len(start)

        while i < n or j < n:
            while i < n and start[i] == "X":
                i += 1
            while j < n and result[j] == "X":
                j += 1

            if i < n and j < n:
                if start[i] != result[j]:
                    return False
                if start[i] == "L" and i < j:
                    return False
                if start[i] == "R" and i > j:
                    return False

            elif i < n or j < n:
                return False

            i += 1
            j += 1

        return True

判断子序列

题目一

来源：力扣392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

思路

我们可以遍历 $t$ ，在遍历的过程中看能否匹配 $s$ 的每个字母。按照子序列的定义，在遍历 $t$ 的过程中，把没匹配到的字母删除，剩下的就是匹配的字母，即字符串 $s$ ，这就说明 $s$ 是 $t$ 的子序列。

代码实现

python写法一

python写法二

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1

            j += 1

        return i == len(s)

题目二

来源：力扣522. 最长特殊序列 II

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

s 的 子序列可以通过删去字符串 s 中的某些字符实现。

例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。

思路

如果短的子序列是「独有子序列」，那么更长的子序列也会是「独有子序列」。或者说，子序列越长，越不可能是其它字符串的子序列。所以只需要枚举字符串 $s = s t rs [i]$ ，判断 $s$ 是否为其它字符串的子序列，如果不是，则用 $s$ 的长度更新答案的最大值。

代码实现

C++

Python

class Solution {
    // 判断 s 是否为 t 的子序列
    bool isSubseq(string& s, string& t) {
        int i = 0;
        for (char c : t) {
            if (s[i] == c && ++i == s.length()) { // 所有字符匹配完毕
                return true; // s 是 t 的子序列
            }
        }
        return false;
    }

public:
    int findLUSlength(vector<string>& strs) {
        int ans = -1;
        for (int i = 0; i < strs.size(); i++) {
            if ((int) strs[i].length() <= ans) { // 不会让 ans 变大
                continue;
            }
            for (int j = 0; j < strs.size(); j++) {
                if (j != i && isSubseq(strs[i], strs[j])) {
                    goto next; // 枚举下一个 i
                }
            }
            ans = strs[i].length();
            next:;
        }
        return ans;
    }
};