9.4 携程笔试

第一题 最长公共子串

int longestSubStrLength(string s1, string s2) {
    int len1 = s1.size(), len2 = s2.size(), iMax = 0;
    vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
    for(int i=1; i<=len1; i++)
        for(int j=1; j<=len2; j++)
            // 通过 | ‘ ’  把字符都转成小写
            if((s1[i-1]|' ') == (s2[j-1]|' ')) {
                dp[i][j] = dp[i-1][j-1] + 1;
                iMax = max(iMax, dp[i][j]);
            }
    return iMax;
}

第二题 版本号比较

vector<int> getNum(string& a) {
    vector<int> res;
    int ind = -1, len = a.size(), num = 0;
    while(++ind < len) {
        if(a[ind] == '.') res.push_back(num), num = 0;
        else num = num * 10 + a[ind]-'0';
    }
    res.push_back(num);
    return res;
}

bool getRes(vector<int>& arr, vector<int>& brr) {
    int len1 = arr.size(), len2 = brr.size(), ind = -1;
    while(++ind < min(len1, len2)) {
        if(arr[ind] < brr[ind]) return true;
        if(arr[ind] > brr[ind]) return false;
    }
    return len1 <= len2;
}

string sortVersion(string s1, string s2) {
    vector<int> arr = getNum(s1);
    vector<int> brr = getNum(s2);
    bool flag = getRes(arr, brr);
    string res = flag ? s1 + "," + s2 : s2 + "," + s1;
    return res;
}

第三题 乘积最大子序列

#include <iostream>
#include <vector>

using namespace std;

vector<int> getNum(string& a) {
    vector<int> res;
    int ind = -1, len = a.size(), num = 0;
    bool flag = true;
    while(++ind < len) {
        if(a[ind] == '-') flag = false;
        else if(a[ind] == ' ') 
            res.push_back(flag ? num : -num), flag = true, num = 0;
        else num = num * 10 + a[ind]-'0';
    }
    res.push_back(flag ? num : -num);
    return res;
}

int main() {
    string s;
    getline(cin, s);

    vector<int> arr = getNum(s);
    int iMax = arr[0], iMin = arr[0], res = arr[0];
    for(int i=1; i<arr.size(); i++) {
        if(arr[i] >= 0) {
            iMax = max(iMax * arr[i], arr[i]);
            iMin = min(iMin * arr[i], arr[i]);
        }else {
            int tem = iMax;
            iMax = max(iMin * arr[i], arr[i]);
            iMin = min(tem * arr[i], arr[i]);
        }
        res = max(res, iMax);
    }
    cout << res << endl;
    return 0;

}