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

题目一

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。

题目链接

自己的解法

思考

这道题可以用一个很暴力的方法，字母异位词的本质就是统计字母的数量，然后在另一个单词中一个一个的查
故方法如下：

class Solution
{
public:
    bool isAnagram(string s, string t)
    {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] >= 'a' && s[i] <= 'z')
                record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++)
        {
            if (t[i] >= 'a' && t[i] <= 'z')
                record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++)
        {
            if (record[i] != 0)
                return false;
        }
        return true;
    }
};

想法和随想录一样，挺好，难得。

题目二

题意：给定两个数组，编写一个函数来计算它们的交集。

题目链接

思考

这道题是不是也可以跟上一题一样，统计一下出现的字符然后进行比对

解法

class Solution
{
public:
    vector<int> intersection(vector<int> &num1, vector<int> &num2)
    {
        int record[26] = {0};
        vector<int> it;
        for (int i = 0; i < num1.size(); i++)
        {
            if (num1[i] >= 0 && num1[i] <= 10)
                record[num1[i] - 0]++;
        }
        for (int i = 0; i < num2.size(); i++)
        {
            if (num2[i] >= 0 && num2[i] <= 10)
                record[num2[i] - 0]--;
        }
        for (int i = 0; i < 26; i++)
        {
            if (record[i] != 0)
                it.push_back(i);
        }
        return it;
    }
};

运行没有问题，但提交就出错了

unordered_set

输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序

class Solution
{
public:
    vector<int> intersection(vector<int> &num1, vector<int> &num2)
    {
        unordered_set<int> nums_result;
        unordered_set<int> nums_set(num1.begin(), num1.end());
        for (int num : num2)
        {
            if (nums_set.find(num) != nums_set.end())
            {
                nums_result.insert(num);
            }
        }
        return vector<int>(nums_result.begin(), nums_result.end());
    }
};

果然简单了很多

题目三

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
题目链接

思考

无限循环？？？我怎么判断一个可能会无限循环的东西能不能达到我要的要求，这个是一个重点。看看随想录的思路：

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
按照这个思路试试

先求和

    int getSum(int n)
    {
        int sum = 0;
        while (n)
        {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }   

再算Happy数

bool isHappy(int n)
    {
        unordered_set<int> set;

        while (1)
        {
            int sum = getSum(n);
            if (sum == 1)
                return true;
            if (set.find(sum) != set.end())
                return false;
            else
                set.insert(sum);
            n = sum;
        }
    }

这个要切记查找元素的方法：set.find(sum) != set.end()

题目四

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题目链接

思路

也许双指针可以实现这个

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        for (int slow = 0; slow < nums.size() - 1; slow++)
        {
            for (int fast = slow + 1; fast < nums.size(); fast++)
            {
                if (nums[slow] + nums[fast] == target)
                {
                    return {slow, fast};
                }
            }
        }
        return {}; 
    }
};

map的解法

随想录用的是map

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

代码如下：¹

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. 今天代码没仔细看，只是抄了一遍，周日再看看 ↩︎