2020/09/01 阿里笔试附解题思路代码

第一题

给定两个字符串 S, T 要求返回满足以下两个条件的子串
1. 子串为 S 的子串例如 a, ac 是 acd 的子串
2. 子串的序列为 T的子序列例如 ac 为 abcd 的子序列

解法为:

先得到 s 的子串 a, b, c, ab, bc, abc

但其实只需要保留 abc, bc, c 即可, 因为 abc中已经包含 a, ab, abc ; bc 包含 b, bc

用 T字符串分别跟 abc, bc, c 比对, 在比对完 abc之后其实我们已经累加得到了 a, ab, abc的答案

复杂度为 O(n) + O(nm)

vector<string> list;
for (int i = 0; i < n - 1; i++) {
    list.push_back(S.substr(i));
}
int res = 0;
int start = 0

for (int i = 0; i < list.size(); i++) {
    int start = 0;
    for (int j = 0; j < T.length && start < list[i].length; j++) {
        if (list[i][start] == T[j]) {
            res++;
            start++;
        }
    }
}

第二题

给定字节长度为m 的 n 组字节流和确认正确的字符数目, 求能否还原正确的字符流, 若能且答案唯一请输出该答案, 若有多个答案输出答案的总数, 若无答案输出 0
例子 : 5
00101 4
00111 3
10011 3
答案唯一为 10101 (不记得是不是这样了, 大概这个题意吧, 不纠结)

解法为: 回溯法, 总共是 2^m种组合可能那么就用回溯法来做

有不对的地方请大家指出来

int dfs (vector<int>& path, int i, int m, vector<vector<int>>& streams, int[] correct, vector<int> res) {
    if (i == m) {
        bool allZero = true;
        for (int j = 0; j < correct.length; j++) {
            if (correct[j] != 0) {
                allZero = false;
                break;
            }
        }
        if (allZero) {
            vector<int>v (path);
            res.swap(v);
            return 1;
        }
        return 0;
    }
    int res = 0;
    int temp[m];
    path.push_back(1);
        for (int j = 0; j < correct.length; j++) {
            temp[j] = streams[j][i] == 1 ? correct[j] - 1 : correct[j];
        }
        res += dfs(path, i + 1, m, streams, temp);
    path.pop_back();
    path.push_back(0);
        for (int j = 0; j < correct.length; j++) {
            temp[j] = streams[j][i] == 0 ? correct[j] - 1 : correct[j];
        }
        res += dfs(path, i + 1, m, streams, temp);
    path.pop_back();
    return res;
}

#阿里笔试2020##笔经##阿里巴巴#