算法训练day6Leetocode242有效字母异位词349两个数组交集202快乐数1两数之和

今天学习的文章和视频链接

https://www.bilibili.com/video/BV1YG411p7BA/?vd_source=8272bd48fee17396a4a1746c256ab0ae

https://www.bilibili.com/video/BV1aT41177mK/?vd_source=8272bd48fee17396a4a1746c256ab0ae

242 有效字母提示词

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

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

 

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
示例 2:

输入: s = "rat", t = "car"
输出: false
 

提示:

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

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

哈希基础

https://blog.csdn.net/qq_36372352/article/details/135376702?spm=1001.2014.3001.5501

我的想法

利用数组来做，用两个数组存储两个字符串的hash表，进行比较

题目分析

哈希值比较小且范围可控一般使用数组，用数组做映射最直接，映射速度最快

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。这一步确实妙，只用一个数组解决了问题，进一步节省空间。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

我的acm完整代码

# include <iostream>
# include <string>

class Solution {
public:
    bool isAnagram(std::string s, std::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;
    }
};

int main () {
    std::string s = "anagram";
    std::string t = "nagaram";
    Solution sol;
    if (sol.isAnagram(s,t)) {
        std::cout << "true" <<std::endl;
    }
    else {
        std::cout << "false" << std::endl;
    }
}

349两个数组的交集

题目描述

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

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
 

提示：

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

题目分析

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

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

std::set
std::multiset
std::unordered_set

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

我的acm代码

# include <iostream>
# include <vector>
# include <unordered_set>

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

int main() {
    std::vector<int> nums1 = {1,2,2,5,1};
    std::vector<int> nums2 = {2,2,5,6};
    std::vector<int> result;
    Solution sol;
    result = sol.intersection(nums1, nums2);
    for (int i = 0; i < result.size(); i++) {
        std::cout << result[i] << " ";
    }
    return 0;
}

好的，让我们用中文来分析这段代码：

头文件：

: 这个头文件被包含进来了，但在代码中并未使用。通常，它用于输入和输出操作。
: 这个头文件用于包含 std::vector 容器，它在这段代码中被用来存储整数数组。
<unordered_set>: 这个头文件包含了 std::unordered_set 容器，它在代码中用于存储唯一元素，以帮助找出两个数组的交集。
类定义：

类 Solution 定义了一个公共成员函数 intersection，用于计算两个整数数组的交集。
函数 intersection：

参数：接受两个引用类型的 std::vector 参数，分别表示两个整数数组。
std::unordered_set result_set: 用于存储最终的交集结果。
std::unordered_set nums_set(nums1.begin(), nums1.end()): 创建一个包含 nums1 所有元素的无序集合（哈希集合），以便快速查找。
循环遍历 nums2 中的每个元素，并检查该元素是否存在于 nums_set 中。如果存在，意味着该元素在两个数组中都出现过，因此将其添加到 result_set。
最后，函数返回一个新的 std::vector，包含了 result_set 中的所有元素。这个新向量是通过 result_set 的迭代器范围构造的。
复杂度分析：

时间复杂度：O(N + M)，其中 N 和 M 分别是 nums1 和 nums2 的长度。这是因为需要遍历这两个数组来构建集合和检查元素。
空间复杂度：O(N + M)，最坏情况下，如果两个数组没有交集，可能需要存储两个数组的所有元素。
优化建议：

如果已知两个数组的大小，可以先遍历较小的数组以减少哈希集合的大小，这可能会稍微提高效率。
由于 在代码中未使用，可以考虑移除此头文件，以清理代码。
总体来说，这段代码是一个有效的解决方案来找出两个整数数组的交集。它使用哈希集合来提高查找效率。

202 快乐数

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

「快乐数」 定义为：

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

提示：

1 <= n <= 231 - 1

题目分析

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

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

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

判断sum是否重复出现就可以使用unordered_set。

代码

class Solution {
public:
    // 取数值各个位上的单数之和
    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(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

1 两数之和

题目描述

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

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

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

 

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

提示：

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

题目分析

我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

再来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

这道题目中并不需要key有序，选择std::unordered_map 效率更高！ 使用其他语言的录友注意了解一下自己所用语言的数据结构就行。

接下来需要明确两点：

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

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

acm代码

#include <iostream>
#include <unordered_map>
#include <vector>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> map;
        std::vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            int tmp = target - nums[i];
            auto iter = map.find(tmp);
            if (iter == map.end()) {
                //  map.insert(nums[i], 0);
                map.insert(std::pair<int, int>(nums[i], i)); 
            }
            else {
                return {iter->second, i};
            }
        }
        return {};
    }
};

int main() {
    std::vector<int> nums = {2, 7, 11, 15}; // 示例数组
    int target = 9; // 目标值

    Solution solution;
    std::vector<int> result = solution.twoSum(nums, target);

    if (!result.empty()) {
        std::cout << "Indices: " << result[0] << " and " << result[1] << std::endl;
    } else {
        std::cout << "No two sum solution found." << std::endl;
    }

    return 0;
}

我遇到的问题

例数组
int target = 9; // 目标值

Solution solution;
std::vector<int> result = solution.twoSum(nums, target);

if (!result.empty()) {
    std::cout << "Indices: " << result[0] << " and " << result[1] << std::endl;
} else {
    std::cout << "No two sum solution found." << std::endl;
}

return 0;

}

## 我遇到的问题

map.insert(nums[i], 0); 是不正确的，这会导致编译错误。正确的插入方法是 map.insert(std::pair<int, int>(nums[i], i));