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;
} 
