您现在的位置是：首页 >其他 >代码随想录刷题第6天|哈希表 LeetCode242、LeetCode349、LeetCode202、LeetCode1网站首页其他

1、LeetCode242 有效的字母异位词

题目链接：242、有效的字母异位词

用哈希表，record[s[i]-'a']++，record[t[i]-'a']--，最后判断record里是否有元素不为0。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++)
        {
            record[s[i] - 'a']++;
        }
        for (int j = 0; j < t.size(); j++)
        {
            record[t[j] - 'a']--;
        }

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

        }
        return true;
    }
};

2、LeetCode349、两个数组的交集

题目链接：349、两个数组的交集

题目如果没有限制数值的大小，就无法使用数组来做哈希表。如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。此时就要使用另一种结构体set。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(), nums1.end());

        for (int i = 0; i < nums2.size(); i++)
        {
            if (nums_set.find(nums2[i]) != nums_set.end())
            {
                result_set.insert(nums2[i]);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

题目如果限制了数值的大小，用数组的方法如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        int hash[1005] = {0};
        for (int i = 0; i < nums1.size(); i++)
        {
            hash[nums1[i]] = 1;
        }

        for (int j = 0; j < nums2.size(); j++)
        {
            if (hash[nums2[j]] == 1)
            {
                result_set.insert(nums2[j]);
            }
        }

        return vector<int>(result_set.begin(), result_set.end());
    }
};

3、LeetCode202 快乐数

题目链接：202、快乐数

取数值各个位上的单数操作。

如果sum曾经出现过，说明已经陷入了无限循环了，立刻return false。

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        unordered_set<int> set;
        while (1)
        {
            int sum = getSum(n);
            if (sum == 1)
            {
                return true;
            }
            else
            {
                // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
                if (set.find(sum) != set.end())
                {
                    return false;
                }
                else{
                    set.insert(sum);
                }
            }
            n = sum;
        }
    }
};

4、LeetCode1 两数之和

题目链接：1、两数之和

用map哈希表,查看所需要的元素在之前是否遍历过，不用每个值都去遍历一遍数组寻找所需要的元素。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for (int i = 0; i < nums.size(); i++)
        {
            int s = target - nums[i];
            auto iter = map.find(s);
            if (iter != map.end())
            {
                return {iter->second, i};
            }
            map.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
};