园区网互联及网站建设2023年7月疫情爆发
1035. 不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
数据范围
1 <= nums1.length, nums2.length <= 5001 <= 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 * 105s 由数字、'+'、'-'、'('、')'、和 ' ' 组成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 <= 1000str1 和 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;}
};