LCS问题和LIS问题

发表于 2022-04-10 更新于 2024-03-25

问题描述

LCS问题就是最长公共子序列问题，即给定一个数组 target 和另一个数组 arr ，要求返回最长公共子序列的长度。特别地，当 target中没有重复的元素时，这个问题等价于求最长上升子序列问题，即LIS问题。

例题

LeetCode 1713. 得到子序列的最少操作次数

给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ， arr 可能包含重复元素。

每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。

请你返回最少操作次数，使得 target 成为 arr 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4]的子序列（加粗元素），但 [2,4,2]不是子序列。

示例 1：

1
2
3

输入： target = [5,1,3], arr = [9,4,2,3,4]
输出： 2
解释： 你可以添加5和1，使得 arr 变为 [5,9,4,1,2,3,4]，target 为 arr 的子序列

示例 2：

1 2	输入： target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1] 输出: 3

题解

首先，我们不难发现，最终需要返回的结果就是 target 数组的长度和两个数组的最长公共子序列的长度的差，即LCS问题。

一般上来说，使用动态规划解决LCS问题需要复杂度为 O(n*m) （定义dp[i][j] 为target 前 i 项和 arr 前 j 项的公共子序列长度）。

但是由于target 数组是无重复的，我们可以将这一问题转化为LIS问题。我们首先建立target 数组中的元素和下标的一一映射关系，存储在哈希表中。然后遍历 arr 数组，找到 arr 数组中全部与 target 重复的元素，并将其下标记录在一个新的数组 vec 中。这样，我们只要找到 vec 数组的最大升序子序列即可。

使用动态规划暴力解决LIS问题需要的复杂度为 O(n²) （定义 dp[i] 为以 vec[i] 结尾的最长上升子序列的长度，每次计算 dp[i] 需要遍历一次 dp[0] ~ dp[i-1] ，并判断 vec[i] 是否可以接在后面， dp[i] 是其中的最大值）。

而使用贪心法，我们可以将求解LIS问题的复杂度降低到 O(nlogn) 。我们可以维护一个贪心数组 g ，定义 g[i] 为长度为 i 的公共子序列的最小结尾元素。可以证明，g[i] 是单调递增的 ~~（但是我不会证）~~ 。因为我们是从左往右扫描 vec 数组的，所以越小的结尾元素能让越多的后续元素接上。我们只要保存最小的结尾元素，就可以保证找到最长的升序子序列（的长度）。

举个例子，对于 vec = [6,7,0,0,2,0,2,6,7] 来说：

将 6 加入到数组 g中。此时 g[1] = 6
将 7 与 g 的最后一个元素比较，发现 7 > 6 ，所以直接将 7 放入数组 g 中。此时 g[1] = 6 , g[2] = 7
将 0 与 g 的最后一个元素比较，发现 0 < 7 ，所以长度为 1 的子序列的最小结尾元素是 0，我们更新 g[1] 为 0 。此时 g[1] = 0 , g[2] = 7 。
将 0 与 g 的最后一个元素比较，发现 0 < 7 ，所以长度为 1 的子序列的最小结尾元素是 0，g 保持不变。此时 g[1] = 0 , g[2] = 7 。
将 2 与 g 的最后一个元素比较，发现 2 < 7 ，所以长度为 2 的子序列的最小结尾元素是 2，我们更新 g[2] 为 2 。此时 g[1] = 0 , g[2] = 2 。
将 0 与 g 的最后一个元素比较，发现 0 < 2 ，所以长度为 1 的子序列的最小结尾元素是 0，g 保持不变。此时 g[1] = 0 , g[2] = 2 。
将 2 与 g 的最后一个元素比较，发现 2 = 2 ，所以长度为 2 的子序列的最小结尾元素是 2，g保持不变。此时g[1] = 0 , g[2] = 2 。
将 6 与 g 的最后一个元素比较，发现 6 > 2 ，所以直接将 6 放入数组 g 中。此时 g[1] = 0 , g[2] = 2 , g[3] = 6 。
将 7 与 g 的最后一个元素比较，发现 7 > 6 ，所以直接将 7 放入数组 g 中。此时 g[1] = 0 , g[2] = 2 , g[3] = 6 , g[4] = 7 。
遍历完毕，此时数组 g 的长度为 4 ，说明 vec 的最长升序子序列的长度为 4 。

当扫描到的 vec[i] 小于数组 g 最后一个元素时，我们应该找到数组 g 中大于 vec[i] 的最小值，并更新这个值为 vec[i] 。由于数组 g 是单调递增的，所以我们可以使用二分查找的方法来找到待更新的值，以达到 O(logn) 的查找复杂度。

代码：

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr){
        //建立一个target元素和下标的映射
        unordered_map<int,int> map;
        for(int i=0;i<target.size();i++) map[target[i]]=i;
        //找到arr和target中的重复元素，并用下标表示。
        vector<int> vec;
        for(int i : arr){
            if(map.count(i)>0) vec.push_back(map[i]);
        }
        int n=vec.size();
        if(n==0) return target.size();//特殊处理，如果没有重复元素就直接返回。
        vector<int> dp;
        dp.push_back(vec[0]);//初始化。
        for(int i=1;i<n;i++){
            if(vec[i]>dp[dp.size()-1]) dp.push_back(vec[i]);
            else{
                //开始二分查找
                int l=0;
                int r=dp.size()-1;
                while(l<r){
                    int mid=(l+r)/2;
                    if(dp[mid]<vec[i]) l=mid+1;
                    else if(dp[mid]==vec[i]) l=r=mid;
                    else r=mid;
                }
                //找到第一个大于vec[i]的元素，其下标为l。
                dp[l]=vec[i];//数组中的最小末尾元素。
            }
        }
        return target.size()-dp.size();
    }
};

有的没的

小黄鸭调试法

小黄鸭调试法是软件工程中使用的调试代码方法之一。就是在程序的调试、纠错或测试过程中，耐心地向小黄鸭解释每一行程序的作用，以此来激发灵感。

将自己学会的东西记录在Blog里，在写博文的过程中就知道什么东西自己已经掌握了，什么东西自己还没搞懂。

启真湖边的小鸭鸭

没事听点歌（Taylor Swift - Forever & Always）

树状数组

发表于 2022-04-07 更新于 2022-04-20

概述

树状数组是用数组来模拟树型结构的一种数据结构，它的优势在于它可以以 O(log n) 的时间复杂度对一个数组进行单点修改和区间求和。普通的数组单点修改的时间复杂度是 O(1) ，区间求和的时间复杂度是 O(n) ，差分数组单点修改的时间复杂度是 O(n)，区间求和的复杂度是 O(1) 。树状数组则将单点修改和区间求和的复杂度都限制在了可以接受的范围内，平均意义上效率更高。

原理

对于原数组 A[i] ，维护一个辅助数组（也就是树状数组） C[i] ，使 C[i] = A[i-2^k+1] + A[i-2^k+2] + ... + A[i] ，其中 k 是 i 的二进制中最低位到最高位连续零的长度。

例如：

C[1] = A[1];
C[2] = A[1] + A[2];
C[3] = A[3];
C[4] = A[1] + A[2] + A[3] + A[4];
C[5] = A[5];
C[6] = A[5] + A[6];
C[7] = A[7];
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

通过这种方法我们可以把数组中若干个单点的和集中起来访问和维护，以达到更高的效率。

代码实现

lowbit：找到一个数的二进制表示中最低位的1

1
2
3

int lowbit(int x){
    return x & -x;
}

单点修改

void add(int index,int val){
    //为下标为index的元素增加val的值
    for(int i=index;i<=n;i+=lowbit(i)){
        c[index] += val;
    }
    a[index] += val;
}

区间求和

int getsum(int index){
    //求A[1]到A[index]的和
    int res=0;
    for(int i=index;i>0;i-=lowbit(i)){
        res += c[i];
    }
    return res;
}

例题

LeetCode 307. 区间和检索 - 数组可修改

题目描述：

给你一个数组 nums ，请你完成两类查询。

1. 其中一类查询要求更新数组 nums 下标对应的值

2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums)用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（包含）的 nums 元素的和 (即, nums[left] + nums[left + 1] + ... + nums[right])

示例1：

输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

题解：

class NumArray {
private:
    vector<int> tree;
    vector<int> nums;
    int lowbit(int x){
        return x & -x;
    }
    int query(int x){
        int ans=0;
        for(int i=x;i>0;i-=lowbit(i)) ans+=tree[i];
        return ans;
    }
    void add(int x, int num){
        for(int i=x;i<tree.size();i+=lowbit(i)) tree[i]+=num;
        return;
    }
public:
    NumArray(vector<int>& nums) {
        this->nums=nums;
        int n=nums.size();
        this->tree.resize(n+1);
        for(int i=0;i<nums.size();i++) add(i+1,nums[i]);
    }

    void update(int index, int val) {
        add(index+1,val-nums[index]);
        nums[index]=val;
    }

    int sumRange(int left, int right) {
        return query(right+1)-query(left);
    }
};

Hello!

发表于 2022-04-06 更新于 2022-04-08

int main(){
    //This is my blog. I created it on 2022/4/6.
    //你好，这是我的博客。
    cout << "hello, world!";
}