随想录Day5|242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

242. 有效的字母异位词

文章&视频讲解

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

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

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

来自卡尔的提示：用数组

第一想法

只要两个字符串的无序版本是一样的就可以了，本来脑子里浮现出的是类似Python的dict，形如{char: frequency, ...}，然后再判断是否一致。但是既然只包含小写字母那就可以只开一个长度为26的数组，分别记录26个字母的出现次数。

悄悄看了一眼题解，更方便的方法是遍历s时在freq数组中++，遍历t时在freq数组中--，当且仅当数组最终全为0的时候两个字符串是异位词。数组第i个位置的值就是第i个字母出现的次数。

用时9min~

bool isAnagram(string s, string t)
{
    int freq[26] = {0};
    for (int i = 0; i < s.size(); i++)
        freq[s[i] - 'a']++;
    for (int i = 0; i < t.size(); i++)
        freq[t[i] - 'a']--;
    for (int i = 0; i < 26; i++)
    {
        if (freq[i] != 0)
            return false;
    }
    return true;
}

349. 两个数组的交集

文章&视频讲解

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

来自卡尔的提示：用set

直接看题解了

感觉这个就是学用容器的事情，以及学到了range-based for循环的写法。主要就是熟悉接口和写法用的。

用时9min~

vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
{
    unordered_set<int> result;
    unordered_set<int> nums1_set(nums1.begin(), nums1.end());
    for (int num : nums2)
    {
        if (nums1_set.find(num) != nums1_set.end()) // nums2中的元素nums1中出现过
            result.insert(num);
    }
    return vector<int>(result.begin(), result.end());
}

202. 快乐数

文章讲解

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

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

提示：1 <= n <= 2^31 - 1

来自卡尔的提示：用set

第一想法

有点没头绪，由于是int类型，取得每一个数位的值，就是while循环不断除以10直到个位？那是不是专门写个处理这个逻辑的函数比较好，输入数字，输出每个数位的平方和。然后在isHappy中循环，如果有1就直接true，如果无限循环怎么办呢？

那就把之前的中间结果都存在unordered_set中，如果出现重复的就说明循环？并不是，不一定有重复结果就说明陷入了无限循环。

看了随想录题解的想法

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

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false，否则一直找到sum为1为止。

所以可以保证这个过程得到的数字总是无限循环的，相当于题目告诉我们这个性质总是成立，所以确实一旦有重复结果就说明陷入了无限循环。

用时20min~

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 (true)
    {
        int sum = getSum(n);
        if (sum == 1)
            return true;
        // sum重复了，已经陷入无限循环
        if (set.find(sum) != set.end())
            return false;
        else
            set.insert(sum);
        n = sum;
    }
}

1. 两数之和

文章&视频讲解

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

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

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

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

来自卡尔的提示：用map

第一想法

如果暴力扫描就是\(O(n^2)\)，那就没意思了！如果化为map则按照“值：下标”的格式，值有序排列。是否还可以类似二分搜索的思想？或者扫描一遍，辗转着往后移（好像不太对），哦还可以在数值num的时候在map中寻找target - num，如果不存在则下一个，否则返回答案。感觉很合理！

看了随想录题解的想法

可以用auto写iter好方便！并且学到了返回的比较好的写法！问了poe assistant，得到如下回答：

在C++中，return {i, j}表示返回一个初始化了两个值 i 和 j 的匿名对象。这个匿名对象的类型是根据花括号中的值进行推断的。

如果 i 和 j 具有相同的类型，那么返回的匿名对象类型将是一个std::pair（或者是其它的元组类型，具体取决于编译器的实现）。例如，如果 i 和 j 都是整数类型，那么返回的类型将是 std::pair<int, int>。

如果 i 和 j 具有不同的类型，那么返回的匿名对象类型将是一个std::tuple（或者是其它的元组类型）。例如，如果 i 是整数类型，而 j 是浮点数类型，那么返回的类型将是 std::tuple<int, float>。

时空复杂度均为\(O(n)\)。

用时13min~

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