目录
菜鸟做题第一周，语言是 C++
1 基础知识
1.1 定义哈希表
unordered_map<string, vector<string>> hashtable;- unordered_map 用于定义哈希表
- 第一个参数为 key 的数据类型，这里是 string 类型
- 第二个参数为 value 的数据类型，这里是 vector<string> 类型
1.2 遍历哈希表
for (auto str:hashtable) {
// code
}- 这种遍历方法对其他容器也适用
- 冒号后写遍历的对象，这里是 hashtable
- 冒号前写被遍历到的元素，这里取名为 str
1.3 查找某一个键
auto it = hashtable.find(target);
if (it != hashtable.end()) {
// code
}- find() 的参数是想要查找的 key
- it 是本次查找的结果
- 若没有找到，则 it 等于 hashtable.end()
- hashtable.end() 是哈希表最后一个元素的后一位
1.4 插入键值对
// 方法一
hashtable[key] = value;
// 方法二
hashtable[key].push_back(value);- 目前看到过上述两种方法
- key 处填写键，value 处填写值
这是看人下碟，暂时还不太懂
1.5 获取键值对的值
// 方法一
str->second
// 方法二
str.second- 同样看到过两种方法
- str 是哈希表中的某一键值对
- second 代表想要获取的是 value
1.6 搜索功能
作用：搜索某个键是否存在于哈希表内。
hashtable.count(key)- count 的作用是搜索而不是计数
- key 代表想要搜索的键
- 若存在该键，则返回值为 1
2 三道题
2.1 1. 两数之和
解题思路：
- 遍历数字集合 nums
- 查询是否有和为 target 的另一个数字
思路说明图：
- 这里假设 target=9
- 将暂时没找到伴儿的数字放入哈希表中
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashmap;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashmap.find(target - nums[i]);
if (it != hashmap.end()) {
return {i, it->second};
}
hashmap[nums[i]] = i;
}
return {};
}
};可能出现的问题：
虽然题设表明一定能找到一对和为 target 的数字，但力扣比较严谨，它要求 if 判断结构中的 else 情况也要进行返回（虽然用不到）。
2.2 49. 字母异位词分组
解题思路：
- 遍历 strs 中的每一个字符串
- 使用 sort 函数对这些字符串进行重新排序
- 排序前的字符串作为 key，排序后的字符串作为 value，插入到哈希表中
- 哈希表中每个键值对的 value 的集合即为最终的结果
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> result;
unordered_map<string, vector<string>> hashtable;
for (auto str:strs) {
auto temp = str;
sort(temp.begin(), temp.end());
hashtable[temp].push_back(str);
}
for (auto str:hashtable) {
result.push_back(str.second);
}
return result;
}
};
这个涉及到哈希表的原理，即 key 相同时，如何存储不同的 value，暂时还没看
2.3 128. 最长连续序列
解题思路：
- 遍历 nums 寻找可能成为序列头的数字（不能存在 num - 1）
- 若找到可能成为序列头的数字，则顺着它找序列并计数（哈希表找 num + 1）
- 每计数完一条序列的长度都要和之前序列的长度进行比较（cucount 和 count）
- 返回最长的长度（count）
思路说明图：
思考过程：
一开始想的是找序列中最小的那个数字（我理所应当地认为它就是序列头），然后以它为开头去找序列并计数，但 nums 中可能存在不止一条连续序列，因此我们需要考虑所有可能的序列头。
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.size() == 0) return 0;
int count = 1;
unordered_map<int, int> hashmap;
for (int i = 0; i < nums.size(); ++i) {
hashmap[nums[i]] = i;
}
for (auto num:nums) {
auto it = hashmap.find(num - 1);
if (it == hashmap.end()) {
int cucount = 1;
it = hashmap.find(num + cucount);
while (it != hashmap.end()) {
++cucount;
it = hashmap.find(num + cucount);
}
count = max(count, cucount);
}
}
return count;
}
};哈希表并不是最优解，因为貌似用不到 value，但我目前只会哈希表。。。
