人生就是总有一天你会去写自己最讨厌的算法题，但是 unordered_map 确实好使。
std::unordered_map 使用哈希和桶实现，不过在使用中并不需要完全理解它是如何实现的。把它理解成键值对的集合，在知道键之后可以快速查询到值，就不用自己慢慢找了。
找到重复出现的字符
给出一个字符串，找出反复出现的字符并输出它们的所在位置。
输入
abcaaAB12ab12
输出
a,1; a,4; a,5; a,10; b,2; b,11; 1,8; 1,12; 2,9; 2,13.
解答
有了 unordered_map，我们可以只遍历一次字符串，在遍历时记录下已经出现的字符。于是，发现遍历到的字符已经被记录下来时，说明这个字符是反复出现的。
不过，反复出现的字符的第一次出现（例如上面的 a,1 和 b,2）也需要输出。可以在它们第一次重复（即第二次出现）时将其输出，于是需要标记记录第一次出现的位置是否已经被输出。
题目没有要求输出顺序，但若有则不能立刻输出，而是应该在遍历时将结果保存下来，最后按照要求的输出顺序输出。
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
int main () {
string s;
cin >> s;
size_t n = s.length();
// record first occur place
unordered_map<char, size_t> firstplace;
// flags for whether first occur has outputed
vector<bool> firstout(n, false);
bool flag = false;
for (size_t i = 0; i < n; i++) {
if (firstplace.find(s[i]) != firstplace.end()) {
// current char is duplicate
auto firstindex = firstplace[s[i]];
if (!firstout[firstindex]) {
// is first duplicate (second occur)
// output first occur
if (flag) {
cout << "; ";
} else {
flag = true;
}
cout << s[i] << ',' << firstindex + 1;
firstout[firstindex] = true;
}
// output this occur
cout << "; " << s[i] << ',' << i + 1;
} else {
// is not duplicate (first occur)
firstplace[s[i]] = i;
}
}
if (flag) {
cout << '.' << endl;
}
return 0;
}
最多两种不同字符构成的最长子序列
给出一个字符串，找出由最多两种不同字符构成的最长子序列。
输入
eeaeaaguhaiouuuuuoououdfvbiu
输出
11 ouuuuuoouou
解答
题目很长也很绕口，不过本质是找出一个「符合特定条件」的子序列。
和许多只包含正数的子序列问题一样，可以使用双指针法。使用两个指针 i 和 j，作为候选子序列的开头和末尾。指针 j 只逐步向前，遍历一次给定的字符串；而指针 i 只在指针 j 更新后候选子序列不满足条件后才更新，前移最少的步数使其重新满足条件。这样，保证候选子序列始终是以 j 结尾的子序列中，满足条件且最长的那一个。将候选子序列与已知最佳相比较，得出新的最佳答案。
例如，本题的条件是候选子序列只包含两种不同的字符串。若 j 的更新使第三种字符出现在了候选字符串里，就移动 i 排除一种字符。例如本题的例子，当移动 j 使得候选字符串从 eeaeaa 变为 eeaeaag 时，移动 i 排除字符 e，使候选变为 aag．显然，i 要移动到两种字符在候选中最后一次出现的这两个位置中，较前的那一个。
如何知道这个位置在哪？当然是使用 unordered_map 记录了。
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main () {
string s;
cin >> s;
size_t i = 0, j;
int best = 0;
string bs = "";
// used to record last occur of each char in substr
unordered_map<char, size_t> rec;
for (j = 0; j < s.size(); j++) {
if (rec.size() == 2 && rec.find(s[j]) == rec.end()) {
// substr is saturated
// potential maximum
int len = j - i;
bs = len > best ? s.substr(i, len) : bs;
best = max(len, best);
// update start pointer
// find the last place of the earlier char in substr
char c;
size_t pos = j;
for (auto it = rec.begin(); it != rec.end(); it++) {
if (pos > it -> second) {
c = it -> first;
pos = it -> second;
}
}
// delete this char
rec.erase(c);
// new start pointer
i = pos + 1;
}
// continue
// update new record
rec[s[j]] = j;
}
int len = j - i;
bs = len > best ? s.substr(i, len) : bs;
best = max(len, best);
cout << best << ' ' << bs << endl;
return 0;
}
这题中的 unordered_map 中虽然最多只包含两个元素，但具有可扩展性。改动判断中的 rec.size() == 2，就可用于解决「最多 n 种不同字符构成的最长子序列」问题。
用 2 的幂组成数字
每个正数都可以表示为 2 的幂的和，例如 ．而 ，并且 ，于是所有的数都可以使用只有 2 和 0 构成的指数式来表示。为了方便阅读输出，用 a(b) 表示 ．
输入
137
输出
2(2(2)+2+2(0))+2(2+2(0))+2(0)
解答
用递归和分治的方法解决此题。让函数在得到 137 时，先得出 2 的幂的和的表示法中的指数，然后再对指数递归调用这个函数。不过如果指数是 1 时，输出的不是 2(2(0)) 而是 2，此时就不用递归直接输出就可以了。
显然，递归会使函数的参数越来越小，于是题目中有许多重复计算的部分。如果能用 unordered_map 把之前计算的表示式存起来，就不用反复计算，于是可以省很多时间，这就是动态规划#。
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
string getRep (long long n, unordered_map<long long, string> &rep) {
auto search = rep.find(n);
// if the representation is already calculated, return it
if (search != rep.end())
return rep[n];
// all exponents
vector<long long> exp;
int t = n;
// break n into sum of power of 2
while (t > 0) {
long long i = 1, p;
for (p = 0; i <= t; p++) {
i *= 2;
}
p--;
// record all exponents
exp.push_back(p);
t -= i / 2;
}
string r = "";
for (auto it = exp.begin(); it != exp.end(); it++) {
if (it != exp.begin())
r += "+";
if ((*it) == 1) {
// if the exponent is 1, no need to write it down
r += "2";
continue;
}
r += "2(";
// recurse!
r += getRep(*it, rep);
r += ")";
}
rep[n] = r;
return r;
}
int main () {
// store already solved representation
unordered_map<long long, string> rep;
rep[0] = "0";
rep[2] = "2";
long long n;
cin >> n;
cout << getRep(n, rep) << endl;
return 0;
}
#. 其实并不完全是。记录下已经解决的子问题是 memoization（没有 r），而动态规划则是 deliberately memoize． ↩