2022-02-07每日刷题打卡

飞书——每日一题

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

这题用的是动态规划的知识点，不过是二维的动态规划。

先看这个图，我们以一个字符串的大小为行数，另一个字符串的大小做列数来做出这个二维数组，然后每次比较，如果当前遍历到的text1字符不和text2上字符相等，我们就从上方或前方取一个最大值赋在格子里，如果相等，就把斜上方的值+1赋在当前格子里，最后返回最右下角的格子即可。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n=text1.size(),m=text2.size();
        vector<vector<int>>v(n+1,vector<int>(m+1));

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(text1[i-1]==text2[j-1])v[i][j]=v[i-1][j-1]+1;
                else v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        return v[n][m];
    }
};

力扣——每日一题

1405. 最长快乐字符串

如果字符串中不含有任何 ‘aaa’，‘bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
s 中只含有 ‘a’、‘b’ 、‘c’ 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 “”。

示例 1：

输入：a = 1, b = 1, c = 7
输出：“ccaccbcc”
解释：“ccbccacc” 也是一种正确答案。

贪心解法，从数量最多的字符开始插入，当插入的数量为2时就换另一个字符插入，然后继续找数量最多的字符开始插入，以此往复得到的就是最长的快乐字符串。

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string str;
        int n=a+b+c,a_num=0,b_num=0,c_num=0;
        for(int i=0;i<n;i++)
        {
            if((a_num<2&&a>=b&&a>=c&&a>0)||(c_num==2&&a>=b&&a>0)||(b_num==2&&a>=c&&a>0))
            {
                a_num++;
                b_num=0;
                c_num=0;
                a--;
                str+='a';
            }
            else if((b_num<2&&b>=a&&b>=c&&b>0)||(c_num==2&&b>=a&&b>0)||(a_num==2&&b>=c&&b>0))
            {
                a_num=0;
                b_num++;
                c_num=0;
                b--;
                str+='b';
            }
            else if((c_num<2&&c>=b&&c>=a&&c>0)||(a_num==2&&c>=b&&c>0)||(b_num==2&&c>=a&&c>0))
            {
                a_num=0;
                b_num=0;
                c_num++;
                c--;
                str+='c';
            }
        }
        if(a_num>=3||b_num>=3||c_num>=3)str.pop_back();
        return str;
    }
};

6003. 移除所有载有违禁货物车厢所需的最少时间

给你一个下标从 0 开始的二进制字符串 s ，表示一个列车车厢序列。s[i] = ‘0’ 表示第 i 节车厢 不 含违禁货物，而 s[i] = ‘1’ 表示第 i 节车厢含违禁货物。

作为列车长，你需要清理掉所有载有违禁货物的车厢。你可以不限次数执行下述三种操作中的任意一个：

从列车 左 端移除一节车厢（即移除 s[0]），用去 1 单位时间。
从列车 右 端移除一节车厢（即移除 s[s.length - 1]），用去 1 单位时间。
从列车车厢序列的 任意位置 移除一节车厢，用去 2 单位时间。
返回移除所有载有违禁货物车厢所需要的 最少 单位时间数。

注意，空的列车车厢序列视为没有车厢含违禁货物。

示例 1：

输入：s = “1100101”
输出：5
解释：
一种从序列中移除所有载有违禁货物的车厢的方法是：

• 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
• 从右端移除一节车厢 1 次。所用时间是 1 。
• 移除序列中间位置载有违禁货物的车厢。所用时间是 2 。
  总时间是 2 + 1 + 2 = 5 。

一种替代方法是：

• 从左端移除一节车厢 2 次。所用时间是 2 * 1 = 2 。
• 从右端移除一节车厢 3 次。所用时间是 3 * 1 = 3 。
  总时间也是 2 + 3 = 5 。

5 是移除所有载有违禁货物的车厢所需要的最少单位时间数。
没有其他方法能够用更少的时间移除这些车厢。

动态规划解法，我们要找的是一个平衡点，因为同样的货物，全部从左边卸掉或全部从右边卸掉或一部分从左边卸掉一部分从右边卸掉所花费的时间是不一样的，我们要找的是用时最少的那个点，我们要进行两次dp，先是从右往左来一遍，再从左往右来一遍。我们先从右端开始卸货物，当遍历到的字符是1时，我们有两种选择，一是花费2点时间直接删掉它，二是花费从最右端到当前货物数*1的时间删掉它（前者是任何位置都可以删但是要花两点时间，后者是当当前货物在最外面的时候只用1点时间就可以删掉，但为了让当前货物在最外面，我们要把排在他前面的货物都删掉，这个时间也要算），我们从两个方法中取时间最短的那一种，当遍历到的字符是0时，我们不必删掉它，直接把上一个位置的值赋给当前位置即可。这就是第一遍dp，第二遍dp前先准备两个变量，一个res计算搬掉全部违禁货物所需的时间，一个ans记录从从往右搬掉货物的最短时间。然后开始第二次dp，我们从左往右遍历字符串，当遍历到1时，我们的计算方法和前者一样，要么搬运时间ans+2，要么是把从左开始到当前货物的货物都删掉，我们取最短的那个。然后记录一下res，res的值是左边所需时间+右边所需时间，左边所需时间就是ans，右边所需时间就是我们第一遍dp得到的，在计算res时同时维护最小值。当第二遍dp结束后返回res即可。

（这题虽是hard，但其实并不难，但周赛的时候我也确实没写出来，看来之后要多练练hard的题）

class Solution {
public:
    int minimumTime(string s) {
        int n=s.size();
        vector<int>dp(n+1);
        for(int i=n-1;i>=0;i--)
        {
            dp[i]=s[i]=='0'?dp[i+1]:min(dp[i+1]+2,n-i);
        }
        int res=dp[0],ans=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='1')
            {
                ans=min(i+1,ans+2);
                res=min(res,ans+dp[i+1]);
            }
        }
        return res;
    }
};