代码随想录 | Day07 | 哈希表：有效的字母异位词&&两个数组的交集&&快乐数

主要学习内容：
1.哈希表的使用
2.set的相关操作，find和count函数

242.有效的字母异位词

242. 有效的字母异位词 - 力扣（LeetCode）

解法：哈希表

思路：map容器一个记录字符一个记录数量不一样直接输出false即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size())
            return false;
        unordered_map<char,int> ps;
        unordered_map<char,int> pt;
        for(auto c:s)
            ps[c]++;
        for(auto c:t)
            pt[c]++;
        int n=s.size();
        for(auto c:s)
            if(ps[c]!=pt[c])
                return false;
        return true;
    }
    /*这样写可以少用一个哈希表
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size())
            return false;
        unordered_map<char,int> ps;
        for(auto c:s)
            ps[c]++;
        for(auto c:t)
            ps[c]--;
        int n=s.size();
        for(auto c:s)
            if(ps[c]!=0)
                return false;
        return true;
    }*/
};

349.两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

解法：哈希表

思路：

1.如果使用undered_map记录数字有没有出现过然后一一判断的话，会出现结果集合中重复元素的出现

比如nums1是1,2,2,1而nums2是2,2

res就会是2,2而不是2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int,int> p;
        for(auto c:nums1)
            p[c]++;
        for(auto c:nums2)
            if(p[c]!=0)
                res.push_back(c);
        return res;
    }
};

2.自认为改进了其实还是错的

把nums1和nums2对调一下就还是错的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        unordered_map<int,int> p;
        for(auto c:nums1)
            p[c]++;
        for(auto c:nums2)
            if(p[c]==1)
                res.push_back(c);
            else if(p[c]>1)
            {
                p[c]=0;
                res.push_back(c);
            }
        return res;
    }
};

3.正确写法是用set，set不允许重复，然后返回结果是直接用set初始化vector然后返回即可

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> r;
        unordered_set<int> s(nums1.begin(),nums1.end());
        for(int num:nums2)
            if(s.find(num)!=s.end())
                r.insert(num);
        return vector<int>(r.begin(),r.end());
    }
};

202.快乐数

202. 快乐数 - 力扣（LeetCode）

解法：哈希表

关键：要想到陷入了无限循环是有了重复的数字出现才导致了无限循环，第一次做没有想明白这一点

知道了这一点剩下的就很容易了

把所有得到的数字都加入到set中，有重复就说明无限循环然后直接false，没有重复最后肯定到1,等于1就返回true即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int getnum(int n)
    {
        int res=0;
        while(n)
        {
            res+=((n%10)*(n%10));
            n/=10;
        }
        return res;
    }
    bool isHappy(int n) {
        unordered_set<int> s;
        
        while(true)
        {
            int temp=getnum(n);
            if(temp==1)
                return true;
            if(s.count(temp))
                return false;
            s.insert(temp);
            n=temp;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对，就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

1.两数之和

梦开始的地方

1. 两数之和 - 力扣（LeetCode）

解法：哈希表

思路

用unordered_map来进行元素标记，first为nums[i]，second为对应元素下标i，然后再哈希表中查找target-i，能找到说明就是答案，找不到就说明没有答案

错误写法：

先建立了一张哈希表，然后再遍历一遍去匹配有没有答案，问题是如果碰到重复元素，map中只会记录一个，自然而然下标也只有一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> s;
        int l,r;
        for(int i=0;i<nums.size();i++)
            s[nums[i]]=i;
        for(auto c:nums)
            if(s.find(target-c)!=s.end())
            {
                l=s[c];
                r=s[target-c];
            }
        return {l,r};
    }
};

正确写法：

在第一遍遍历时候就开始找，这样做，重复元素的nums[i]和i就不会进入哈希表而是直接输出成为答案，从而避免了这样的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> s;
        for(int i=0;i<nums.size();i++)
        {
            auto it=s.find(target-nums[i]);
            if(it!=s.end())
                return {it->second,i};
            else
                s.insert({nums[i],i});
        }
        return { };
    }
};