当前位置 博文首页 > pushup8的博客:LeetCode分类刷题(五):哈希表(Hash Table)
哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。哈希表简单的理解:在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。
使用哈希查找有两个步骤:
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
C++中unordered_map 与 map 的对比:
LeetCode中关于哈希表的题目有以下三种类型题:
(一)哈希表之数组相关题目:
(二)哈希表之字符串相关题目:
(三)哈希表之应用实例相关题目:
1.?Two Sum
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res(2, -1);
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++){
if(hash.count(target - nums[i])){
res[0] = hash[target - nums[i]];
res[1] = i;
return res;
}else{
hash[nums[i]] = i;
}
}
return res;
}
};
454.?4Sum II
(i, j, k, l)
?there are such that?A[i] + B[j] + C[k] + D[l]
?is zero.class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int n = A.size(), res = 0;
unordered_map<int, int>hash1, hash2;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
hash1[A[i] + B[j]]++;
hash2[C[i] + D[j]]++;
}
}
for(auto m : hash1) res += m.second * (hash2[-m.first]);
return res;
}
};
217.?Contains Duplicate
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++){
if(hash.find(nums[i]) != hash.end()) return true;
else hash[nums[i]] = i;
}
return false;
}
};
349.?Intersection of Two Arrays
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set(nums1.begin(), nums1.end());
vector<int> res;
for(auto num : nums2){
if(set.count(num)) res.push_back(num);
}
unordered_set<int> res_set(res.begin(), res.end());
return vector<int>(res_set.begin(), res_set.end());
}
};
350.?Intersection of Two Arrays II
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> hash;
vector<int> res;
for(auto num : nums1) hash[num]++;
for(auto num : nums2){
if(hash[num]-- >0) res.push_back(num);
}
return res;
}
};
290.?Word Pattern
pattern
?and a string?str
, find if?str
?follows the same pattern.Here?follow?means a full match, such that there is a bijection between a letter in?pattern
?and a?non-empty?word in?str
.class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, int>hash1;
unordered_map<string, int>hash2;
istringstream in(str);
int i = 0;
for(string word; in >> word; i++){
if(hash1.find(pattern[i]) != hash1.end() || hash2.find(word) != hash2.end()){
if(hash1[pattern[i]] != hash2[word]) return false;
}else{
hash1[pattern[i]] = i + 1;
hash2[word] = i + 1;
}
}
return i == pattern.size();
}
};
205.?Isomorphic Strings
class Solution {
public:
bool isIsomorphic(string s, string t) {
int n = s.size(), hash1[256] = {0}, hash2[256] = {0};
for(int i = 0; i < n; i++){
if(hash1[s[i]] != hash2[t[i]]) return false;
hash1[s[i]] = i + 1;
hash2[t[i]] = i + 1;
}
return true;
}
};
383.?Ransom Note
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<int, int> hash;
for(auto ch : magazine) hash[ch]++;
for(auto ch : ransomNote){
if(--hash[ch] < 0) return false;
}
return true;
}
};
500.?Keyboard Row
class Solution {
public:
vector<string> findWords(vector<string>& words) {
unordered_set<char> set1{'q','w','e','r','t','y','u','i','o','p'};
unordered_set<char> set2{'a','s','d','f','g','h','j','k','l'};
unordered_set<char> set3{'z','x','c','v','b','n','m'};
vector<string> res;
for(auto word : words){
int r1 = 0, r2 = 0, r3 = 0;
for(auto ch : word){
if(ch < 'a') ch += 32;
if(set1.count(ch)) r1 = 1;
if(set2.count(ch)) r2 = 1;
if(set3.count(ch)) r3 = 1;
if(r1 + r2 + r3 != 1) break;
}
if(r1 + r2 + r3 == 1) res.push_back(word);
}
return res;
}
};
593.?Valid Square
class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
unordered_set<int> set{get_distance(p1, p2),get_distance(p1, p3),get_distance(p1, p4),get_distance(p2, p3),get_distance(p2, p4),get_distance(p3, p4)};
return !set.count(0) && set.size() == 2;
}
int get_distance(vector<int>& m, vector<int>& n){
return (m[0]-n[0])*(m[0]-n[0]) + (m[1]-n[1])*(m[1]-n[1]);
}
};
554.?Brick Wall
class Solution {
public:
int leastBricks(vector<vector<int>>& wall) {
int mx = 0;
unordered_map<int, int> hash;
for(auto row : wall){
int sum = 0;
for(int i = 0; i < row.size() - 1; i++){
sum += row[i];
hash[sum]++;
mx = max(mx, hash[sum]);
}
}
return wall.size() - mx;
}
};
525.?Contiguous Array
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int res = 0, sum = 0;
unordered_map<int, int> hash{{0, -1}};
for(int i = 0; i < nums.size(); i++){
sum += (nums[i] == 1) ? 1 : -1;
if(hash.count(sum)) res = max(res, i - hash[sum]);
else hash[sum] = i;
}
return res;
}
};
560.?Subarray Sum Equals K
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int sum = 0, res = 0;
unordered_map<int, int> hash{{0, 1}};
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
res += hash[sum - k];
hash[sum]++;
}
return res;
}
};
299.?Bulls and Cows
A
?to indicate the bulls and?B
?to indicate the cows.?class Solution {
public:
string getHint(string secret, string guess) {
int m[256] = {0}, bulls = 0, cows = 0;
for(int i = 0; i < secret.size(); i++){
if(secret[i] == guess[i]) bulls++;
else{
if(m[secret[i]]-- > 0) cows++;
if(m[guess[i]]++ < 0) cows++;
}
}
return to_string(bulls) + "A" + to_string(cows) + "B";
}
};
如果各位看官们,大神们发现了任何错误,或是代码无法通过OJ,或是有更好的解法,或是有任何疑问,意见和建议的话,请一定要在帖子下面评论区留言告知博主啊,多谢多谢,祝大家刷得愉快,刷得精彩,刷出美好未来~
cs