leetcode哈希表hash table集合

1.two sum

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> m;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (m.find(target - nums[i]) != m.end()) {
                res.push_back(m[target-nums[i]]);
                res.push_back(i);
                return res;
            }
            m.insert({nums[i],i});
        }
        return res;
    }

811 Subdomain Visit Count

vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string,int> mp;
        vector<string> res;
        for (auto cd : cpdomains) {
            int i = cd.find(" ");
            int num = stoi(cd.substr(0,i));
            string s = cd.substr(i+1,cd.size()-1-i);
            mp[s] += num;
            for (int j = i+1; j < cd.size(); j++) {
                if (cd[j] =='.') {
                    mp[cd.substr(j+1,cd.size()-1-j)] += num;
                }
            }
        }
        for(auto m : mp) {
            res.push_back(to_string(m.second) +" " + m.first);
        }
        return res;
    }

500 Keyboard Row

 vector<string> findWords(vector<string>& words) {
        vector<string> res;
        unordered_map<char,int> mp;
        vector<string> key = {"qwertyuiop","asdfghjkl","zxcvbnm"};
        for (int i = 0; i < 3; i++) {
            for (char ch : key[i]) {
                mp[ch] = i;
            }
        }
        for (auto word : words) {
            int cl = mp[tolower(word[0])];
            bool flag = true;
            for (char ch : word) {
                if (mp[tolower(ch)] != cl)
                    flag = false;
            }
            if (flag)
                res.push_back(word);
        }
        return res;
    }

389.Find the Difference
思路：注意t中并不是和s中一样的排序，然后插入一个字符，而是打乱后插入一个字符。

char findTheDifference(string s, string t) {
        unordered_map<char,int> mp;
        for (char ch : s) {
            mp[ch]++;
        }
        char ans;
        for (char ch : t) {
            if (mp[ch]) mp[ch]--;
            else{
                ans = ch;
                break;
            }
        }
        return ans;
    }

349.Intersection of Two Arrays

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> n1(nums1.begin(),nums1.end()),res;
        for (auto num : nums2) {
            if (n1.find(num) != n1.end())
                res.insert(num);
        }
        return vector<int>(res.begin(),res.end());
    }

242.Valid Anagram

bool isAnagram(string s, string t) {
        unordered_map<char,int> mp;
        if (s.size() != t.size())
            return false;
        for (auto ch : s) {
            mp[ch]++;
        }
        for (char ch : t) {
            if (mp[ch]) mp[ch]--;
            else
                return false;
        }
        return true;
    }

217.Contains Duplicate

bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> mp;
        for (auto num : nums) {
            if (mp[num] == 1)
                return true;
            mp[num]++;
        }
        return false;
    }

387.First Unique Character in a String

 int firstUniqChar(string s) {
        unordered_map<char,int> mp;
        for (auto ch : s) {
            mp[ch]++;
        }
        for (int i = 0; i < s.size(); i++) {
            if (mp[s[i]] == 1)
                return i;
        }
        return -1;
    }

408.Longest Palindrome

 int longestPalindrome(string s) {
        unordered_map<char,int> mp;
        for (auto ch : s) {
            mp[ch]++;
        }
        set<char> charset(s.begin(),s.end());
        int count = 0;
        for(auto ch : charset) {
            if (mp[ch] >= 2)
                count += 2 * (mp[ch] / 2) ;
        }
        if (count < s.size())
            count += 1;
        return count;
    }

204.Count Primes

 int countPrimes(int n) {
        int count = 0;
        int limit = sqrt(n);
        vector<bool> valid(n,true);
        for (int i = 2; i <= limit; i++) {
            if (valid[i]) {
                for (int j = i * i; j < n; j += i) {
                    valid[j] = false;
                }
            }
        }
        for (int i = 2; i < n; i++) {
            if (valid[i]) count++;
        }
        return count;
    }

739

 vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size(),0);
        stack<int> st;
        for (int i = 0; i < temperatures.size(); i++) {
            while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
                int t = st.top();
                st.pop();
                res[t] = i - t;
            }
            st.push(i);
        }
        return res;
    }