HackerRank‐Dictionaries and Hashmaps - a920604a/leetcode GitHub Wiki

title: DictionariesandHashmaps categories: - interview-preparation-kit - HackerRank comments: false

Hash Tables: Ransom Note

字典的使用

def checkMagazine(magazine, note):
    # Write your code here
    mp = dict()
    for word in magazine:
        mp[word] = mp.get(word, 0)+1
    for word in note:
        if mp.get(word,0)==0:
            print("No")
            return
        else :
            mp[word]-=1
    print("Yes")
void checkMagazine(vector<string> magazine, vector<string> note) {
    unordered_map<string, int> mp;
    for(string str:magazine) mp[str]++;
    for(string n:note){
        if(mp[n]==0){
            cout<<"No";
            return ;
        }
        else mp[n]--;
    }
    cout<<"Yes";
    return;

}

analysis

  • time complexity O(n)
  • space complexity O(n)

Two Strings

def twoStrings(s1, s2):
    # Write your code here
    s = set()
    for c in s1:
        s.add(c)
    for c in s2:
        if c in s:
            return "YES"
    return "NO"
string twoStrings(string s1, string s2) {
    unordered_set<char> s;
    for(char c:s1) s.insert(c);
    for(char c:s2){
        if(s.find(c)!=s.end()) return "YES";
    }
    return "NO";
}

analysis

  • time complexity O(n)
  • space complexity O(n)

Count Triplets *

需要兩組字典，分別紀錄 過去及未來的 數字出現頻率。

long countTriplets(vector<long> arr, long r) {
    unordered_map<long,long> mr, ml;
    for(int a:arr) mr[a]++;
    int n = arr.size();
    long count=0;
    for(int i=0;i<n;++i){
        mr[arr[i]]--;
        if(arr[i]%r==0){
            count+= ml[arr[i]/r] * mr[arr[i]*r];
        }
        ml[arr[i]]++;
    }
    return count;
}

analysis

  • time complexity O(n)
  • space complexity O(n)

Frequency Queries

需要兩組字典

def freqQuery(queries):
    freq = dict()
    freq2num = defaultdict(int)
    ans = list()
    for (op, val) in queries:
        if op ==1:
            if val not in freq:
                freq[val] = 1
                freq2num[1]+=1
            else:
                idx = freq[val]
                freq2num[idx]-=1
                freq[val] +=1
                freq2num[idx+1]+=1
        elif op ==2:
            idx = freq.get(val,0)
            if idx==0:
                 continue
            freq[val]-=1
            freq2num[idx]-=1
            if idx-1>0:
                freq2num[idx-1]+=1
        else:
            if freq2num[val]:
                ans.append(1)
            else:
                ans.append(0)
    return ans
  
vector<int> freqQuery(vector<vector<int>> queries) {
    vector<int> ret;
    unordered_map<int,int> mp; // value to freq
    unordered_map<int,int> imp; // count map to the number of key's freq
    for(vector<int> q:queries){
        int op = q[0];
        if(op ==  1){
            if(!mp.count(q[1])){
                mp[q[1]]=1;
                imp[1]++;
            }
            else{
                int t = mp[q[1]];
                imp[t]--;
                imp[t+1]++;
                mp[q[1]]++;
            }
        }
        else if(op ==2){
            int t = mp[q[1]];
            if(t==0) continue;
            imp[t]--;
            mp[q[1]]--;
            if(t-1>0) {
                imp[t-1]++;
            }
        }
        else if(op==3){
            if(imp[q[1]]>0 ){
                ret.push_back(1);
            }
            else{
                ret.push_back(0);
            }
        }
    }
    return ret;
}

analysis

  • time complexity O(n)
  • space complexity O(n)

Sherlock *

int sherlockAndAnagrams(string s) {
    int count = 0, n=s.size();
    unordered_map<string,int> mp; 
    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){ 
            string tmp = s.substr(i,j-i+1);
            sort(tmp.begin(), tmp.end());
            mp[tmp]++;
        }
    }
    for(auto m:mp){
        if(m.second > 1 ) count += (long)(m.second)*(m.second -1 )/2;
    }
    return count;
}

analysis

  • time complexity O(n^3 log n)
  • space complexity O(n^2)

footer

⚠️ **GitHub.com Fallback** ⚠️