4-哈希表

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

1207. 独一无二的出现次数

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int,int> umap;
        unordered_set<int> uset;
        for(int x:arr)umap[x]++;
        for(auto x:umap) uset.insert(x.second);
        return uset.size() == umap.size();
    }
};

剑指 Offer 50. 第一个只出现一次的字符

class Solution {
public:
    char firstUniqChar(string s) {
        int pos[26];
        int cnt[26] = {0};
        for(int i = s.size() - 1; i >= 0;i--)
        {
            cnt[s[i] - 'a']++;
            pos[s[i] - 'a'] = i;
        }
        int res = INT_MAX;
        for(int i = 0;i < 26;i++)
        {
            if(cnt[i] == 1 && res > pos[i])
            {
                res = pos[i];
            }
        }
        return res == INT_MAX ? ' ': s[res];
    }

242. 有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int arr[26] = {0};
        for (int i = 0; i < s.size(); ++i) {
            arr[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); ++i) {
            arr[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; ++i) {
            if (arr[i]!=0) return false;
        }
        return true;
    }
};

49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,vector<string>> umap;
        for(string s:strs)
        {
            string t = s;
            sort(s.begin(),s.end());
            umap[s].push_back(t);
        }
        for(auto x:umap) res.push_back(x.second);
        return res;
    }
};

438. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(p.size() > s.size()) return {};
        unordered_map<char,int> p_umap;
        for(char x:p) p_umap[x]++;
        unordered_map<char,int> s_umap;
        vector<int> res;
        for(int i = 0; i < s.size();i++)
        {
            s_umap[s[i]]++;
            if(i >= p.size()) 
            {
                s_umap[s[i - p.size()]]--;
                if(s_umap[s[i - p.size()]] == 0)s_umap.erase(s[i - p.size()]);
            }
            if(s_umap == p_umap) res.push_back(i - p.size() + 1);
        }
        return res;
    }
};

349. 两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> uset1(nums1.begin(),nums1.end());
        unordered_set<int> uset2(nums2.begin(),nums2.end());
        vector<int> res;
        for(int x : uset1) 
        {
            if(uset2.find(x) != uset2.end()) res.push_back(x);
        }
        return res;
    }
};

350. 两个数组的交集 II

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> umap1;
        for(int x:nums1) umap1[x]++;
        vector<int> res;
        for(int x:nums2)
        {
            if(umap1[x] > 0) 
            {
                res.push_back(x);
                umap1[x]--;
            }
        }
        return res;
    }
};

202. 快乐数

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> num;
        while(true)
        {
            int sum = 0;
            while(n)
            {
                sum += pow(n % 10,2);
                n /= 10;
            }
            if(sum == 1)  return true;
            if(num.find(sum) == num.end())num.insert(sum);
            else return false;
            n = sum;
        }
        return true;
    }
};

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> umap;
        for(int i = 0; i < nums.size() ;i++)
        {
            if(umap.find(target - nums[i]) != umap.end()) return {i,umap[target - nums[i]]};
            else umap[nums[i]] = i;
        }
        return {};
    }
};

454. 四数相加 II

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> umap1;
        unordered_map<int,int> umap2;
        for(auto x:nums1)
            for(auto y:nums2)
                umap1[x+y]++;
        for(auto x:nums3)
            for(auto y:nums4)
                umap2[x+y]++;
        int res = 0;
        for(auto x:umap1)
        {
            if(umap2.find(-x.first) != umap2.end()) res += x.second * umap2[-x.first];
        }
        return res;
    }
};

383. 赎金信

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int map[26]={0};//制作map
        for (auto  i :magazine) map[i - 'a']++;//遍历i++
        for (auto  i :ransomNote) map[i - 'a']--;
        for (int i = 0; i < 26; ++i)
            if (map[i] < 0) return false;
        return true;

    }
};

205. 同构字符串

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        unordered_map<char,char> umap;
        unordered_map<char,char> umap2;
        for(int i = 0 ; i < s.size() ;i++) 
        {
            if(umap.find(s[i]) == umap.end()) 
            {
                umap[s[i]] = t[i];
                umap2[t[i]] = s[i];
            }
            else if(umap[s[i]] != t[i]) return false;
        }
        return umap.size() == umap2.size();
    }
};

1002. 查找共用字符

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        unordered_map<char,int> umap;
        for(char s = 'a' ; s <= 'z' ;s++)
        {
            int mins = INT_MAX;
            for(string ss:words)
            {
                mins = min(mins,(int)count(ss.begin(),ss.end(),s));
                if(mins == 0) break;
            }
            if(mins) umap[s] = mins;
        }
        vector<string> res;
        for(auto &x:umap)
        {
            while(x.second--) res.push_back(string(1,x.first));
        }
        return res;
    }
};

128. 最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        set<int> sets;
        for(int x:nums) sets.insert(x);
        int pre = INT_MIN, lenth = 1, max_len = 0;
        for(int x:sets) 
        {
            if(pre + 1 == x) lenth++;
            else lenth = 1;
            max_len = max(max_len,lenth);
            pre = x;
        }
        return max_len;
    }
};

594. 最长和谐子序列

class Solution {
public:
    int findLHS(vector<int>& nums) {
        map<int,int> mps;
        for(int x:nums) mps[x]++;
        int pre = INT_MIN , sum = 0 , res = 0;
        int pre_sum = 0;
        for(auto x:mps)
        {
            if(pre  == x.first - 1) res = max(pre_sum + x.second,res);
            pre = x.first;
            pre_sum = x.second;
        }
        return res;
    }
};

621. 任务调度器

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        unordered_map<char,int> umap;
        unordered_map<char,int> recent_use;
        for(char x: tasks) umap[x]++;
        int cur = 0;
        while(!umap.empty())
        {
            int mins = INT_MIN;
            char res = '-';
            for(auto &x: umap)
            {
                if((recent_use.find(x.first) == recent_use.end()|| cur - recent_use[x.first] > n) && mins < x.second)
                {
                    mins = x.second;
                    res = x.first;
                }
            }
            if(mins != INT_MIN) 
            {
                recent_use[res] = cur;
                umap[res]--;
                if(umap[res] == 0) 
                {
                    umap.erase(res);
                    recent_use.erase(res);
                }
            }
            //cout << res ;
            cur++;
        }
        return cur;
    }
};

LCR 014. 字符串的排列

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        if(s1.size() > s2.size()) return false;
        unordered_map<char,int> umap_s1;
        unordered_map<char,int> umap_s2;
        for(char x:s1) umap_s1[x]++;
        for(int i = 0; i < s1.size();i++) umap_s2[s2[i]]++;
        if(umap_s1 == umap_s2) return true;

        for(int i = 0; i < s2.size() - s1.size();i++)
        {
            umap_s2[s2[i]]--;
            umap_s2[s2[i + s1.size()]]++;
            if(umap_s2[s2[i]] == 0) umap_s2.erase(s2[i]);
            if(umap_s1 == umap_s2) return true;
        }
        return false;

    }
};

LCR 015. 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.size() < p.size()) return {};
        vector<int> res;
        unordered_map<char,int> umap_s;
        unordered_map<char,int> umap_p;
        for(char x:p) umap_p[x]++;
        for(int i = 0; i < p.size();i++) umap_s[s[i]]++;
        if(umap_s == umap_p) res.push_back(0);

        for(int i = 0; i < s.size() - p.size();i++)
        {
            umap_s[s[i]]--;
            umap_s[s[i + p.size()]]++;
            if(umap_s[s[i]] == 0) umap_s.erase(s[i]);
            if(umap_p == umap_s) res.push_back(i + 1);
        }
        return res;
    }
};

LCR 093. 最长的斐波那契子序列的长度

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //暴力求解
        int res = 0;
        unordered_map<int,int> umap;
        for(int i = 0 ;i < arr.size(); i++) umap[arr[i]] = i;
        for(int i = 0; i < arr.size() ;i++)
        {
            for(int j = i + 1 ; j < arr.size();j++)
            {
                int first = arr[i],second = arr[j],cur = 2;
                while(umap.find(first + second) != umap.end())
                {
                    cur++;
                    int t = first + second;
                    first = second;
                    second = t;
                }
                res = max(res,cur);
            }
        }
        return res < 3 ? 0 : res;
    }
};

1657. 确定两个字符串是否接近

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        int sz1 = word1.size(), sz2 = word2.size();
        if (sz1 != sz2) return false;
        vector<int> rc1(26, 0), rc2(26, 0);
        for (int i = 0; i < sz1; ++i) {
            rc1[word1[i] - 'a']++;
            rc2[word2[i] - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (rc1[i] == 0 && rc2[i] != 0 || rc1[i] != 0 && rc2[i] == 0) return false;
        }
        sort(rc1.begin(), rc1.end());
        sort(rc2.begin(), rc2.end());
        return rc1 == rc2;
}
};

面试题 16.10. 生存人数

class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        unordered_map<int,int> bi;
        unordered_map<int,int> de;
        for(int x : birth) bi[x]++;
        for(int x : death) de[x]++;
        int counts = 0;
        int maxx = 0 , res = 1900;
        for(int i = 1900; i < 2024; i++)
        {
            counts += bi[i];
            if(maxx < counts)
            {
                maxx = counts;
                res = i;
            }
            counts -= de[i];
        }
        return res;
    }
};

面试题 16.20. T9键盘

class Solution {
public:
    vector<string> getValidT9Words(string num, vector<string>& words) {
        vector<string> map({"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"});
        vector<string> res;
        for(string s : words)
        {
            if(num.size() == s.size())
            {
                int i = 0;
                for(; i < s.size();i++)
                {
                    if(map[num[i] - '0'].find(s[i]) == -1) break;
                }
                if(i == s.size())res.push_back(s);
            }
        }
        return res;

    }
};

面试题 16.21. 交换和

class Solution {
public:
    vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {
        int sum1 = accumulate(array1.begin(),array1.end(),0);
        int sum2 = accumulate(array2.begin(),array2.end(),0);
        int target = sum1 - sum2;
        //两个数组分别取一个数 得到指定值  target == 2 * a - 2 * b
        cout << target;
        unordered_set<int> uset;
        for(int x : array1) uset.insert(2 * x - target);
        for(int x : array2)
        {
            if(uset.find(2 * x) != uset.end()) return {(target +  2 * x) / 2 , x};
        }
        return {};
    }
};

299. 猜数字游戏

class Solution {
public:
    string getHint(string secret, string guess) {
        int bull = 0;
        int cow = 0;
        int secret_map[10] = {0};
        int guess_map[10] = {0};
        for(int i = 0; i < secret.size();i++)
        {
            secret_map[secret[i] - '0']++;
            guess_map[guess[i] - '0']++;
            if(secret[i] == guess[i]) bull++;
        }
        for(int i = 0; i < 10; i++)
        {
            cow += min(secret_map[i],guess_map[i]);
        }
        return to_string(bull) + "A" + to_string(cow - bull) + "B";
    }
};

1094. 拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        unordered_map<int,int> up;
        unordered_map<int,int> down;
        for(auto x:trips)
        {
            up[x[1]] += x[0];
            down[x[2]] += x[0];
        }
        int cur = 0;
        for(int i = 0; i <= 1000;i++)
        {
            cur += up[i] - down[i];
            if(cur > capacity) return false;
        }
        return true;
    }
};

1109. 航班预订统计

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
    vector<int> res(n);
    unordered_map<int,int> up;
    unordered_map<int,int> down;
    int cnt = 0;
    for(auto x : bookings) 
    {
        up[x[0]] += x[2];
        down[x[1] + 1] += x[2];
    }
    for(int i = 1; i <= n;i++)
    {
        cnt += up[i] - down[i];
        res[i - 1] = cnt;
    }
    return res;
    }
};

554. 砖墙

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int,int> umap;
        for(int i = 0; i < wall.size();i++)
        {
            int pre = 0;
            for(int x = 0;x < wall[i].size() - 1;x++) 
            {
                pre += wall[i][x];
                umap[pre]++;
            }
        }
        
        int height = wall.size();
        int res = height;
        for(auto x : umap) res = min(height - x.second, res);
        return res;
    }
};

888. 公平的糖果交换

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
        int a_count = accumulate(aliceSizes.begin(),aliceSizes.end(),0);
        int b_count = accumulate(bobSizes.begin(),bobSizes.end(),0);
        unordered_set<int> uset_a(aliceSizes.begin(),aliceSizes.end());
        unordered_set<int> uset_b(bobSizes.begin(),bobSizes.end());
        if(b_count > a_count)
        {
            int p = (b_count - a_count) / 2;
            for(int i : uset_a)
            {
                if(uset_b.count(i + p)) return {i,i + p};
            }
        }
        else
        {
            int p = (a_count - b_count) / 2;
            for(int i : uset_a)
            {
                if(uset_b.count(i - p)) return {i,i - p};
            }
        }
        return {};
    }
};

1128. 等价多米诺骨牌对的数量

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        unordered_map<int,int> umap;
        for(auto x : dominoes)
        {
            int k = x[0] > x[1] ? x[1] * 10 + x[0] : x[0] * 10 + x[1];
            umap[k]++;
        }
        int res = 0;
        for(auto x : umap)
        {
            if(x.second > 1) res += (1 + x.second - 1) * (x.second - 1) / 2;
        }
        return res;
    }
};

652. 寻找重复的子树

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string,int> umap;
        vector<TreeNode*> res;
        function<string(TreeNode*)> dfs = [&](TreeNode* root)->string{
            if(!root) return "";
            string ss = to_string(root->val) + " "+ dfs(root->left) +" "+ dfs(root->right);
            umap[ss]++;
            if(umap[ss] == 2) res.push_back(root);
            return ss;
        };
        dfs(root);
        return res;
    }
};