LeetCode周赛

第227场周赛

1752. 检查数组是否经排序和轮转得到

Description
给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
源数组中可能存在 重复项 。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。
Example
示例 1：
输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 3 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。

示例 2：
输入：nums = [2,1,3,4]
输出：false
解释：源数组无法经轮转得到 nums 。

示例 3：
输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置（即不轮转）得到 nums 。

示例 4：
输入：nums = [1,1,1]
输出：true
解释：[1,1,1] 为有序的源数组。
轮转任意个位置都可以得到 nums 。

示例 5：
输入：nums = [2,1]
输出：true
解释：[1,2] 为有序的源数组。
可以轮转 x = 5 个位置，使新数组从值为 2 的元素开始：[2,1] 。

提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
Program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool check(vector<int>& nums) {
        vector<int> A(nums.begin(), nums.end());
        sort(A.begin(), A.end());
        int n=nums.size();
        for(int x=0;x<n;x++){
            int cnt=0;
            for(int i=0;i<n;i++){
                if(A[i]==nums[(i+x)%n]) cnt++;
            }
            if(cnt==n) return true;
        }
        return false;
    }
};

1753. 移除石子的最大得分

Description
你正在玩一个单人游戏，面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。
每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 1 分。当存在 两个或更多 的空堆时，游戏停止。
给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。
Example
示例 1：
输入：a = 2, b = 4, c = 6
输出：6
解释：石子起始状态是 (2, 4, 6) ，最优的一组操作是：

  • 从第一和第三堆取，石子状态现在是 (1, 4, 5)
  • 从第一和第三堆取，石子状态现在是 (0, 4, 4)
  • 从第二和第三堆取，石子状态现在是 (0, 3, 3)
  • 从第二和第三堆取，石子状态现在是 (0, 2, 2)
  • 从第二和第三堆取，石子状态现在是 (0, 1, 1)
  • 从第二和第三堆取，石子状态现在是 (0, 0, 0)
    总分：6 分 。

示例 2：
输入：a = 4, b = 4, c = 6
输出：7
解释：石子起始状态是 (4, 4, 6) ，最优的一组操作是：

  • 从第一和第二堆取，石子状态现在是 (3, 3, 6)
  • 从第一和第三堆取，石子状态现在是 (2, 3, 5)
  • 从第一和第三堆取，石子状态现在是 (1, 3, 4)
  • 从第一和第三堆取，石子状态现在是 (0, 3, 3)
  • 从第二和第三堆取，石子状态现在是 (0, 2, 2)
  • 从第二和第三堆取，石子状态现在是 (0, 1, 1)
  • 从第二和第三堆取，石子状态现在是 (0, 0, 0)
    总分：7 分 。

示例 3：
输入：a = 1, b = 8, c = 8
输出：8
解释：最优的一组操作是连续从第二和第三堆取 8 回合，直到将它们取空。
注意，由于第二和第三堆已经空了，游戏结束，不能继续从第一堆中取石子。

提示：
1 <= a, b, c <= 105
Program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumScore(int a, int b, int c) {
        priority_queue<int, vector<int>, less<int>> pq;
        pq.push(a);
        pq.push(b);
        pq.push(c);
        int ans=0;
        while(pq.size()>=2){
            ans++;
            a=pq.top();pq.pop();
            b=pq.top();pq.pop();
            a--;
            b--;
            if(a>0) pq.push(a);
            if(b>0) pq.push(b);
        }
        return ans;
    }
};

1754. 构造字典序最大的合并字符串

Description
给你两个字符串 word1 和 word2 。你需要按下述方式构造一个新字符串 merge ：如果 word1 或 word2 非空，选择 下面选项之一 继续操作：
如果 word1 非空，将 word1 中的第一个字符附加到 merge 的末尾，并将其从 word1 中移除。
例如，word1 = “abc” 且 merge = “dv” ，在执行此选项操作之后，word1 = “bc” ，同时 merge = “dva” 。
如果 word2 非空，将 word2 中的第一个字符附加到 merge 的末尾，并将其从 word2 中移除。
例如，word2 = “abc” 且 merge = “” ，在执行此选项操作之后，word2 = “bc” ，同时 merge = “a” 。
返回你可以构造的字典序 最大 的合并字符串 merge 。
长度相同的两个字符串 a 和 b 比较字典序大小，如果在 a 和 b 出现不同的第一个位置，a 中字符在字母表中的出现顺序位于 b 中相应字符之后，就认为字符串 a 按字典序比字符串 b 更大。例如，”abcd” 按字典序比 “abcc” 更大，因为两个字符串出现不同的第一个位置是第四个字符，而 d 在字母表中的出现顺序位于 c 之后。
Example
示例 1：
输入：word1 = “cabaa”, word2 = “bcaaa”
输出：”cbcabaaaaa”
解释：构造字典序最大的合并字符串，可行的一种方法如下所示：

  • 从 word1 中取第一个字符：merge = “c”，word1 = “abaa”，word2 = “bcaaa”
  • 从 word2 中取第一个字符：merge = “cb”，word1 = “abaa”，word2 = “caaa”
  • 从 word2 中取第一个字符：merge = “cbc”，word1 = “abaa”，word2 = “aaa”
  • 从 word1 中取第一个字符：merge = “cbca”，word1 = “baa”，word2 = “aaa”
  • 从 word1 中取第一个字符：merge = “cbcab”，word1 = “aa”，word2 = “aaa”
  • 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。

示例 2：
输入：word1 = “abcabc”, word2 = “abdcaba”
输出：”abdcabcabcaba”

提示：
1 <= word1.length, word2.length <= 3000
word1 和 word2 仅由小写英文组成
Program
每一次操作选择字典序大的！
时间复杂度：$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string largestMerge(string word1, string word2) {
        string res;
        while(word1.length()>0&&word2.length()>0){
            if(word1<word2) swap(word1, word2);  //每次优先选用字典序大的进行操作！
            res+=word1[0];
            word1.erase(0, 1);
        }
        while(word1.length()>0){
            res+=word1[0];
            word1.erase(0, 1);
        }
        while(word2.length()>0){
            res+=word2[0];
            word2.erase(0, 1);
        }
        return res;
    }
};

1755. 最接近目标值的子序列和

Description
给你一个整数数组 nums 和一个目标值 goal 。
你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。
返回 abs(sum - goal) 可能的 最小值 。
注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
Example
示例 1：
输入：nums = [5,-7,3,5], goal = 6
输出：0
解释：选择整个数组作为选出的子序列，元素和为 6 。
子序列和与目标值相等，所以绝对差为 0 。

示例 2：
输入：nums = [7,-9,15,-2], goal = -5
输出：1
解释：选出子序列 [7,-9,-2] ，元素和为 -4 。
绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。

示例 3：
输入：nums = [1,2,3], goal = -7
输出：7

提示：
$1 <= nums.length <= 40$
$-10^7 <= nums[i] <= 10^7$
$-10^9 <= goal <= 10^9$
Program
状压DP+二分
（1）首先，需要计算所有子序列的和sum[i]=sum[i-(1<<j)]+nums[j]，其中(i&(1<<j))!=0，状压DP！
（2）然后计算每个子序列和求abs(goal-s);
（3）然而，题目$n=40$，求子序列和时间复杂度：$O(n * 2^{n})$，超时，因为超过了$10^8$，但是$O(n * 2^{n/2})$可行；
（4）将数组分成前后各一半，分别求出前后的子序列和，最终答案只会出现在这三种情况：
① leftSum的某个;
② rightSum的某个;
③ leftSum与rightSum各一个的和！
（5）然而①②时间复杂度都是$O(\frac{n}{2})$，而③顺序遍历会是$O(n)$，还是超时；
（6）考虑二分，将leftSum,rightSum排序，那么：
i=0, j=rightSum.size()-1;
s=leftSum[i]+rightSum[j]
如果s比goal大，j减少，否则i增加！因为如果s大，那么j后面的与i求和都会比s大！，反之，如果s小，那么i前面的与j求和只会比s小；
时间复杂度:$(\log{\frac{n}{n}}+n * 2^{\frac{n}{2}})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n=nums.size();
        int half=n/2;
        int ls=half, rs=n-half;
        vector<int> leftSum((1<<ls), 0), rightSum((1<<(rs)), 0);
        for(int i=1;i<(1<<ls);i++){
            for(int j=0;j<ls;j++){
                if((i&(1<<j))==0) continue;
                leftSum[i]=leftSum[i-(1<<j)]+nums[j];
                break;
            }
        }
        for(int i=1;i<(1<<rs);i++){
            for(int j=0;j<rs;j++){
                if((i&(1<<j))==0) continue;
                rightSum[i]=rightSum[i-(1<<j)]+nums[j+half];
                break;
            }
        }
        sort(leftSum.begin(), leftSum.end());
        sort(rightSum.begin(), rightSum.end());

        int res=INT_MAX;
        for(int x:leftSum) res=min(res, abs(goal-x));
        for(int x:rightSum) res=min(res, abs(goal-x));
        int i=0, j=rightSum.size()-1;
        while(i<leftSum.size()&&j>=0){
            int s=leftSum[i]+rightSum[j];
            res=min(res, abs(goal-s));
            if(s>goal) j--;
            else i++;
        }
        return res;
    }
};

第228场周赛

1758. 生成交替二进制字符串的最少操作数

Description
给你一个仅由字符 ‘0’ 和 ‘1’ 组成的字符串 s 。一步操作中，你可以将任一 ‘0’ 变成 ‘1’ ，或者将 ‘1’ 变成 ‘0’ 。
交替字符串 定义为：如果字符串中不存在相邻两个字符相等的情况，那么该字符串就是交替字符串。例如，字符串 “010” 是交替字符串，而字符串 “0100” 不是。
返回使 s 变成 交替字符串 所需的 最少 操作数。
Example
示例 1：
输入：s = “0100”
输出：1
解释：如果将最后一个字符变为 ‘1’ ，s 就变成 “0101” ，即符合交替字符串定义。

示例 2：
输入：s = “10”
输出：0
解释：s 已经是交替字符串。

示例 3：
输入：s = “1111”
输出：2
解释：需要 2 步操作得到 “0101” 或 “1010” 。

提示：
1 <= s.length <= 104
s[i] 是 ‘0’ 或 ‘1’
Program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minOperations(string s) {
        int n=s.length();
        int a=0, b=0;
        for(int i=0;i<n;i++){
            if(i%2==0){
                if(s[i]=='1') a++;
                else b++;
            }else{
                if(s[i]=='0') a++;
                else b++;
            }
        }
        return min(a, b);
    }
};

1759. 统计同构子字符串的数目

Description
给你一个字符串 s ，返回 s 中 同构子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。
同构字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同构字符串。
子字符串 是字符串中的一个连续字符序列。
Example
示例 1：
输入：s = “abbcccaa”
输出：13
解释：同构子字符串如下所列：
“a” 出现 3 次。
“aa” 出现 1 次。
“b” 出现 2 次。
“bb” 出现 1 次。
“c” 出现 3 次。
“cc” 出现 2 次。
“ccc” 出现 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：
输入：s = “xy”
输出：2
解释：同构子字符串是 “x” 和 “y” 。

示例 3：
输入：s = “zzzzz”
输出：15

提示：
1 <= s.length <= 105
s 由小写字符串组成
Program
滑窗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    const int MOD=1e9+7;
    int countHomogenous(string s) {
        int n=s.length();
        char pre=s[0];
        int end=-1;
        long ans=0;
        for(int i=0;i<n;i++){
            while(end+1<n&&s[end+1]==pre){
                end++;
            }
            long m=end-i+1;
            // cout<<end<<":"<<i<<":"<<m*(m+1)/2<<" ";
            ans=ans%MOD+(m*(m+1)/2)%MOD;
            if(end<n-1){
                i=end;
                pre=s[end+1];
            }else break;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    const int MOD=1e9+7;
    int countHomogenous(string s) {
        int n=s.length();
        char pre=s[0];
        int end=-1;
        long ans=0;
        for(int i=0;i<n;i++){
            if(s[i]!=pre){
                pre=s[i];
            }
            while(end+1<n&&s[end+1]==pre){
                end++;
            }

            ans=ans%MOD+(end-i+1)%MOD; //[bbb]有三个, [bb]两个，过程累加！
        }
        return ans;
    }
};

1760. 袋子里最少数目的球

Description
给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次：
选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。
比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。
请你返回进行上述操作后的最小开销。
Example
示例 1：
输入：nums = [9], maxOperations = 2
输出：3
解释：

  • 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
  • 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
    装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

示例 2：
输入：nums = [2,4,8,2], maxOperations = 4
输出：2
解释：

  • 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
  • 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
  • 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
  • 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
    装有最多球的袋子里装有 2 个球，所以开销为 2 并返回 2 。

示例 3：
输入：nums = [7,17], maxOperations = 2
输出：7

提示：
1 <= nums.length <= 105
1 <= maxOperations, nums[i] <= 109
Program
二分
（1）二分枚举最小开销
（2）已知最小开销，那么原始每个袋子x划分到最小开销需要操作(x-1)/cos;
（3）如果操作数小于最大可操作数说明可行，right=mid;否则，不可行，left=mid+1;
时间复杂度：$O(n\log{n})$
总感觉类似题目做过…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isPass(const vector<int>& nums, int cos, int maxOperations){
        int ans=0;
        for(int x:nums){
            ans+=(x-1)/cos;
            if(ans>maxOperations) return false;
        }
        return true;
    }
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left=1, right=1e9;
        while(left<right){
            int mid=left+(right-left)/2;
            if(isPass(nums, mid, maxOperations)){
                right=mid;
            }else left=mid+1;
        }
        return left;
    }
};

1761. 一个图中连通三元组的最小度数

Description
给你一个无向图，整数 n 表示图中节点的数目，edges 数组表示图中的边，其中 edges[i] = [ui, vi] ，表示 ui 和 vi 之间有一条无向边。
一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。
连通三元组的度数 是所有满足此条件的边的数目：一个顶点在这个三元组内，而另一个顶点不在这个三元组内。
请你返回所有连通三元组中度数的 最小值 ，如果图中没有连通三元组，那么返回 -1 。
Example
示例 1：
输入：n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
输出：3
解释：只有一个三元组 [1,2,3] 。构成度数的边在上图中已被加粗。

示例 2：
输入：n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
输出：0
解释：有 3 个三元组：

1) [1,4,3]，度数为 0 。
2) [2,5,6]，度数为 2 。
3) [5,6,7]，度数为 2 。

提示：
2 <= n <= 400
edges[i].length == 2
1 <= edges.length <= n * (n-1) / 2
1 <= ui, vi <= n
ui != vi
图中没有重复的边。
Program
暴力
枚举三个顶点
时间复杂度：$O(n^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minTrioDegree(int n, vector<vector<int>>& edges) {
        vector<vector<bool>> Adj(n+1, vector<bool>(n+1, false));
        vector<int> degree(n+1);
        for(vector<int>& edge:edges){
            int u=edge[0], v=edge[1];
            Adj[u][v]=Adj[v][u]=true;
            degree[u]++;
            degree[v]++;
        }
        int ans=INT_MAX;
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                if(!Adj[i][j]) continue;
                for(int k=j+1;k<=n;k++){
                    if(Adj[i][k]&&Adj[j][k]){
                        ans=min(ans, degree[i]+degree[j]+degree[k]-6);
                    }
                }
            }
        }
        return ans==INT_MAX?-1:ans;
    }
};

第229场周赛

1768. 交替合并字符串

Description
给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
返回 合并后的字符串 。
Example
示例 1：
输入：word1 = “abc”, word2 = “pqr”
输出：”apbqcr”
解释：字符串合并情况如下所示：

1
2
3
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r

示例 2：
输入：word1 = “ab”, word2 = “pqrs”
输出：”apbqrs”
解释：注意，word2 比 word1 长，”rs” 需要追加到合并后字符串的末尾。

1
2
3
word1：  a   b
word2：    p   q   r   s
合并后：  a p b q   r   s

示例 3：
输入：word1 = “abcd”, word2 = “pq”
输出：”apbqcd”
解释：注意，word1 比 word2 长，”cd” 需要追加到合并后字符串的末尾。

1
2
3
word1：  a   b   c   d
word2：    p   q
合并后：  a p b q c   d

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int m=word1.length(), n=word2.length();
        int flag=0;
        string res;
        int i=0, j=0;
        while(i<m&&j<n){
            if(flag==0){
                res+=word1[i++];
            }else res+=word2[j++];
            flag=1-flag;
        }
        while(i<m) res+=word1[i++];
        while(j<n) res+=word2[j++];
        return res;
    }
};

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

Description
有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 ‘0’ 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 ‘1’ 表示盒子里有 一个 小球。
在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。
每个 answer[i] 都需要根据盒子的 初始状态 进行计算。
Example
示例 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’
Program
（1）leftSum, rightSum首先记录i左/右邻近位置的1移动到i的的步数，注意这里是leftSum[i-1]和rightSum[i+1]累积了左/右的1的一次邻近步数；

1
2
3
4
5
6
nums:     1 1 0
leftSum:  0 1 2
rightSum: 1 0 0
前后缀:
leftSum:  0 1 3
rightSum: 1 0 0

（2）最后再计算leftSum,rightSum的前后缀和，得到最终表示i左/右所有1移动到i的操作数！

1
2
3
4
5
6
7
nums:     1 1 0
leftSum:  0 1 2
rightSum: 1 0 0
前后缀:
leftSum:  0 1 3
rightSum: 1 0 0
answer:   1 1 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n=boxes.length();
        vector<int> leftSum(n, 0), rightSum(n, 0);
        for(int i=1;i<n;i++) leftSum[i]=leftSum[i-1]+boxes[i-1]-'0';
        for(int i=1;i<n;i++) leftSum[i]+=leftSum[i-1];
        for(int i=n-2;i>=0;i--) rightSum[i]=rightSum[i+1]+boxes[i+1]-'0';
        for(int i=n-2;i>=0;i--) rightSum[i]+=rightSum[i+1];
        vector<int> res(n, 0);
        for(int i=0;i<n;i++) res[i]=leftSum[i]+rightSum[i];
        return res;
    }
};

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

Description
给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ，其中 n >= m ，数组下标 从 1 开始 计数。
初始时，你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作（从 1 开始 计数）中，需要：
选择数组 nums 开头处或者末尾处 的整数 x 。
你获得 multipliers[i] * x 分，并累加到你的分数中。
将 x 从数组 nums 中移除。
在执行 m 步操作后，返回 最大 分数。
Example
示例 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
Program
记忆化搜索
时间复杂度: $O(m * n ^2)$
果断超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<vector<int>>> vis;
    int n,m;
    int helper(const vector<int>& nums, const vector<int>& multipliers, int i, int left, int right){
        if(i==m||left>right) return 0;
        if(vis[i][left][right]!=INT_MIN) return vis[i][left][right];
        int score=max(nums[left]*multipliers[i]+helper(nums, multipliers, i+1, left+1, right),
                      nums[right]*multipliers[i]+helper(nums, multipliers, i+1, left, right-1));
        vis[i][left][right]=score;
        return score;
    }
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        n=nums.size(), m=multipliers.size();
        vis.resize(m, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
        return helper(nums, multipliers, 0, 0, n-1);
    }
};

DP
由于最终结果只会取前i个元素以及后j个元素，其中i+j=m；
设dp[i][j]表示取前i个元素和后j个元素的最大得分，状态转移方程：
$dp[i][j]=max(dp[i-1][j]+nums[i-1] * multipliers[i-1], dp[i][j-1]+nums[n-j] * multipliers[j-1])$
注意边界：
$dp[i][0]=dp[i-1][0]+nums[i-1] * multipliers[i-1]$
$dp[0][j]=dp[0][j-1]+nums[n-j] * multipliers[j-1]$
时间复杂度：$O(m^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumScore(vector<int>& nums, vector<int>& multipliers) {
        int n=nums.size(), m=multipliers.size();
        vector<vector<int>> dp(m+1, vector<int>(m+1, INT_MIN));
        dp[0][0]=0;
        for(int i=1;i<=m;i++) dp[i][0]=dp[i-1][0]+nums[i-1]*multipliers[i-1];
        for(int j=1;j<=m;j++) dp[0][j]=dp[0][j-1]+nums[n-j]*multipliers[j-1];
        int ans=INT_MIN;
        for(int i=1;i<=m;i++){
            for(int j=1;i+j<=m;j++){
                dp[i][j]=max(dp[i-1][j]+nums[i-1]*multipliers[i+j-1],
                             dp[i][j-1]+nums[n-j]*multipliers[i+j-1]);
                if(i+j==m) ans=max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

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

Description
给你两个字符串 word1 和 word2 ，请你按下述方法构造一个字符串：
从 word1 中选出某个 非空 子序列 subsequence1 。
从 word2 中选出某个 非空 子序列 subsequence2 。
连接两个子序列 subsequence1 + subsequence2 ，得到字符串。
返回可按上述方法构造的最长 回文串 的 长度 。如果无法构造回文串，返回 0 。
字符串 s 的一个 子序列 是通过从 s 中删除一些（也可能不删除）字符而不更改其余字符的顺序生成的字符串。
回文串 是正着读和反着读结果一致的字符串。
Example
示例 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 由小写英文字母组成
Program
(1)最长回文子串思路，讲了两个串联结后，按照最长回文子串计算；
(2)注意点，题目需要前后两个子序列非空，所以dp[i][j]的i,j分别属于第一个串和第二个串；
(3)所以，只需要在更新str[i]==str[j]更新dp[i][j]时，判断i,j是否满足题意；
时间复杂度:$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        int m=word1.length(), n=word2.length();
        string str=word1+word2;
        int len=m+n;
        vector<vector<int>> dp(len, vector<int>(len, 1));
        int res=0;
        for(int i=0;i<len;i++){
            if(i>0&&str[i-1]==str[i]) dp[i-1][i]=2;
            if(i==m&&str[m-1]==str[m]) res=max(res, dp[i-1][i]); //特例，word1最后一个字符与word2第一个字符匹配
        }
        for(int l=3;l<=len;l++){
            for(int i=0;i+l-1<len;i++){
                int j=i+l-1;
                if(str[i]==str[j]){
                    dp[i][j]=dp[i+1][j-1]+2;
                    if(i<m&&j>=m) res=max(res, dp[i][j]);
                }else dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return res;
    }
};
赏

Thank you for inviting me to have candy.

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

做一个安静细微的人，<br> 于角落里自在开放，<br> 默默悦人，<br> 却始终不引起过分热闹的关注，<br> 保有独立而随意的品格，<br> 这就很好。<br><br> Stick to what you insist on,<br> believe what you believe!<br> Life hastily for decades,<br> do what I can!