代码随想录算法训练营第五天 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

代码随想录算法训练营第五天 | 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

最近有点忙，哈希表章节的博客可能没有以前那么多图和那么详细了。不过忙完这段时间我可能会回来补的。

有效字母异位词

题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

思路

这题是我们直接使用数组就可以完成任务，题目中有几点比较关键

• s,t的每个字符出现次数要相同
• s,t要包含同样的字符

于是我们的数组就可以设置为下标代表26个字母，数组所包含的值作为字符出现的次数。

接下里就先遍历s，出现的字符直接在对应的数组位置上++；然后再遍历t，出现的字符直接在对应的数组位置上–；最终数组元素全部归零即为有效字母异位词。

代码

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 i = 0; i < t.size(); i++)
        {
            record[t[i]-'a']--;
        }
        for(int j = 0; j < 26 ; j++)
        {
            if(record[j]!=0)
            {
                return false;
            }
        }
        return true;
    }
};

两个数组的交集

题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

思路

首先，交集是集合，那么我们使用std::set<int>当然是最好的，其特点相信只要高中学过集合都知道是无序不可重复。先把一个数组的所有元素加入set中（有重复元素，set会自动过滤），然后再遍历另外一个数组，对每个元素使用find，若在set中找到了改元素，则留下（在交集中），找不到的，就删去

代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //使用集合set
        set<int> s;
        for(int i = 0; i < nums1.size(); i++)
        {
            s.insert(nums1[i]);
        }
        vector<int> result;
        for(int i = 0; i < nums2.size(); i++)
        {
            if(s.find(nums2[i]) != s.end())
            {
                result.push_back(nums2[i]);
                s.erase(nums2[i]);
            }
        }
        return result;
    }
};

快乐数

题目链接/文章讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

思路

这题要注意这几点：

• 什么时候会出现无限循环：

  a → b → c → a a\rightarrow b\rightarrow c\rightarrow a a→b→c→a从这可以看出如果出现了之前出现的数那么就会陷入循环（有点像数电中的计数器的自启动）所以我们可以用哈希表记录出现过的和

• 如何分开每位数并求和：

  利用%10取最高位，用/10去除最高位

代码

class Solution {
public:
    bool isHappy(int n) {
        set<int> s;
        while(s.find(n)==s.end())
        {
            s.insert(n);
            int sum = 0;
            while(n)
            {
                int temp = n%10; //取最高位
                sum+=temp*temp;
                n = n/10;//去最高位
            }//这个可以看出模版
            
            if(sum==1)
            {
                return true;
            }
            n = sum;
        }
        return false;
    }
};

两数之和

题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

思路

这题用哈希表就很简单了。直接遍历数组，对于每一个元素，先find一下看看哈希表中有没有对应的相加为target的元素，有则返回，无则加入到哈希表中。

• 这里我们使用unordered_map，其搜索速度快！时间复杂度为O（1），并且每一个数映射（map）为其数组下标，方便直接返回

代码

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

今天的题还比较简单，主要是掌握哈希表的思路