LeetCode第229场周赛

2021-02-21

5685. 交替合并字符串

给你两个字符串 word1word2 。请你从 word1 开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串

思路

模拟即可

代码


class Solution {
public:
    string mergeAlternately(string w, string w2) {
        string s="";
        int len1=w.size();
        int len2=w2.size();
        int i=0,j=0;
        int f=1;
        while(i<len1&&j<len2) {
            if(f) s+=w[i++],f=0;
            else s+=w2[j++],f=1;
        }
        while(i<len1) s+=w[i++];
        while(j<len2)s+=w2[j++];
        return s;
    }
};

5686. 移动所有球到每个盒子所需的最小操作数

难度中等 4

n 个盒子。给你一个长度为 n 的二进制字符串 boxes ,其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 的,而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中,你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意,操作执行后,某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ,其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

思路

预处理前缀和的前缀和,后缀和的后缀和,对于第 i 个盒子答案为:

pre[i-1]+aft[i+1]

代码

class Solution {
public:
    int pre[2010];
    int aft[2010];
    vector<int> minOperations(string b) {
        int len=b.size();
  
        for(int i=0;i<len;i++) {
            int x=b[i]-'0';
            if(!i)pre[i]=x;
            else pre[i]=pre[i-1]+x;
        }
        for(int i=len-1;i>=0;i--){
            int x=b[i]-'0';
           aft[i]=aft[i+1]+x;
        }
        for(int i=0;i<len;i++) {
            if(i)pre[i]+=pre[i-1];
        }
        for(int i=len-1;i>=0;i--){
            aft[i]+=aft[i+1];
        }
        vector<int>ans;
        for(int i=0;i<len;i++) {
            if(!i) ans.push_back(aft[i+1]);
            else ans.push_back(pre[i-1]+aft[i+1]);
        }
        return ans;
  
    }
};

5687. 执行乘法运算的最大分数

给你两个长度分别 nm 的整数数组 numsmultipliers** **,其中 n >= m ,数组下标 从 1 开始 计数。

初始时,你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作(从 1 开始 计数)中,需要:

  • 选择数组 nums 开头处或者末尾处 的整数 x
  • 你获得 multipliers[i] * x 分,并累加到你的分数中。
  • x 从数组 nums 中移除。

在执行 m 步操作后,返回 最大 分数

思路

f[i][j]: 定义为 剩余区间[i,j]的所有操作方案的集合 注:剩余
属性: 最大值

f[i][j]=\left\{\begin{matrix} & f[i+1][j]+w[i]*c[n-len] & 删除第i个 \\ & f[i][j-1]+w[j]*c[n-len] & 删除第j个 \\ \end{matrix}\right.

几个边界值分析:

len 为当前区间的长度最小值为:n-m+1,因为 dp 状态定义时为剩余区间的长度,最大值为 n

左区间端点为从 1 开始,右区间端点为 i+len-1,需保证右区间端点小于等于 n

非常重要的一个理解:

假设 n==m,当剩余区间长度为 1 时即代表是第 n-1 次操作,区间长度为 n-1 时代表第 1 次操作,

而 n!=m 时 总符合 当剩余区间长度为 len 时,为 n-len 次操作 比较难以理解是当 n 大于 m 时,枚举区间长度是

从 n-m+1 开始的,因为定义是剩余区间,即最小时是 m 次操作都进行完以后,剩余区间长度为 n-m+1。

状态转移如上述所示即可。

代码

class Solution {
public:

    //int f[1010][1010];

    int maximumScore(vector<int>& nums, vector<int>& mul) {
        int n=nums.size();
        int m=mul.size();
	//将无用区间进行删除 可以不删
        if(n>=m*2) {
            int i=m,j=n-m;
            while(j<n) nums[i++]=nums[j++];
            n=i;
        }
        vector<vector<int>> f(n + 2, vector<int>(n + 2));
        for(int len=n-m+1;len<=n;len++){//枚举剩余区间大小
            cout<<len<<'\n';
            for(int i=1;i+len-1<=n;i++) {//枚举左端点
                int j=i+len-1;//右端点
                f[i][j]=max(f[i+1][j]+nums[i-1]*mul[n-len],f[i][j-1]+nums[j-1]*mul[n-len]);
            }
        }

        return f[1][n];

    }
};

5688. 由子序列构造的最长回文串的长度

难度困难 2

给你两个字符串 word1word2 ,请你按下述方法构造一个字符串:

  • word1 中选出某个非空 子序列 subsequence1
  • word2 中选出某个非空 子序列 subsequence2
  • 连接两个子序列 subsequence1 + subsequence2 ,得到字符串。

返回可按上述方法构造的最长 回文串长度 。如果无法构造回文串,返回 0

字符串 s 的一个 子序列 是通过从 s 中删除一些(也可能不删除)字符而不更改其余字符的顺序生成的字符串。

回文串 是正着读和反着读结果一致的字符串。

思路

最长公共子序列

状态定义: f[i][j]代表第一个序列前 i 个字符和第二个序列前 j 个字符构成的所有方案的集合

属性 :最大值

状态转移

f[i][j]= \left\{\begin{matrix} & max(f[i-1][j],f[i][j-1]) & \\ & max(f[i+1][j-1]+1,f[i][j]) & s[i]==t[j]\\ \end{matrix}\right.

最长回文子序列

状态定义 f[i][j]: 区间[i,j]中所有回文子序列的方案数

属性:最大值

f[i][j]=\left\{\begin{matrix} & 1 & len==1 \\ & max(f[i+1][j],f[i][j-1]) & len>1且不要第i个字符或不要第j个字符取最大 \\ & max(f[i+1][j-1]+2,f[i][j]) & len >1且 s[i]==t[j]\\ \end{matrix}\right.

本题:

将任意一个字符串翻转后,先预处理出两个字符串各自的最长回文子序列,然后预处理出两个字符串的最长公共子序列,那么两个字符串组成的最长公关回文子序列即为:

前 i 个和倒数第 i 个为两个字符串的最长公共子序列,中间是两个最长回文子序列的最大值,组合一起即为总体最大值

代码

class Solution {
public:
    int f1[1010][1010],f2[1010][1010],f3[1010][1010];

    //处理最长回文子序列
    void work(string &s,int f[][1010]){
        int n=s.size();
        for(int len=1;len<=n;len++) {
            for(int i=1;i+len-1<=n;i++) {
                int j=i+len-1;
                if(len==1) f[i][j]=1;
                else {
                    f[i][j]=max(f[i+1][j],f[i][j-1]);
                    if(s[i]==s[j]) f[i][j]=max(f[i][j],f[i+1][j-1]+2);
                }
            }
        }
    }
  
    int longestPalindrome(string s, string t) {
  
        int n=s.size();
        int m=t.size();

        reverse(t.begin(),t.end());
        s=" "+s;
        t=" "+t;
        work(s,f2);
        work(t,f3);

        //处理最长公共子序列
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                f1[i][j]=max(f1[i-1][j],f1[i][j-1]);
                if(s[i]==t[j]) f1[i][j]=max(f1[i][j],f1[i-1][j-1]+1);
            }
        }

        //枚举两个分界点
        int ans=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(f1[i][j]) {
                    ans=max(ans,f1[i][j]*2+max(f2[i+1][n],f3[j+1][m]));
                }
            }
        }
        return ans;
    }
};

标题:LeetCode第229场周赛
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/02/21/1613890207291.html