21/3/18 携程 开发笔试 凉经

第一次参加比笔试
凌晨投的携程
下午就发了晚上的 笔试链接

以为会有选择填空
原来只有两道编程题
以为一会er就做完了
结果最后 一题都没做完
哭唧唧

第一题 动态规划 题目原型 Leet code 712

两个字符串 最小 ASCII 删除和
leetcode 是只判断一组
面试题 是判断多组
不过应该都一样
虽然我不是很多熟悉 动态规划
但是应该 可以做完
可怕之处
在于
携程 给的 输入样例 是

Zhang San
Zhan Ai

但是 我分析了 题目模板 给的读入 格式
明明是这个 啊

 2
Zhang
San
2
Zhan
Ai

由于我写完的时候 以及只有3分钟了 按照这个样例写的 通过测试样例为0
但是时间 不足了，没有尝试 另一个格式是否能够 通过
我盲猜应该能过吧。
就是自己太菜了。

我写的 凉凉的代码

#include <iostream>
#include <vector>
#include <numeric>
#include <limits>

using namespace std;

int cha(string sa,string sb){
    int na = sa.length();
    int nb = sb.length();
//    int a=0,b=0;
    int sum=0;

    vector<vector<int > > dp(na+1,vector<int>(nb+1));
    for(int i=1;i<=na;i++)dp[i][0]=dp[i-1][0]+sa[i-1];
    for(int i=1;i<=nb;i++)dp[0][i]=dp[0][i-1]+sb[i-1];
    dp[0][0]=0;
    for(int i= 1;i<=na;i++){
        for(int j=1;j<=nb;j++){
            dp[i][j] = min(dp[i-1][j]+sa[i-1],dp[i][j-1]+sb[j-1]);
            int r = (sa[i-1] == sb[j-1]) ? 0 : (sa[i-1]+sb[j-1]);
            //cout<<i-1<<" "<<j-1<<" ++++++++++"<<r<<endl;
            //cout<<r<<"------"<<endl;
            if(sa[i-1] == sb[j-1]){
                //cout<<"equal"<<endl;
                //cout<<dp[i][j]<<" "<<dp[i-1][j-1]+r<<endl;
                if(dp[i-1][j-1]+r>dp[i][j]){
                        dp[i][j]=     dp[i][j];
                }else{
                        dp[i][j]=dp[i-1][j-1]+r;
                }
                //dp[i][j] == min(dp[i-1][j-1]+r,dp[i][j]);
                //cout<<i<<" "<<j<<"dp:"<<dp[i][j]<<endl;
            }
//            if(sa[i-1]==sb[j-1]){
//                dp[i][j]=dp[i-1][j-1];
//            }else{
//                dp[i][j] = min(dp[i-1][j-1]+sa[i-1]+sb[j-1],min(dp[i-1][j]+sa[i-1],dp[i][j-1]+sb[j-1]));
//                cout<<dp[i][j]<<"-------"<<endl;
//            } 
        }
    }
    return dp[na][nb];
}
/*请完成下面这个函数，实现题目要求的功能
当然，你也可以不按照下面这个模板来作答，完全按照自己的想法来 ^-^ 
******************************开始写代码******************************/
int calcSimilarity(vector < string > name1, vector < string > name2) {

    int n1 = name1.size();
    int n2 = name2.size();
    int ans = 0;
    int p = n1;
    if(p<n2)p=n2;
    for(int i=0;i<p;i++){
        if(n1>i&&n2>i){
            ans+=cha(name1[i],name2[i]);
        }else if(n1<=i&&n2>i){
            ans+=cha("",name2[i]);
        }else if(n1>i&&n2<=i){
            ans+=cha(name1[i],"");    
        }
        //cout<<cha(name1[i],name2[i])<<endl;
        //cout<<"-------------"<<endl;
    }

    return ans; 
}
/******************************结束写代码******************************/


int main() {
    int res;

    int _name1_size = 0;
    cin >> _name1_size;
    cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n'); 
    vector<string> _name1;
    string _name1_item;
    for(int _name1_i=0; _name1_i<_name1_size; _name1_i++) {
        getline(cin, _name1_item);
        _name1.push_back(_name1_item);
    }
    int _name2_size = 0;
    cin >> _name2_size;
    cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n'); 
    vector<string> _name2;
    string _name2_item;
    for(int _name2_i=0; _name2_i<_name2_size; _name2_i++) {
        getline(cin, _name2_item);
        _name2.push_back(_name2_item);
    }

    res = calcSimilarity(_name1, _name2);
    cout << res << endl;

    return 0;

}

第二题是 AC自动机 超纲了 我就弃了。