Open in app

Sign in

Write

Sign in

Algorithms & Data Structures : Hash Problems

吳建興
8 min readJul 27, 2022

--

Problems

LeetCode 718. Maximum Length of Repeated Subarray
[rolling hash]

LeetCode 2034. Stock Price Fluctuation
[hash map + ordered map]

LeetCode : 245. Shortest Word Distance III
[hash table]

LeetCode : 2295. Replace Elements in an Array
[hash table]

LeetCode : 2260. Minimum Consecutive Cards to Pick Up
[hash table]

LeetCode : 1865. Finding Pairs With a Certain Sum
[hash table]

LeetCode : 1797. Design Authentication Manager
[hash table]

LeetCode : 2284. Sender With Largest Word Count
[hash table][string]

LeetCode : 325. Maximum Size Subarray Sum Equals k
[hash table]

LeetCode : 2408. Design SQL
[Hash Table][String][Array]

LeetCode : 2001. Number of Pairs of Interchangeable Rectangles
[Hash Table][Number Theory][Array][Math]

LeetCode : 2032. Two Out of Three
[hash table]

LeetCode : 2062. Count Vowel Substrings of a String
[hash table][string]

LeetCode : 2094. Finding 3-Digit Even Numbers
[hash table][sorting]

—

LeetCode 706. Design HashMap
[hash function]

LeetCode 705. Design HashSet
[hash function]

LeetCode 572. Subtree of Another Tree
[hash function]

LeetCode 1. Two Sum
[hash table]

LeetCode 718. Maximum Length of Repeated Subarray

在做這題之前，可能要先學會快速冪取模
然後我的算法原本是看這一篇，後來發覺用 rolling hash 一直解不出來 ( 原本是使用 DP 解) ， 最後受不了就看答案了QQ。

#define MOD 1000000007
#define BASE 113
#define LL long long
/*
   MOD  :大質數
   BASE :大於 nums[i] 的質數
   quickPowMod : 快速冪取模
   pinv == p^(-1) == (p ^ (MOD - 2)) % MOD
 */class Solution {   
private:    
    LL pinv;
public:
    LL quickPowMod(LL base, LL n) {
        LL res = 1;
        while(n > 0) {
            if(n & 1) {
                res = res * base % MOD;
            }   
            base = base * base % MOD;
            n = n >> 1;
        }
        return res;
    }
    
    // 每個 len 分別檢查
    // 減少 collision 的機率
    // 並且可對 len 做二分搜
    bool check(int len, vector<int> &A, vector<int> &B) {
        unordered_map<int, vector<int>> um;    
        
        LL H = 0;
        LL nowBase = 1;
        for(int i = 0;i < len;i++) {
            H += (A[i] * nowBase) % MOD;
            H %= MOD;
            if(i < len - 1) {
                nowBase = (nowBase * BASE) % MOD;
            }
        }        um[H].push_back(0);
        
        for(int i = len;i < A.size();i++) {
            H = (H - A[i - len]) * pinv % MOD;
            H += (A[i] * nowBase) % MOD;
            H %= MOD;
            um[H].push_back(i - len + 1);
        }
        
        H = 0;
        nowBase = 1;
        
        for(int i = 0;i < len;i++) {
            H += (B[i] * nowBase) % MOD;
            H %= MOD;
            
            // nowBase == BASE^(len - 1)
            if(i < len - 1) {
                nowBase = (nowBase * BASE) % MOD;
            }
        }
                
        if(um.find(H) != um.end()) {
            vector<int> &v = um[H];
            bool res = true;
            for(int i = 0;i < v.size();i++) {
                int indexA = v[i];
                int indexB = 0;
                for(int j = 0;j < len;j++) {
                    if(A[indexA] != B[indexB]) {
                        res = false;
                        break;
                    }
                    indexA++;
                    indexB++;
                }
            }
            if(res) {
                return true;
            }
        }
        
        for(int i = len;i < B.size();i++) {
            H = (H - B[i - len]) * pinv % MOD;
            H += (B[i] * nowBase) % MOD;
            H %= MOD;
            
            if(um.find(H) != um.end()) {
                vector<int> &v = um[H];
                bool res = true;
                for(int j = 0;j < v.size();j++) {
                    int indexA = v[j];
                    int indexB = i - len + 1;
                    for(int q = 0;q < len;q++) {
                        if(A[indexA] != B[indexB]) {
                            res = false;
                            break;
                        }
                        indexA++;
                        indexB++;
                    }
                }
                if(res) {
                    return true;
                }
            }
        }
                
        return false;
    }
    
    int findLength(vector<int>& A, vector<int>& B) {
        
        pinv = quickPowMod(BASE, MOD - 2);
         
        int left = 1;
        int right = min(A.size(), B.size());
        int mid = 0;
        int res = 0;
        while(left <= right) {
            mid = (left + right) / 2;
            if(check(mid, A, B)) {
                res = max(mid, res);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }        return res;
    }
};

LeetCode 2034. Stock Price Fluctuation

TODO : 效能太差了，想想怎麼加速，或是看其他人的實作方式。

class StockPrice {
private:
    int newestT = 0;
    int currentVal = -1;
    unordered_map<int, int> t2p;
    map<int, int> p2n;
public:
    StockPrice() {
    }
    
    void update(int timestamp, int price) {
        if(timestamp >= newestT) {
            currentVal = price;
            newestT = timestamp;
        }
        
        if(t2p.find(timestamp) != t2p.end()) {
            int tmpPrice = t2p[timestamp];
            p2n[tmpPrice]--;
            if(0 == p2n[tmpPrice]) {
                p2n.erase(tmpPrice);
            }
            
        }
        t2p[timestamp] = price;
        p2n[price]++;
    }
    
    int current() {
        return currentVal;
    }
     
    int maximum() {
        return p2n.rbegin()->first;
    }
    
    int minimum() {
        return p2n.begin()->first;
    }
};

LeetCode : 245. Shortest Word Distance III

class Solution {
public:
    int shortestWordDistance(vector<string>& wordsDict, string word1, string word2) {
        
        unordered_map<string, int> um;
        
        int res = INT_MAX;
        
        for(int i = 0;i < wordsDict.size();i++) {
            if(wordsDict[i] == word1) {
                if(um.find(word2) != um.end()) {
                    res = min(res, i - um[word2]);
                }
            }
            
            if(wordsDict[i] == word2) {
                if(um.find(word1) != um.end()) {
                    res = min(res, i - um[word1]);
                }
            }
            
            um[wordsDict[i]] = i;
        }
        
        return res;
    }
};

LeetCode : 2295. Replace Elements in an Array

// 用 hash map 紀錄數字的對應
// 先走一遍 operations，之後再走一遍 numsclass Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        vector<int> res = vector<int>(nums.size());
        
        unordered_map<int, int> a2b;
        unordered_map<int, int> b2a;
        
        vector<vector<int>> &op = operations;
        for(int i = 0;i < op.size();i++) {
            if(b2a.find(op[i][0]) == b2a.end()) {
                a2b[op[i][0]] = op[i][1];
                b2a[op[i][1]] = op[i][0];
            } else {
                int tmp = b2a[op[i][0]];
                b2a.erase(op[i][0]);
                a2b[tmp] = op[i][1];
                b2a[op[i][1]] = tmp;
            }
        }
        for(int i = 0;i < nums.size();i++) {
            if(a2b.find(nums[i]) == a2b.end()) {
                res[i] = nums[i];
            } else {
                res[i] = a2b[nums[i]];
            }
        }
        
        return res;
    }
};

LeetCode : 2260. Minimum Consecutive Cards to Pick Up

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int ans = INT_MAX;
        
        unordered_map<int, int> um;
        for(int i = 0;i < cards.size();i++) {
            if(um.find(cards[i]) != um.end()) {
                ans = min(ans, i - um[cards[i]] + 1);   
            }
            um[cards[i]] = i;
        }
        
        return ans == INT_MAX ? -1 : ans;
    }
};

LeetCode : 1865. Finding Pairs With a Certain Sum

class FindSumPairs {
private:
    unordered_map<int, int> um;
    vector<int> n1;
    vector<int> n2;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        n1 = nums1;
        n2 = nums2;
        for(int i = 0;i < nums2.size();i++) {
            um[nums2[i]]++;
        }
    }
    
    void add(int index, int val) {
        um[n2[index]]--;
        if(0 == um[n2[index]]) {
            um.erase(n2[index]);
        }
        n2[index] += val;
        um[n2[index]]++;
    }
    
    int count(int tot) {
        int ans = 0;
        for(int i = 0;i < n1.size();i++) {
            int goal = tot - n1[i];
            if(um.find(goal) != um.end()) {
                ans += um[goal];
            }
        }
        return ans;
    }
};/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(nums1, nums2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

LeetCode : 1797. Design Authentication Manager

class AuthenticationManager {
private:
    int ttl = 0; // timeToLive
    int ttk = 0; // total taskId
    
    // time 2 taskIds
    map<int, map<string, bool>> t2tks;
    
    // taskId 2 time
    unordered_map<string, int> tk2t;
    
    void expire(int currentTime) {
        while(t2tks.size() > 0 && t2tks.begin()->first <= currentTime) {
            map<string, bool> &tmp = t2tks.begin()->second;
            for(auto it = tmp.begin();it != tmp.end();it++) {
                tk2t.erase(it->first);
                ttk--;
            }
            
            t2tks.erase(t2tks.begin()->first);
        }
    }
    
public:
    
    AuthenticationManager(int timeToLive) {
        ttl = timeToLive;
    }
    
    void generate(string tokenId, int currentTime) {
        tk2t[tokenId] = currentTime + ttl;
        t2tks[currentTime + ttl][tokenId] = true;
        ttk++;
    }
    
    void renew(string tokenId, int currentTime) {
        expire(currentTime);
        if(tk2t.find(tokenId) == tk2t.end()) {
            return;
        }
        
        int oldTime = tk2t[tokenId];
        t2tks[oldTime].erase(tokenId);
        
        tk2t[tokenId] = currentTime + ttl;
        t2tks[currentTime + ttl][tokenId] = true;
    }
    
    int countUnexpiredTokens(int currentTime) {
        expire(currentTime);
        return ttk;
    }
};/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * AuthenticationManager* obj = new AuthenticationManager(timeToLive);
 * obj->generate(tokenId,currentTime);
 * obj->renew(tokenId,currentTime);
 * int param_3 = obj->countUnexpiredTokens(currentTime);
 */

LeetCode : 2284. Sender With Largest Word Count

class Solution {
public:
    int calc(string &s) {
        int c = 0;
        
        for(int i = 0;i < s.size();i++) {
            if(' ' == s[i]) {
                c++;
            }
        }
        
        return c + 1;
    }
    
    string largestWordCount(vector<string>& messages, vector<string>& senders) {
        string ans;
        
        unordered_map<string, int> um;
        
        // senders without duplication
        vector<string> se;
        
        for(int i = 0;i < messages.size();i++) {
            int sc = calc(messages[i]);
            
            if(um.find(senders[i]) == um.end()) {   
                se.push_back(senders[i]);
            }   
            um[senders[i]] += sc;
        }
        
        sort(se.begin(), se.end());
        
        int maxVal = 0;
        for(int i = se.size() - 1;i >= 0;i--) {
            int tmp = um[se[i]];
            if(tmp > maxVal) {
                maxVal = tmp;
                ans = se[i];
            }
        }
        
        return ans;
    }
};

LeetCode : 325. Maximum Size Subarray Sum Equals k

// TODO : 太慢了
#define LL long long
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        
        vector<LL> prefix = vector<LL>(nums.size(), 0);
        
        // sum2index
        unordered_map<LL, map<int, bool>> s2i;
        
        prefix[0] = nums[0];
        s2i[prefix[0]][0] = true;
        for(int i = 1;i < nums.size();i++) {
            prefix[i] = prefix[i - 1] + nums[i];
            s2i[prefix[i]][i] = true;
        }
        
        s2i[0][-1] = true;
        
        LL maxVal = INT_MIN;
        for(int i = prefix.size() - 1;i >= 0;i--) {
            LL target = prefix[i] - k;
            if(s2i.find(target) != s2i.end()) {
                int lefti = s2i[target].begin()->first;
                if(lefti <= i) {
                    maxVal = max(maxVal, (LL)i - lefti);
                }
            }
        }
        
        
        return maxVal == INT_MIN ? 0 : maxVal;
    }
};

LeetCode : 2408. Design SQL

// TODO : 效能太差
class SQL {
public:
    
    // tables
    vector<unordered_map<int, vector<string>>> ts;
    
    // tables id
    vector<int> ti;
    
    // string to index
    unordered_map<string, int> s2i;
    
    SQL(vector<string>& names, vector<int>& columns) {
        ti = vector<int>(names.size(), 1);
        ts = vector<unordered_map<int, vector<string>>>(names.size());
        
        for(int i = 0;i < names.size();i++) {
            s2i[names[i]] = i;
        }
    }
    
    void insertRow(string name, vector<string> row) {
        int table_index = s2i[name];
        
        ts[table_index][ti[table_index]] = row;
        ti[table_index]++;
    }
    
    void deleteRow(string name, int rowId) {
        int table_index = s2i[name];        
        ts[table_index].erase(rowId);
    }
    
    string selectCell(string name, int rowId, int columnId) {
        int table_index = s2i[name];
        vector<string> &ss = ts[table_index][rowId];
        return ts[table_index][rowId][columnId - 1];
    }
};/**
 * Your SQL object will be instantiated and called as such:
 * SQL* obj = new SQL(names, columns);
 * obj->insertRow(name,row);
 * obj->deleteRow(name,rowId);
 * string param_3 = obj->selectCell(name,rowId,columnId);
 */

LeetCode : 2001. Number of Pairs of Interchangeable Rectangles

// TODO : 效能太差了
#define LL long long
class Solution {
public:
    long long interchangeableRectangles(vector<vector<int>>& rectangles) {
        vector<double> dv = vector<double>(rectangles.size());
        for(int i = 0;i < rectangles.size();i++) {
            dv[i] = (double)rectangles[i][0] / (double)rectangles[i][1];
        }
        
        unordered_map<double, int> um;
        LL ans = 0;
        for(int i = 0;i < dv.size();i++) {
            ans += um[dv[i]];
            um[dv[i]]++;
        }
        
        return ans;
    }
};

LeetCode : 2032. Two Out of Three

class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        unordered_map<int, bool> ex;
        unordered_map<int, bool> exInAns;
        vector<int> ans;
        
        for(int i = 0;i < nums1.size();i++) {
            ex[nums1[i]] = true;
        }
        
        for(int i = 0;i < nums2.size();i++) {
            if(ex[nums2[i]] &&
               !exInAns[nums2[i]]) {
                exInAns[nums2[i]] = true;
                ans.push_back(nums2[i]);
            }
        }
        
        for(int i = 0;i < nums2.size();i++) {
            ex[nums2[i]] = true;
        }
        
        
        for(int i = 0;i < nums3.size();i++) {
            if(ex[nums3[i]] &&
               !exInAns[nums3[i]]) {
                exInAns[nums3[i]] = true;
                ans.push_back(nums3[i]);
            }
        }
        
        return ans;
    }
};

LeetCode : 2062. Count Vowel Substrings of a String

// TODO : 應該有複雜度更低的作法
class Solution {
public:
    bool isVowel(char c) {
        switch (c) {
        case 'a':
        case 'e':
        case 'i':
        case 'o':
        case 'u':
            return true;
        }
        return false;
    }

    bool check(vector<int> &alpha) {
        if (alpha['a' - 'a'] > 0 &&
            alpha['e' - 'a'] > 0 &&
            alpha['i' - 'a'] > 0 &&
            alpha['o' - 'a'] > 0 &&
            alpha['u' - 'a'] > 0) {
            return true;
        }
        return false;
    }

    int countVowelSubstrings(string word) {
        int ans = 0;
        vector<int> alpha = vector<int>(26, 0);
        for(int i = 0;i < word.size();i++) {
            for(int j = i;j < word.size();j++) {
                if (isVowel(word[j])) {
                    alpha[word[j] - 'a']++;
                } else {
                    break;
                }
                if(check(alpha)) {
                    ans++;
                }         
            }
            alpha['a' - 'a'] = 0;
            alpha['e' - 'a'] = 0;
            alpha['i' - 'a'] = 0;
            alpha['o' - 'a'] = 0;
            alpha['u' - 'a'] = 0;
        }
        return ans;
    }
};

LeetCode : 2094. Finding 3-Digit Even Numbers

// TODO : 效能太差，程式碼有點醜
class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        unordered_map<int, bool> um;
        vector<int> ans;
        for(int i = 0;i < digits.size();i++) {
            for(int j = 0;j < digits.size();j++) {
                if (i == j) {
                    continue;
                }
                for(int k = 0;k < digits.size();k++) {
                    if (i == k || j == k) {
                        continue;
                    }
                    if (digits[i] == 0) {
                        continue;
                    }
                    if (digits[k] % 2 != 0) {
                        continue;
                    }
                    int tmp = 100 * digits[i] +
                              10 * digits[j] + 
                              digits[k];
                    if (um.find(tmp) == um.end()) {
                        ans.push_back(tmp);
                        um[tmp] = true;
                    }
                }
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};
Algorithms

--

--

吳建興
吳建興

Written by 吳建興

42 Followers
49 Following

I want to be a good programmer.(´・ω・`)

No responses yet

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams