再谈双指针算法

上一篇双指针算法介绍了堆暴力枚举的优化，其实双指针算法思想在其他部分仍有很多的运用，这篇就双指针归并、子序列问题做一个归纳整理

模板

归并有序序列

• 假设有两个递增序列$A$和$B$，要求将他们合并为一个递增序列$C$

int merge (int A[], int B[], int C[], int n, int m) {
    int i = 0, j = 0, index = 0;
    while (i < n && j < m) {
        if (A[i] <= B[i])
            c[index++] = A[i++];
        else
            C[index++] = B[j++];
    }
    while (i < n)
        C[index++] = A[i++];
    while (j < m)
        C[index++] = B[j++];
    return index;
}

判断子序列

给定一个长度为$n$的整数序列$a_{1},a_{2},…,a_{n}$，以及一个长度为$m$的整数序列$b_{1},b_{2},…,b_{m}$。请你判断$a$序列是否为$b$序列的子序列。子序列指序列的一部分项按原有次序排列而得的序列，例如序列$a_{1},a_{3},a_{5}$是序列$a_{1},a_{2},a_{3},a_{4},a_{5}$的一个子序列

bool check(int A[], int B[], int n, int m) {
    int i = 0, j = 0;
    while (j < m) {
        if (A[i] == B[j])
            i++;
        j++;
    }
    return i == n;
}

合并两个有序数组

• LeetCode84题：合并两个有序数组

给你两个有序整数数组$nums1$和$nums2$，请你将$nums2$合并到$nums1$中，使$nums1$成为一个有序数组。说明：初始化$nums1$和$nums2$的元素数量分别为$m$和$n$。你可以假设$nums1$有足够的空间（空间大小大于或等于 $m + n$）来保存$nums2$中的元素。示例:

输入

$nums1 = [1,2,3,0,0,0], m = 3$

$nums2 = [2,5,6], n = 3$

输出

$[1,2,2,3,5,6]$

• 为了不造成额外数组开销，我们需要反向使用双指针算法

• 如果$p1$先走到$0$，$nums2$数组还没有归并完，直接将$nums2$数组中剩下的覆盖到$nums1$数组中即可

• 如果$p2$先走到$0$，那么$p1$前面已经有序，便可结束无需再归并

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2])
                nums1[p--] = nums1[p1--];
            else 
                nums1[p--] = nums2[p2--];
        }
        while (p2 >= 0)
            nums1[p--] = nums2[p2--];
    }
};

通过删除字母匹配到字典里最长单词

• LeetCode524题：通过删除字母匹配到字典里最长单词

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

输入

$s = abpcplea,\ d = [ale\ ,apple\ ,monkey\ ,plea]$

输出

$apple$

• 使用子序列的模板找到所有符合条件的字符串放进res里面
• 写比较函数，对答案进行排序，返回第一个即可

class Solution {
public:
    /**
     * @brief 比较函数：返回长度最长且字典顺序最小的字符串
     * @param a 
     * @param b 
     * @return true 
     * @return false 
     */
    static bool cmp(string &a, string &b) {
      if (a.size() != b.size())
          return a.size() > b.size();
      else
          return a < b;
    }

    string findLongestWord(string s, vector<string>& d) {
        if (d.empty())
            return "";
        vector<string> res;
        // 找到所有的情况
        for (string str : d) {
            int i = 0, j = 0;
            while (j < s.size()) {
                if (str[i] == s[j])
                    i++;
                j++;
            }
            if (i == str.size())
                res.push_back(str);
        }
        if (res.empty())
            return "";
        sort(res.begin(), res.end(), cmp);
        return res[0];
    }
};