秋招突击——算法打卡——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] == '.'){
                    // 这里就是可以匹配任何不同的数据，但是有一个末尾匹配的问题
                    
                }else
                    px ++;


            }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，然后在复习一道题，差不多一天四道题。不能再多了，再多没时间学习别的了。