本次作业完成了力扣《面试经典 150 题》「哈希表」部分的全部题目。
力扣 面试经典 150 题 - 哈希表
LeetCode 383. 赎金信
思路
因为只有小写字母，所以可以用一个长度为 $26$ 的数组来记录每个字母出现的次数，然后遍历 ransomNote，如果字母出现次数大于 $0$ 则减一，否则返回 false。
代码
提交记录：8 ms (97.72%) / 8.78 MB (37.45%)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int cnt[26] = { 0 };
for (auto &i : magazine) ++cnt[i - 97];
for (auto &i : ransomNote) if (cnt[i - 97] > 0) --cnt[i - 97]; else return false;
return true;
}
};
LeetCode 205. 同构字符串
思路
因为映射关系是一一对应的，所以可以用两个数组来记录映射关系，遍历 s 和 t，如果当前字母没有映射关系，则建立映射关系，否则判断是否与之前的映射关系相同。
代码
提交记录：4 ms (97.78%) / 6.89 MB (94.40%)
class Solution {
public:
bool isIsomorphic(string s, string t) {
char x[128] = { 0 }, y[128] = { 0 };
for (int i = 0; i < s.length(); ++i)
if (!x[s[i]] && !y[t[i]]) x[s[i]] = t[i], y[t[i]] = 1;
else if (x[s[i]] != t[i]) return false;
return true;
}
};
LeetCode 290. 单词规律
思路
由于相同的字母必须对应相同的单词，所以可以用一个长度为 $26$ 的数组来记录每个字母对应的单词，同时用一个集合来记录已经出现过的单词，遍历 pattern 和 s，如果当前字母没有对应的单词且当前单词没有出现过，则建立映射关系，否则判断是否与之前的映射关系相同。
代码
提交记录：36 ms (91.58%) / 15.63 MB (48.20%)
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
x = [''] * 26
S = set()
s = s.split()
if len(s) != len(pattern):
return False
for i in range(len(pattern)):
if x[ord(pattern[i]) - 97] == '' and s[i] not in S:
x[ord(pattern[i]) - 97] = s[i]
S.add(s[i])
elif x[ord(pattern[i]) - 97] != s[i]:
return False
return True
LeetCode 242. 有效的字母异位词
思路
最简单的办法是排序后比较，但是时间复杂度为 $O(n \log n)$，可以先遍历 s，用一个长度为 $26$ 的数组来记录每个字母出现的次数，然后遍历 t，如果字母出现次数大于 $0$ 则减一，否则返回 false。
代码
提交记录：4 ms (97.83%) / 7.48 MB (21.91%)
class Solution {
public:
bool isAnagram(string s, string t) {
int x[26] = { 0 };
if (s.length() != t.length()) return false;
for (auto &i : s) ++x[i - 97];
for (auto &i : t) if (x[i - 97] == 0) return false; else --x[i - 97];
return true;
}
};
LeetCode 49. 字母异位词分组
思路
字母异位词排序后相同，所以可以用一个哈希表来记录每个单词排序后的结果，然后遍历 strs，如果当前单词排序后的结果没有出现过，则建立映射关系，否则将当前单词加入到对应的答案数组中。
代码
提交记录：20 ms (99.12%) / 19.11 MB (77.76%)
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> M;
vector<vector<string>> ans;
for (auto &str : strs) {
string x = str;
sort(x.begin(), x.end());
M[x].emplace_back(str);
}
for (auto &[key, value] : M) ans.emplace_back(value);
return ans;
}
};
LeetCode 202. 快乐数
思路
可以使用哈希表来记录每个数是否出现过，如果出现过则说明进入了循环，返回 false，否则继续计算下一个数，直到出现 $1$ 为止。
代码
提交记录：0 ms (100.00%) / 6.62 MB (6.26%)
class Solution {
public:
bool isHappy(int n) {
int ans;
unordered_set<int> S;
auto nxt = [&] (int x) { for (ans = 0; x; x /= 10) ans += (x % 10) * (x % 10); };
while (n != 1) if (S.count(n)) return false; else S.insert(n), nxt(n), n = ans;
return true;
}
};
LeetCode 219. 存在重复元素 II
思路
可以使用哈希表来记录每个数上一次出现的位置，然后遍历 nums，如果当前数出现过且距离上一次出现的位置小于等于 $k$ 则返回 true，否则更新当前数的位置。如果最终没有找到相邻 $k$ 个数中的重复元素，则返回 false。
代码
提交记录：132 ms (87.15%) / 69.34 MB (93.24%)
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> S;
for (int i = 0; i < nums.size(); S.insert(nums[i++]), i > k && S.erase(nums[i - k - 1])) if (S.count(nums[i])) return true;
return false;
}
};
LeetCode 128. 最长连续序列
思路
方法 $1$：首先可以对数组进行排序，然后遍历数组，如果当前数与上一个数不连续，则更新答案，否则继续计算当前连续序列的长度。时间复杂度为 $O(n \log n)$。虽然时间复杂度不符合题目要求，但常数很小，代码跑得很快。
方法 $2$：为了满足题目要求的复杂度，可以先将数组中的数放入哈希表，然后遍历数组，如果当前数是连续序列的第一个数，则计算当前连续序列的长度。这样每个数都只会在内层循环中被访问一次，因此时间复杂度为 $O(n)$。但是由于 unordered_set 的常数比较大，所以虽然算法的理论复杂度很优秀，但代码跑得比方法 $1$ 慢很多。
代码
方法 $1$：提交记录：68 ms (99.10%) / 43.92 MB (90.90%)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int ans = 0, now = 0, lst = -1000000000;
sort(nums.begin(), nums.end());
for (auto &i: nums)
if (lst + 1 < i) ans = max(ans, now), now = 1, lst = i;
else now += i - lst, lst = i;
return max(ans, now);
}
};
方法 $2$：提交记录：1180 ms (14.15%) / 67.64 MB (30.83%)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> S;
int ans = 0;
for (const auto &i : nums) S.insert(i);
for (const auto &i : nums) if (!S.count(i - 1)) for (int now = 0; S.count(i + now) || (ans = max(ans, now)) && 0; ++now);
return ans;
}
};
