做法总览
朴素做法:$O(N^2)$——TLE
朴素+去重做法:$O(NlogN) + O(N) + O(m*N) = O(NlogN)$——AC(37 ms)
Hash做法:$O(N)$——AC(27 ms)
关于朴素+去重做法的说明:
第一项$O(NlogN)$为sort、第二项$O(N)$为unique,两步加起来可以视为去重,所以去重的总时间复杂度为$O(NlogN)$
第三项$O(m*N)$为算法主体的时间复杂度,系数为m是因为ASCII共95个可打印字符,也就是说输入最多有95种,常数级
各做法数据量的计算:
时间限制:$0.1s$——>数据量:$10^7$
$N = 10^4$
朴素:$$10^8 > 10^7$$
朴素+去重:$$10^4 * 8 * 3.x \approx 32 * 10 ^ 4 < 10^7$$
Hash:$$10 ^ 4 < 10^7$$
意外收获
意外收获:当自定义变量名和库中函数名重复时,可以在前面加::
代表其不在显示命名空间中(包括std::空间)
error:error: reference to ‘hash’ is ambiguous
error原因:在全局作用域声明的变量名与显示命名空间中的其他类/函数/…重复
error解决:
1. 不加显示命名空间,例如去掉using namespace std;
,要用的时候再加,即std::cin
等
2. 说明其不属于显示命名空间,即::hash
等
3. 别放全局作用域。这样做其实没什么影响,C++写算法时将数据结构放在全局是因为基础数据结构不会自动初始化,导致脏读;而C++ STL中的数据结构都会进行初始化,所以放哪都行。(不过我还是喜欢把需要读入的数据都声明在全局,看着整齐)
各做法代码
朴素做法
#include <iostream>
using namespace std;
string s1, s2;
bool is_exist(char ch)
{
for (auto i : s2)
if (i == ch)
return true;
return false;
}
int main()
{
getline(cin, s1);
getline(cin, s2);
string res;
for (auto ch : s1)
if (!is_exist(ch))
res += ch;
cout << res << endl;
return 0;
}
朴素+去重做法
#include <iostream>
#include <algorithm>
using namespace std;
string s1, s2;
bool is_exist(char ch)
{
for (auto i : s2)
if (i == ch)
return true;
return false;
}
int main()
{
getline(cin, s1);
getline(cin, s2);
// 去重
sort(s2.begin(), s2.end()); // 仅有序变量可被unique
auto it = unique(s2.begin(), s2.end()); // 将不重复的元素放在前面,返回尾迭代器
s2.erase(it, s2.end()); // 将尾迭代器到变量末的重复元素清除
string res;
for (auto ch : s1)
if (!is_exist(ch))
res += ch;
cout << res << endl;
return 0;
}
Hash做法
#include <iostream>
#include <unordered_set>
using namespace std;
int main()
{
string s1, s2;
getline(cin, s1);
getline(cin, s2);
unordered_set<char> hash;
for (auto ch : s2) hash.insert(ch);
string res;
for (auto ch : s1)
if (!hash.count(ch))
res += ch;
cout << res << endl;
return 0;
}
Hash做法2
#include <iostream>
#include <unordered_set>
using namespace std;
string s1, s2;
unordered_set<char> hash;
int main()
{
getline(cin, s1);
getline(cin, s2);
for (auto ch : s2) ::hash.insert(ch);
string res;
for (auto ch : s1)
if (!::hash.count(ch))
res += ch;
cout << res << endl;
return 0;
}