[数据结构与算法]哈希表的经典入门LeetCode题

242. 有效的字母异位词

思路:如果2个字符串中字母相同,返回true。
? ? ? ? 利用一个数组去处理，如果最后数组全为0,则返回true

class Solution {
public:
    bool isAnagram(string s, string t) {
    int ans[26];
    memset(ans,0,sizeof(ans));
    for(auto ch : s)
        ans[ch-'a']++;

    for(auto ch : t)
    {
        ans[ch -'a']--;
    }

    for(int i=0;i<26;i++) {
        if (ans[i] != 0)
            return false;
    }
        return true;
    }
};

136. 只出现一次的数字

思路:因为其他数字都会重复出现，hash_set剩下的就是需要返回的。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> hash_set;
        for (auto ch: nums) {
            if (hash_set.count(ch) == 0)
                hash_set.insert(ch);
            else
                hash_set.erase(ch);
        }
        return *hash_set.begin();
    }

};

217. 存在重复元素

思路:只要计数值不为0，就返回true

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s_1;
    for(auto ch : nums)
        if(s_1.count(ch) == 0)
            s_1.insert(ch);
        else
            return true;
    return false;
    }
};

349. 两个数组的交集

思路：第一个map用于除去nums1中重复元素

? ? ? ? ? 第二个map用于除去nums1与nums2中重复插入的数据

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
     unordered_set<int> hash_map;
     unordered_set<int> hash_map_2;
     for(auto ch : nums1)
         hash_map.insert(ch);

     vector<int> ans;
     for(auto ch : nums2)
     {
         if(hash_map.count(ch)!=0)
             hash_map_2.insert(ch);
     }

     for(auto it= hash_map_2.begin();it!=hash_map_2.end();it++)
         ans.push_back(*it);

        return ans;
    }
};

387. 字符串中的第一个唯一字符

class Solution {
public:
    int firstUniqChar(string s) {
     unordered_map<int,int> m;
     for(int i=0;i<s.size();i++)
         m[s[i]-'a']++;//0~26
     for(int i=0;i<s.size();i++)
     {
        if(m[s[i]-'a']==1)
            return i;
     }
        return -1;
    }
};

771. 宝石与石头

太简单了没什么好讲的。

执行用时：4 ms, 在所有 C++ 提交中击败了42.08%的用户
内存消耗：6.2 MB， 在所有 C++ 提交中击败了51.88%的用户

class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
    unordered_set<char> s_1;
    for(int i = 0 ;i <jewels.size();i++)
        s_1.insert(jewels[i]);
    int sum = 0;
    for(int i=0;i<stones.size();i++)
    {
        if(s_1.count(stones[i])!=0)
            sum++;
    }
    return sum;
    }
};

3. 无重复字符的最长子串

思路:滑动窗口?

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    if(s.length() == 0 || s.length() == 1)
        return s.length();

    unordered_set<char>  s_1;
    int ch_max=0,left=0;
    for(int i = 0; i <s.size() ;i++) {
        while (s_1.find(s[i]) != s_1.end()) {
            s_1.erase(s[left]);
            left++;
        }
        ch_max = max(ch_max , i - left + 1);
        s_1.insert(s[i]);
    }

        return ch_max;
    }
};