Junyuan's Homepage

242. 有效的字母异位词

题目链接：click here
文章讲解：click here
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
示例 2: 输入: s = “rat”, t = “car” 输出: false
说明: 你可以假设字符串只包含小写字母。
思路：
不仅要求字母相同，还要求相同字母出现的次数完全相同。
可以把 s 以 {键，值} = {元素，次数} 的形式，存在 unordered_map 里，
然后遍历 t，检测 t 内元素是否在 unordered_map 中存在，不存在直接报错。
存在则将对应 ‘值’ 减一。
最后遍历 unordered_map 的所有元素，值全为0，则输出 true, 反之 false。
讲解思路：
大同小异，使用了数组来完成 ‘值’ 的初始化，以及限制总体内存开销，并减少 hash function 的计算。
事实上，可以把 ‘char’ - ‘a’ 视为自定义 hash function。
在已经数据规模的条件下，判断有限总数的元素集合中某个元素是否曾出现过，可以使用数组来优化内存。

代码：

class Solution
{
public:
    bool isAnagram(string s, string t)
    {
        std::unordered_map<char, int> um;
        for (auto &c_s : s)
        {
            if (um.find(c_s) == um.end())
            {
                um[c_s] = 1;
            }
            else
            {
                um[c_s]++;
            }
        }

        for (auto &c_t : t)
        {
            if (um.find(c_t) == um.end())
            {
                return false;
            }
            else
            {
                um[c_t]--;
                if (um[c_t] < 0)
                {
                    return false;
                }
            }
        }

        for (auto item : um)
        {
            if (item.second != 0)
            {
                return false;
            }
        }
        return true;
    }
};

讲解代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i] != 0) {
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

时空复杂度分析：
完整遍历两个string：O(n) 时间复杂度
使用unordered_map存储：O(n) 空间复杂度
使用数组存储：O(1) 空间复杂度

349. 两个数组的交集

题目链接：click here
文章讲解：click here
题目描述：给定两个数组，编写一个函数来计算它们的交集。
思路：
所谓求交，就是求大家都有的部分。
先把数组1转到set1里去重，再遍历数组2，查找元素是否存于set1中，若是，则转存到set_res里。
这里用了两个set, set1是为了给数组1去重，set_res是为了给结果去重，本质上也是对数组2去重。
讲解思路：
对结果没有顺序要求，从底层实现出发，可以选用 unordered_set 代替 set，二者的底层分别是哈希表和红黑树，显然前者的插入和搜索效率更高。
set 可以很方便地从 vector 生成，调用 set 的构造函数，传入 vector 的起始、终止迭代器即可；同理，vector也是，这些内置的数据结构彼此之间转换和拷贝数据都可以这样进行。

代码：

class Solution
{
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        std::unordered_set<int> set_res;
        std::unordered_set<int> set_1(nums1.begin(), nums1.end());

        for (auto &num : nums2)
        {
            if (set_1.find(num) != set_1.end())
            {
                set_res.insert(num);
            }
        }

        return std::vector<int>(set_res.begin(), set_res.end());
    }
};

时空复杂度分析：
遍历数组2，将数组1转为 u_set，将 u_set 转为结果输出：O(n+m) 时间复杂度
使用unordered_set存储数组1和结果：O(n) 空间复杂度

202. 快乐数

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

思路：

我一开始很好奇这个循环过程中，一直不变成1，该如何退出循环。
讲解提供了关键点“结果是无限循环的”，解题方法就清楚了。
首先需要会通过对正整数模10除10法提取各个位置上的数字。然后累加其平方和，计算完成后，
检查最终结果是否为1，是，则返回 True, 反之则检查结果是否已经存在于 unordered_set 里，若存在，说明循环，返回 False,
若不存在，将结果存入 unordered_set 里，以备后续检索重复出现的历史值。

因为这里无需其有序，只是为了搜索历史值是否重复出现，所以选用具有降重功能最轻便的 unordered_set。

代码：

class Solution
{
public:
    bool isHappy(int n)
    {
        std::unordered_set<int> res_;

        int temp = n;
        while (true)
        {
            int res = 0;
            while (temp > 0)
            {
                int factor = temp % 10;
                res += factor * factor;
                temp /= 10;
            }
            if (res == 1)
            {
                return true;
            }

            if (res_.find(res) == res_.end())
            {
                res_.insert(res);
            }
            else
            {
                return false;
            }

            temp = res;
        }
    }
};

时间复杂度：O(logn)
空间复杂度：O(logn)
这里还不是很理解为什么？
数字 n 的位数大约是 log10(n) !，所以会做log10(n)次乘法
而快乐数的迭代是有限的，要不然是快乐数，退出，要不然陷入循环然后主动退出，所以while的次数是有上限的，进而时间复杂度就是内部的乘法次数，即O(logn)。
另外，就空间而言，由于上述过程有限，所以 res_ 需要存储的结果也是有限的，不会高达O(n)量级，所以空间复杂度就是O(logn)这个量级。

1. 两数之和

题目链接：click here
文章讲解：click here
题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
思路：
前向遍历数组，将遍历过的数及其下标存储在能快速搜索的哈希表里，当前遍历的结果通过哈希表快速查找想要的历史值（这里的目的是当前值+某个历史值 = target，所以查找时用 target-当前值来作为键，能找到，二者相加即为target）。
若能找到，则可输出结果。

有点像SLAM里存储历史关键帧的描述子，构建词袋，然后实时帧的描述子在词袋中进行检索，能检索到相似的，就构建一帧候选回环。
这里面描述子向量若能通过合理的 hash function 转为 hash key，存 hash value（一般是对应帧点云、Pose的指针），则后续的描述子就能以O(1)的速度查找词袋中是否有相似描述子。相关工作见：BTC: A Binary and Triangle Combined Descriptor for 3D Place Recognition.

代码：

class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        std::unordered_map<int, int> um;
        int index = 0;
        for (auto &num : nums)
        {
            if (um.find(target - num) == um.end())
            {
                um.insert({num, index++});
            }
            else
            {
                return std::vector<int>({index, um[target - num]});
            }
        }

        return std::vector<int>();
    }
};

时间复杂度：O(n) 遍历一遍数组
空间复杂度：O(n) 存储一遍数组

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
有效的字母异位词：规模有限的比对问题，可以先用有限大小的数组保存其中一个词条的字频，再遍历另一个词条核对字频
字频一致则比对成功。
两个数组的交集：求交问题，需要利用 u_set 做去重，另外还掌握了 std 容器之间相互转换的构造方法，传入旧容器的起止迭代器即可。
快乐数：核心的是理解题意中，若不快乐，会无限循环。意味着，识别循环可以用u_set(哈希表)。
两数之和：技巧题，利用哈希表来存储、查找历史值，利用哈希表，将当前值与历史值快速比对是否 match，本题 match 的准则是 target - now = history，以后可能会遇到变种。
耗时：2h

Junyuan Lu(陆俊元)

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

242. 有效的字母异位词

349. 两个数组的交集

202. 快乐数

1. 两数之和

今日收获