Leetcode周赛

27.Leetcode周赛

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

返回 合并后的字符串 。

示例 1:

输入:word1 = “abc”, word2 = “pqr”
输出:“apbqcr”
解释:字符串合并情况如下所示:
word1: a b c
word2: p q r
合并后: a p b q c r
示例 2:

输入:word1 = “ab”, word2 = “pqrs”
输出:“apbqrs”
解释:注意,word2 比 word1 长,“rs” 需要追加到合并后字符串的末尾。
word1: a b
word2: p q r s
合并后: a p b q r s
示例 3:

输入:word1 = “abcd”, word2 = “pq”
输出:“apbqcd”
解释:注意,word1 比 word2 长,“cd” 需要追加到合并后字符串的末尾。
word1: a b c d
word2: p q
合并后: a p b q c d

提示:

1 <= word1.length, word2.length <= 100
word1 和 word2 由小写英文字母组成

class Solution {
     
public:
    string mergeAlternately(string word1, string word2) {
     
        int len1 = word1.size();
        int len2 = word2.size();
        int len = min(len1,len2);
        string s;
        for(int i=0;i<len;i++)
        {
     
            string w1=word1.substr(i,1);
            string w2 =word2.substr(i,1);
            //cout<<(w1+w2)<
            s=s+(w1+w2);
        }
        cout<<s<<endl;
        if(len1==len2) return s;
        else if(len1<len2)
        {
     
            //string s1 = word2.substr(0,len1-1);
            string s2 = word2.substr(len1,len2-1);
            return s+s2;
        }
        else
        {
     
            //string s1 = word1.substr(0,len2-1);
            string s2 = word1.substr(len2,len1-1);
            return s+s2;
        }
        
    }
};

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

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

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

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

示例 1:

输入:boxes = “110”
输出:[1,1,3]
解释:每个盒子对应的最小操作数如下:

  1. 第 1 个盒子:将一个小球从第 2 个盒子移动到第 1 个盒子,需要 1 步操作。
  2. 第 2 个盒子:将一个小球从第 1 个盒子移动到第 2 个盒子,需要 1 步操作。
  3. 第 3 个盒子:将一个小球从第 1 个盒子移动到第 3 个盒子,需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子,需要 1 步操作。共计 3 步操作。
    示例 2:

输入:boxes = “001011”
输出:[11,8,5,4,3,4]

提示:

n == boxes.length
1 <= n <= 2000
boxes[i] 为 ‘0’ 或 ‘1’

class Solution {
     
public:
    vector<int> minOperations(string boxes) {
     
        int len = boxes.length();
        vector<int> ans(len,0);
        for(int i=0; i< len ;i++)
        {
     
            for(int j=0;j< len ;j ++)
            {
     
                if(boxes[j]=='1')
                ans[i]+=abs(j-i);
            }
        }
        return ans;

    }
};

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

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

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

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

示例 1:

输入:nums = [1,2,3], multipliers = [3,2,1]
输出:14
解释:一种最优解决方案如下:
- 选择末尾处的整数 3 ,[1,2,3] ,得 3 * 3 = 9 分,累加到分数中。
- 选择末尾处的整数 2 ,[1,2] ,得 2 * 2 = 4 分,累加到分数中。
- 选择末尾处的整数 1 ,[1] ,得 1 * 1 = 1 分,累加到分数中。
总分数为 9 + 4 + 1 = 14 。

示例 2:

输入:nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
输出:102
解释:一种最优解决方案如下:
- 选择开头处的整数 -5 ,[-5,-3,-3,-2,7,1] ,得 -5 * -10 = 50 分,累加到分数中。
- 选择开头处的整数 -3 ,[-3,-3,-2,7,1] ,得 -3 * -5 = 15 分,累加到分数中。
- 选择开头处的整数 -3 ,[-3,-2,7,1] ,得 -3 * 3 = -9 分,累加到分数中。
- 选择末尾处的整数 1 ,[-2,7,1] ,得 1 * 4 = 4 分,累加到分数中。
- 选择末尾处的整数 7 ,[-2,7] ,得 7 * 6 = 42 分,累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102 。

提示:

  • n == nums.length
  • m == multipliers.length
  • 1 <= m <= 103
  • `m <= n <= 105```
  • -1000 <= nums[i], multipliers[i] <= 1000

class Solution {
     
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
     
        int len1 = nums.size();
        int len2 = multipliers.size();
        int f[1005][1005]={
     0};
        for(int i=1;i<=len2;i++)
        {
     
            for(int j=0;j<=i;j++)
            {
     
                if(j==0) f[0][i] = f[0][i-1] + nums[len1-i]*multipliers[i-1];
                else if (j == i) f[i][0] = f[i-1][0] + nums [i-1] * multipliers [i-1];
                else f[j][i-j] = max (f[j][i-j-1]+nums[len1-i+j]*multipliers[i-1],f[j-1][i-j]+nums[j-1]*multipliers[i-1]);
                //cout<
            }
        }
        int res=-99999999999;
        for(int i=0;i<len2;i++)
        {
     
            res = max(f[i][len2-i],res);
        }
        return res;
    }
};

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

从 word1 中选出某个 非空 子序列 subsequence1 。
从 word2 中选出某个 非空 子序列 subsequence2 。
连接两个子序列 subsequence1 + subsequence2 ,得到字符串。
返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串,返回 0 。

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

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

示例 1:

输入:word1 = “cacb”, word2 = “cbba”
输出:5
解释:从 word1 中选出 “ab” ,从 word2 中选出 “cba” ,得到回文串 “abcba” 。
示例 2:

输入:word1 = “ab”, word2 = “ab”
输出:3
解释:从 word1 中选出 “ab” ,从 word2 中选出 “a” ,得到回文串 “aba” 。
示例 3:

输入:word1 = “aa”, word2 = “bb”
输出:0
解释:无法按题面所述方法构造回文串,所以返回 0 。

提示:

1 <= word1.length, word2.length <= 1000
word1 和 word2 由小写英文字母组成

class Solution {
     
public:
    int longestPalindrome(string word1, string word2) {
     
        string s = word1 + word2;
        int len1 =word1.length()-1;
        int len2 =word2.length()-1;
        int len = s.length();
        int f[2020][2020];
        for(int i=0;i<2020;i++) f[i][i]=1;
        int res=0;
        for(int i=1;i<len;i++)
        {
     
            //f[][]
            for(int j=0;i+j<len;j++)
            {
     
                //if(j==0) f[i+j][]
                if(s[j]==s[i+j]) {
     
                    f[j][i+j] = f[j+1][i+j-1]+2;
                    if(j<=len1&&i+j>len1) res = max (res,f[j][i+j]);}
                else f[j][i+j]=max(f[j][i+j-1],f[j+1][i+j]);
                    
            }
        }
        return res;
    }
};

你可能感兴趣的