力扣11.5

1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。

数据范围

• 1 <= nums1.length, nums2.length <= 500
• 1 <= nums1[i], nums2[j] <= 2000

分析

实际就是求最长公共子序列

代码

class Solution {
public: const static int N = 505;int dp[N][N];int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);if(nums1[i] == nums2[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);}}return dp[n][m];}
};

---

1458. 两个子序列的最大点积

给你两个数组 nums1 和 nums2 。

请你返回 nums1 和 nums2 中两个长度相同的 非空 子序列的最大点积。

数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5] 是 [1,2,3,4,5] 的一个子序列而 [1,5,3] 不是。

数据范围

• 1 <= nums1.length, nums2.length <= 500
• -1000 <= nums1[i], nums2[i] <= 100

分析

最长公共子序列的变式，令dp[i][j]表示nums1的前i个数和nums2的前j个数所能构成的点积最大值，接下来考虑nums1[i]和nums2[j]是否选择

• 若nums1[i]*nums2[j]<0
  • 只选择nums1[i]，dp[i][j]=dp[i][j-1]
  • 只选择nums2[j]，dp[i][j]=dp[i-1][j]
  • 这里不能都不选，因为题目规定是非空子序列，还有第三种情况，dp[i][j]=nums1[i]*nums2[j]
• 若nums1[i]*nums2[j]>0
  • dp[i][j]=dp[i-1][j-1]+nums1[i]*nums2[j]

代码

class Solution {
public:const static int N = 505;int dp[N][N];int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();memset(dp, -0x3f, sizeof(dp));for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {dp[i + 1][j + 1] = max(nums1[i] * nums2[j], max(dp[i][j + 1], dp[i + 1][j]));if(nums1[i] * nums2[j] >= 0) {dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + nums1[i] * nums2[j]);} }}return dp[n][m];}
};

---

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

数据范围

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
• '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

分析

使用一个操作数栈和一个符号栈，先转换为后缀表达式，然后求解
**注意：**对于-a的处理是变成0-a的形式

代码

typedef long long LL;
class Solution {
public:const static int N = 3e5 + 5;int tt1 = -1, tt2 = -1;char stk[N];LL num[N];LL calculate(string s) {int start = 0;for(int i = start; i < s.size(); i ++ ) {if(s[i] == ' ') continue;if(s[i] == '(') stk[++ tt1] = s[i];else if(s[i] == ')') {int a = num[tt2];int b = num[tt2 - 1];int j = tt1;while(j != -1 && stk[j] != '(') {if(stk[j] == '+') num[-- tt2] = a + b;else if(stk[j] == '-') num[-- tt2] = b - a;j -- ;}tt1 = j - 1;} else if(s[i] >= '0' && s[i] <= '9') {LL tnum = 0;int j = i;while(s[j] >= '0' && s[j] <= '9') {tnum = tnum * 10 + s[j] - '0';j ++ ;}i = j - 1;num[++ tt2] = tnum;} else if(s[i] == '+' || s[i] == '-') {if(tt1 == -1 || stk[tt1] == '(') stk[++ tt1] = s[i];else {int a = num[tt2];int b = num[tt2 - 1];if(stk[tt1] == '+') num[-- tt2] = a + b;else num[-- tt2] = b - a;stk[tt1] = s[i];}if(s[i] == '-') {int j = i - 1;while(j >= 0) {if(s[j] == ' ') j -- ;if(s[j] == ')') j -- ;if(s[j] >= '0' && s[j] <= '9') break;if(s[j] == '(') break;}if(j < 0 || s[j] == '(') {num[++ tt2] = 0;}}}}if(tt1 != -1) {for(int i = tt2; i >= 0; i -- ) {int a = num[tt2];int b = num[tt2 - 1];if(stk[i] == '+') num[-- tt2] = a + b;else if(stk[i] == '-') num[-- tt2] = b - a;}}return num[0];}
};

---

1092. 最短公共超序列

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

如果从字符串 t 中删除一些字符（也可能不删除），可以得到字符串 s ，那么 s 就是 t 的一个子序列。

数据范围

• 1 <= str1.length, str2.length <= 1000
• str1 和 str2 都由小写英文字母组成。

分析

令dp[i][j]为包含str1的前i个字符和str2的前j个字符的最短字符串长度，最原始的dp做法是，用另一个dp数组dp2表示包含str1的前i个字符和str2的前j个字符的最短字符串，但这样内存会超，这道题可以通过路径追踪类似的方法得到最终的字符串

代码

typedef pair<pair<int, int>, char> PIIC;
class Solution {
public:const static int N = 1005;int dp[N][N];PIIC last[N][N];string shortestCommonSupersequence(string str1, string str2) {int n = str1.size();int m = str2.size();memset(dp, 0x3f, sizeof(dp));dp[0][0] = 0;for(int i = 1; i <= m; i ++ ) {dp[0][i] = i;last[0][i] = {{0, i - 1}, str2[i - 1]};}for(int i = 1; i <= n; i ++ ) {dp[i][0] = i;last[i][0] = {{i - 1, 0}, str1[i - 1]};}for(int i = 0; i < n; i ++ ) {for(int j = 0; j < m; j ++ ) {if(dp[i + 1][j + 1] > dp[i][j + 1] + 1) {dp[i + 1][j + 1] = dp[i][j + 1] + 1;last[i + 1][j + 1] = {{i, j + 1}, str1[i]};} if(dp[i + 1][j + 1] > dp[i + 1][j] + 1) {dp[i + 1][j + 1] = dp[i + 1][j] + 1;last[i + 1][j + 1] = {{i + 1, j}, str2[j]};}if(str1[i] == str2[j]) {if(dp[i + 1][j + 1] > dp[i][j] + 1) {dp[i + 1][j + 1] = dp[i][j] + 1;last[i + 1][j + 1] = {{i, j}, str1[i]};}}}}string res = "";PIIC now = last[n][m];while(now.first.first != 0 || now.first.second != 0) {res = now.second + res;PIIC tmp = now;now = last[now.first.first][now.first.second];if(now.first.first == 0 && now.first.second == 0) {if(tmp.first.second != 0) res = str2[0] + res;else res = str1[0] + res;}}return res;}
};