打卡记录

最长相邻不相等子序列 I（脑筋急转弯）

链接

思路：形如 11100110001 要达到最大，必须在重复数字选出一个，即在111中取一个1，在00中取一个0，以此类推最终便得到最长相邻不相等子序列。

class Solution {
public:vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {vector<string> ans;for (int i = 0; i < n; i++)if (i == n - 1 || groups[i] != groups[i + 1]) ans.push_back(words[i]);return ans;}
};

最长相邻不相等子序列 II（DP）

链接

思路：「子序列 + 考虑相邻元素」DP

子序列 DP 的思考套路
子序列 + 不考虑相邻元素：选或不选。代表题目：494. 目标和（0-1 背包）
子序列 + 考虑相邻元素：枚举选哪个。代表题目：300. 最长递增子序列

class Solution {
public:vector<string> getWordsInLongestSubsequence(int n, vector<string>& words, vector<int>& groups) {auto check = [&](string& a, string& b) -> bool{if (a.size() != b.size()) return false;int m = a.size();bool flag = false;for (int i = 0; i < m; ++i){if (a[i] != b[i]){if (flag) return false;flag = true;}}return flag;};int dp[n], max_len = 1, pre[n], idx = 0;memset(pre, -1, sizeof pre);for (int i = 0; i < n; ++i){dp[i] = 1;for (int j = 0; j < i; ++j){if (groups[i] != groups[j] && check(words[i], words[j]) && dp[i] < dp[j] + 1){dp[i] = dp[j] + 1;pre[i] = j;}if (max_len < dp[i]){max_len = dp[i];idx = i;}}}vector<string> ans;for (int i = idx; i != -1; i = pre[i]) ans.push_back(words[i]);reverse(ans.begin(), ans.end());return ans;}
};

执行操作使两个字符串相等

链接

class Solution {
public:int minOperations(string s1, string s2, int x) {if (count(s1.begin(), s1.end(), '1') % 2 != count(s2.begin(), s2.end(), '1') % 2) {return -1;}int n = s1.length();int memo[n][n + 1][2];memset(memo, -1, sizeof(memo)); // -1 表示没有计算过function<int(int, int, bool)> dfs = [&](int i, int j, bool pre_rev) -> int {if (i < 0) {return j || pre_rev ? INT_MAX / 2 : 0;}int &res = memo[i][j][pre_rev]; // 注意这里是引用if (res != -1) { // 之前计算过return res;}if ((s1[i] == s2[i]) == !pre_rev) { // 无需反转return dfs(i - 1, j, false);}res = min(dfs(i - 1, j + 1, false) + x, dfs(i - 1, j, true) + 1);if (j) { // 可以免费反转res = min(res, dfs(i - 1, j - 1, false));}return res;};return dfs(n - 1, 0, false);}
};