秋招突击——算法打卡——5/30——复习{最大上升子序列的和、面试算法缺陷补充}——新做：{回文数+补充 自定义Stoi实现、正则表达式匹配}

复习

导弹拦截——最大上升子序列和

• 同样类型题目链接：导弹拦截
• 重做这道题主要是在看一遍最大上升子序列，应该怎么写？使用二维矩阵进行动态规划应该怎么写？昨天面试的时候，一维的矩阵写出来，但是二维的没整明白。
  • 校正
    • 这里搞错了，是针对那种二维迷宫的问题，是可以使用滚动数组进行优化的，但是对于这个最大上升子序列，本身的动态规划就是一维的，记错了，尴尬！！！
    • 可以使用滚动数组优化的DP问题链接——采药问题

推理过程

实现代码

const int N = 1010;
int f[N],w[N];
int n;int main(){cin>>n;for (int i = 1; i <= n; ++i) {cin>>w[i];}// 计算最大上升子序列和，并更新动态规划矩阵for (int i = 1; i <= n; ++i) {f[i] = w[i];for (int j = 1; j <= i; ++j) {if(w[j] < w[i]){f[i] = max(f[i],f[j] + w[i]);}}}// 求其最大上升子序列和的值int res = 0;for (int i = 1; i <= n; ++i) {res = res > f[i] ? res :f[i];}cout<<res<<endl;
}

补充昨日面试

• 昨天面试的时候，要写代码，有两个地方不确定

定义sort函数的排序函数

• 自定义比较，定义一个compare函数
  
• 使用Lamdba表达式
  • 好家伙，蛮丢弃人的，原来我笔试的时候写错了，尴尬
    

pair数据的使用

• 创建pair变量

  • 使用{}，不用使用make_pair，这样会快捷很多

• 函数中如何传入对应的pair类型的数据
  

新作

回文数

• 题目链接

实现代码

bool isPalindrome(int x) {long  y = 0,temp = x;while(x > 0){y = y * 10 + x % 10;x /= 10;}return temp == y;}

• 一道简单题，整的有点快，顺便看一下上次的那个自定义的转为整数的做法

字符串转整数

• 跳转链接：字符串转整数

• 之前写的代码有几个问题

  • 如果已经处理完了符号还有空格，就不需要再进行遍历，后续在遇到类似的情况就是终止的开始，所以没有必要将之再放到你的循环里面。
  • 使用index进行逐步遍历，完全比我现在的方法要好很多，可以更加灵活地控制，

• 更新之后的代码是这样的

int myAtoi1(string s){int idx = 0;int res = 0;// 遍历所有的空格while(idx < s.size() && s[idx] == ' ') idx ++;if(idx == s.size()) return 0;// 遍历对应的符号int minus = 1;if(s[idx] == '-') minus = -1,idx ++;if(s[idx] == '+') {if (minus == -1)    return 0;idx ++;}// 遍历所有的数字while(idx < s.size() && s[idx] >= '0' && s[idx] <= '9'){int x = s[idx] - '0';if( res >(INT_MAX - x) - 10){if (minus == 1) return INT_MAX;else return INT_MIN;}res = res * 10 + x;idx ++;}res *= minus;return res;
}

• 这样写比之前好多了，不会看起来很乱了，下次继续。

正则表达式匹配

• 题目链接：正则表达式匹配
  

个人实现

思路分析

• 这个没写出来，但是也得给出自己的实现思路，面试的时候，就算写不出来，也会问你基本的实现思路。
• 首先，这是一个字符串匹配问题，所以可以使用双指针，先把问题简化一下，仅仅只有“.”,就要保证长度是一致的，然后“.”是可以匹配任何字符的，所以遇到了"."跳过
• 然后在增加"*",也就是说，长度可以不用相等，统计*的个数为n，然后分别作为0和0次以上重复两种情况，长度范围就是size - 2n 到目标的size
• 然后就将问题转化为子串匹配问题：
  • 主要是集中在以*为核心的三元组字符串展开，以下4种情况，然后分段进行处理即可。
    • a*b
    • a*a
    • a*.
    • .*

实现代码如下

• 这里写的比较挫，不过接受了，下次再改。唯一的问题是，先写一个大概，不管能拿多少分，先写一个，就算过了负向样例也是可以的，它是按照样例算分的，这个只会输出true或者false，还是很好通过样例得分的，并不是以ac为目的。

bool isMatch(string s,string p){int sx = 0,px = 0;while(sx < s.size() && px < p.size()){// 数字相同或者正则表达式中有“.”if (s[sx] == p[px] || p[px] == '.')  sx ++,px ++;else{// 遍历完是否相同，看下一个位置是否是"*"if (p[px] == '*'){// 查看上一个元素// 如果上一个元素是相同的，转换成子串匹配的问题if (s[sx - 1]== p[px - 1]){int start = px - 1;for (int i = 0; i < ; ++i) {}}else if(p[px - 1] == '.'){// 这里就是可以匹配任何不同的数据，但是有一个末尾匹配的问题}elsepx ++;}else{return false;}}}if (sx < s.size() | px < p.size() )     return false;else return true;
}

参考做法

思路分析

• 首先，这道题的是DP解答，类似的使用DP解决的字符串问题
  • 两个字符串，求最长的公共字串
  • 两个字符串求边际距离
  • 两个字符串是否相等等等
• 具体分析如下，这里的分析还是有点看不懂，还是看看别人的分析吧

• 这里还是有点不懂，再好好推理一下具体的过程，具体如下
• f(i,j)有很多匹配方式，看一下有没有合法的匹配方案数量
  

实现代码

bool isMatch(string s,string p){// 简化操作int n = s.size(),m = p.size();// 将坐标置定为1开始s = ' ' + s,p = ' ' + p;// 定义状态转移方程vector<vector<bool>> f(n + 1,vector<bool>(m + 1));f[0][0] = true;  // 两个数组都为空// 双重循环遍历对应的数组for (int i = 0; i <= n; ++i) {// 这里j不能从零开始，因为i为空，j不为空的情况下，根本不可能实现for (int j = 1; j <= m; ++j) {// 单独匹配到*，直接跳过，因为※是两个字符同时使用if (j + 1 <= m && p[j + 1] == '*')  continue;// 处理状态转移方程if (i && p[j] != '*'){// 正常字符串匹配f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');}else if(p[j] == '*'){// 非正常匹配字符，可以是※的匹配f[i][j] = f[i][j - 2] || (i && f[i - 1][j] && (s[i] == p[j -1] || p[j - 1] == '.'));}}}return f[n][m];
}

总结

• 感觉不能只刷leetcode，还是得抽时间，刷一下算法提高课，这样吧，差不多一天三道题，一道题是算法提高课里面的题目，剩下的题目就是leetcode，然后在复习一道题，差不多一天四道题。不能再多了，再多没时间学习别的了。