[代码随想录算法训练营14期]-Day6-第三章 哈希表part01

Day6-第三章 哈希表part01

---

---

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

---

做题思路

判断两个字符串中小写字母出现的次数是否相同，这里可以使用数组来充当哈希表的作用，把字母a～z分别放入哈希表即数组中存放，数组下标0处存放字母a出现的次数，依此重复，将s字符串中的字符出现的次数存在数组中，再对t字符串循环，字符出现一次即减去次数，最后若 s 和 t 中每个字符出现的次数都相同，哈希表（数组）所有值为零，否则不是字母异位词。

1.bug

• 最后一个for循环判断条件写错i<26
• 数组要赋初值为0

1.代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26]= {0};
        for(int i = 0; i < s.size(); i++){
            hash[s[i]-'a']++;
        }
        for(int i = 0; i < t.size(); i++){
            hash[t[i]-'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(hash[i] != 0)
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数

---

做题思路

自己没有思路，每计算一次sum要查询之前是否出现过来跳出循环。

1.bug

• set.find()如果找不到则返回最后一个元素

2.代码

class Solution {
public:
    int getsum(int n){
        int sum = 0;
        while(n > 0){
            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{
                //set.find()如果找不到则返回最后一个元素
                if(set.find(sum) != set.end())
                    return false;
                else
                    set.insert(sum);
            }
            n = sum;
        }
    }
};
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

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

---

做题思路

第一次做思路是排序以后锁定一个后二分查找，但是排序以后下标就变了，所以不能用这个方法，暴力法的复杂度是n方，故可以使用哈希表：判断一个元素是否出现过，用map存放值和下标，每遍历一个数就要查询另一个正好和为target的数是否在map中出现过，如果存在返回下标，不存在则放入map中

2.bug

• 不熟悉map需要学习

1.代码

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};
            else
                map[nums[i]] = i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

• 判断一个元素是否出现集合里的时候，就要考虑哈希法。