代码随想录Day6

 · 2024-1-1 · 次阅读

代码随想录Day6|242. 有效的字母异位词|349. 两个数组的交集|第202题. 快乐数|1. 两数之和

[书籍资料](代码随想录 (programmercarl.com))

视频资料

242

思路和关键点记录：

字母移位词只有小写字母，哈希表大小a-z

只需要一个哈希表记录，另外一个删除即可

哈希表有三种数据类型可选：数组；set；map

分别对应的情况

  • 数组： 数据范围可控
  • set： 数据范围很大
  • key对应value的话用map

以下搬运代码随想录官网

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

那么再来看一下map ，在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

其他语言例如：java里的HashMap ，TreeMap 都是一样的原理。可以灵活贯通。

虽然std::set、std::multiset 的底层实现是红黑树，不是哈希表，std::set、std::multiset 使用红黑树来索引和存储，不过给我们的使用方式，还是哈希法的使用方式，即key和value。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。 map也是一样的道理。

这里在说一下，一些C++的经典书籍上 例如STL源码剖析，说到了hash_set hash_map，这个与unordered_set，unordered_map又有什么关系呢？

实际上功能都是一样一样的， 但是unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好，这就好比一个是官方认证的，hash_set，hash_map 是C++11标准之前民间高手自发造的轮子。

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

代码和记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) {
            return false; // 长度不相等，不可能是字母异位词
        }
        int rec[26] ={0};
        for(int i=0;i<s.size();i++){
            rec[s[i]-'a']++;
        }
        for(int j=0;j<t.size();j++){
            rec[t[j]-'a']--;
        }
        for(int i=0;i<26;i++){
            if(rec[i]!=0) return false;
        }
        return true;
    }
};

犯了一些傻鸟错误，emm不提也罢，大概就是把s和t写串了，之后一定注意。

349

思路和关键点记录

尝试用unordered_set解决 -效率最高的哈希存储方式。

unordered_set是去重的。

还有一种是multi_set；可以检查重复了几次

1
int count = myMultiSet.count(target_element);

以及set

std::set` 提供了快速的查找、插入和删除操作，时间复杂度为 O(log n)，其中 n 是元素的数量。

std::unordered_set提供了常数时间的平均复杂度的查找、插入和删除操作，即 O(1)，但最坏情况下的复杂度为 O(n)，通常情况下它比std::set` 更快。

具体需求来选择使用哪种容器。如果需要有序存储元素或者需要使用自定义比较函数进行排序，可以选择 std::set。如果只需要快速的查找、插入和删除操作，并且不关心元素的顺序，可以选择 std::unordered_set。

代码和记录

C++语法学习+1

1
2
3
4
5
6
for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }

代码随想录网站循环写法： int num:nums2没看懂，研究了一下，是等价于

1
int i=0;i<nums2.size();i++

关于C++的迭代器处理需要记忆

1
nums_set.find(num) != nums_set.end()

if (nums_set.find(num) != nums_set.end()): 这个 if 语句检查 num 是否存在于 nums_set 集合中。

  • nums_set.find(num) 会在 nums_set 中查找 num 的值。
  • 如果 num 在 nums_set 中找到，find 函数将返回一个指向 num 的迭代器。如果没找到，find 函数将返回一个指向 nums_set 结束位置的迭代器，即 nums_set.end()。
  • 所以，这个条件判断实际上是在看 num 是否存在于 nums_set 中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果的集合
        unordered_set<int> nums_set(nums1.begin(), nums1.end()); // 将nums1转换成集合

        // 遍历nums2的元素
        for(int i = 0; i < nums2.size(); i++){
            // 检查nums2的元素是否在nums_set中
            if(nums_set.find(nums2[i]) != nums_set.end()){
                result_set.insert(nums2[i]);
            }
        }

        return vector<int>(result_set.begin(), result_set.end()); // 将结果集转换回向量
    }
};

202

思路和关键点

这个题的核心在于取余数，来找各个位置

代码

代码一直超时目前还没解决等会解决了来更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> set;
        int sum=0;
        while(1){
            while(n){
                sum+=pow(n%10,2);         //从个位开始，每次拆掉靠右边的一位
                n/=10;
            }
                    if(sum==1)return true;
        if(set.find(sum)!=set.end()){
            return false;
        }
        else{
            set.insert(sum);
        }
        n=sum;
        }

    }
};

image-20240102001631908

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> s;
        
        while(1){
            int sum=0;
            while(n){
                sum+=pow(n%10,2);         //从个位开始，每次拆掉靠右边的一位
                n/=10;
                if (!n) cout << 1 << endl;
            }
            if(sum==1)return true;
            if(s.find(sum)!=s.end()){
                return false;
            }
            else{
                s.insert(sum);
            }
            n=sum;
        }
    }
};

sum要在循环里面置零

1.两数之和

思路

保存的是 键值对 ： 在K_V关系的哈希表中每次遍历存一次 如果没找到就存一次Key - 数组内元素，Value -数组下标

在使用c++ unordered_map时，存储KV值的方式是：

1
2
iter->second  //Value
iter->first		//key

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
     std::unordered_map <int,int> k_V;
     for(int i=0;i<nums.size();i++){
         auto it =k_V.find(target-nums[i]);
         if(it!=k_V.end()){	//核心代码，构造哈希表
             return {it->second,i};
         }
         k_V.insert(pair<int,int>(nums[i],i));
     }   
     return {};
    }
};

总结和记录

C++ 对于哈希表使用支持：

map set 数组
unordered_map unordered_set 有序
赏