关于c++:leetcode-229-周赛

5685. 交替合并字符串

给你两个字符串 word1 和 word2。请你从 word1 开始，通过交替增加字母来合并字符串。如果一个字符串比另一个字符串长，就将多进去的字母追加到合并后字符串的开端。

返回 合并后的字符串。
输出：word1 = “abc”, word2 = “pqr”
输入：“apbqcr”

思路

• 通过 up 进行判断

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int i = 0, j = 0;
        string res;
        bool up = true;
        while (i <= word1.size() && j <= word2.size()) {if (i < word1.size() && up == true) {res += word1[i++];
                up = false;
            } else if (j < word2.size() && up == false) {res += word2[j++];
                up = true;
            }
            
            if (i == word1.size() && j == word2.size()) {break;} else if (i == word1.size() && j < word2.size()) {while (j < word2.size()) {res += word2[j++];
                }
            } else if (j == word2.size() && i < word1.size()) {while (i < word1.size()) {res += word1[i++];
                }
            }
        }
        return res;
    }
    
};

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

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

在一步操作中，你能够将 一个 小球从某个盒子挪动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i – j) == 1。留神，操作执行后，某些盒子中可能会存在不止一个小球。

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

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

思路

• 用值为 1 的下标减去以后下标

vector<int> minOperations(string boxes) {
        vector<int> res;
        int cnt = 0;
        for (int i = 0; i < boxes.size(); i++) {for (int j = 0; j < boxes.size(); j++) {int tmp = boxes[j] - '0';
                if (tmp == 1) {cnt += abs(j-i);
                }
            }
            res.push_back(cnt);
            cnt = 0;
        }

        return res;
    }

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

思路

• 有两种抉择，抉择最后面的或者最开端的
• 共抉择 m 个，首抉择 i，尾抉择 j，i+j <= m
• 代码从 1 开始计数, 首就是 nums[i-1], 尾是 nums[n-i]

class Solution {
public:
    int maximumScore(vector<int>& ns, vector<int>& ms) {int m = ms.size();
        int n = ns.size();
        vector<vector<int>> mem(m + 1, vector<int>(m + 1));
        mem[0][0] = 0;
        for (int i=1; i<=m; ++i) {mem[i][0] = mem[i-1][0] + ns[i-1] * ms[i-1]; // 从后面选
            mem[0][i] = mem[0][i-1] + ns[n-i] * ms[i-1]; // 从前面选
        }
        for (int i=1; i<=m; ++i) {for (int j=1; i+j<=m; ++j) {mem[i][j] = max(mem[i-1][j]+ms[i+j-1]*ns[i-1], // 从后面选
                    mem[i][j-1]+ms[i+j-1]*ns[n-j] // 从前面选
                );
            }
        }
        int res = INT_MIN;
        for (int i=0; i<=m; ++i)
            res = max(res, mem[i][m-i]); // 从后面抉择了 i 个，从前面抉择了 m - i 个
        return res;
    }
};

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

给你两个字符串 word1 和 word2，请你按下述办法结构一个字符串：

从 word1 中选出某个 非空 子序列 subsequence1。
从 word2 中选出某个 非空 子序列 subsequence2。
连贯两个子序列 subsequence1 + subsequence2，失去字符串。
返回可按上述办法结构的最长 回文串 的 长度。如果无奈结构回文串，返回 0。

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

思路

• 相似于 leetcode516. 最长回文子序列

• dpi 示意从 [i,j] 的最长回文串的长度，默认 dpi = 1;

  • 留神 i <= j
• 留神首尾字符须要在不同的字符串中

class Solution {
public:
    int longestPalindrome(string word1, string word2) {
        // 首尾别离在 word1 和 word2 中
        string word3 = word1 + word2;
        int mid = word1.size();
        return getString(word3, mid);
    }

    int getString(string s, int mid) {int n = s.size();
        int ans = 0;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; i++) {dp[i][i] = 1;
        }
        for (int i = n-1; i >= 0; i--) {for (int j = i+1; j < n; j++) {if (s[i] == s[j]) {dp[i][j] = dp[i+1][j-1] + 2;
                    if (i < mid && j >= mid) {// 首尾在两个不同的字符串
                        ans = max(ans, dp[i][j]);
                    }
                } else {dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return ans;
    }
};