为了提取出后 30 位，需要使用 mask ，取值为 0x7ffffff（二进制表示含有 27 个 1） ，先用此 mask 可取出整个序列的后 27 位，然后再向左平移三位可取出 10 个字母长的序列 （ 30 位）。
为了保存子串的频率，这里使用哈希表。
首先当取出第十个字符时，将其存在哈希表里，和该字符串出现频率映射，之后每向左移三位替换一个字符，查找新字符串在哈希表里出现次数，如果之前刚好出现过一次，则将当前字符串存入返回值的数组并将其出现次数加一，如果从未出现过，则将其映射到 1。
解题代码 class Solution {public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
if (s.size() <= 10) return res;
int mask = 0x7ffffff, cur = 0;
unordered_map<int, int> m;
for (int i = 0; i < 9; ++i) {
cur = (cur << 3) | (s[i] & 7);
}
for (int i = 9; i < s.size(); ++i) {
cur = ((cur & mask) << 3) | (s[i] & 7);
if (m.count(cur)) {
if (m[cur] == 1) res.push_back(s.substr(i - 9, 10));
++m[cur];
} else {
m[cur] = 1;
}
}
return res;
}
};
5. 两个数组的交集
题目来源于 LeetCode 上第 349 号问题： Intersection of Two Arrays。
题目描述给定两个数组，编写一个函数来计算它们的交集。
题目解析容器类 set 的使用。
遍历 num1，通过 set 容器 record 存储 num1 的元素
遍历 num2，在 record 中查找是否有相同的元素，如果有，用 set 容器 resultSet 进行存储
将 resultSet 转换为 vector 类型
动画描述// 空间复杂度: O(n)
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> record;
for( int i = 0 ; i < nums1.size() ; i ++ ){
record.insert(nums1[i]);
}
set<int> resultSet;
for( int i = 0 ; i < nums2.size() ; i ++ ){
if(record.find(nums2[i]) != record.end()){
resultSet.insert(nums2[i]);
}
}
vector<int> resultVector;
for(set<int>::iterator iter = resultSet.begin(); iter != resultSet.end(); iter ++ ){
resultVector.push_back(*iter);
}
return resultVector;
}
};
6. 两个数组的交集 II
题目来源于 LeetCode 上第 350 号问题： Intersection of Two Arrays II。
题目描述给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]
题目解析
与上题 两个数组的交集 类似。只不过这里使用的是 map 。
遍历 num1，通过 map 容器 record 存储 num1 的元素与频率；