c++打卡

一、哈希表理论

• 哈希表用途：快速判断一个元素是否在集合里
• 定义：哈希表是根据关键码的值而直接进行访问的数据结构
• 好处：枚举的时间复杂度为O(n),而使用哈希表，时间复杂度为O(1)
• 三种哈希结构：数组、集合set、映射map
  • 使用场景：
  • 集合：unordered_set查询、增删快，且不重复，set有序，multiset有序且允许重复数据

二、242.有效的字母异位词

1. 标记字母出现次数

    vector\<int\> record[26] = {0};
    record[string[i] - 'a']++;
   

2. 思路：利用数组记录字符串中数字出现的次数，若相同，则位有效的字母异位词

三、349.两个数组的交集

1. 学会数据结构unordered_set：无序，元素一定不重复

    //初始化
    unordered_set\<int\> set;
    //插入元素
    set.insert(1);
    //删除元素
    set.erase(1);
    //判断元素是否在集合中
    if (set.find(1) != set.end())
   

2. 环境循环：遍历容器的元素

    vector\<int\> set;
    for (int x : set) {
        //循环体
    }
   

3. 代码尚有问题

    //如何用迭代器初始化？
    unordered_set\<int\> nums_set(nums1.begin(), nums1.end());
    //如何用迭代器生成vector？
    return vector\<int\>(result_set.begin(), result_set.end());
   

四、202.快乐数

1. 求各个位数之和

    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10);//取模
            n /= 10;//除去最低位
        }
        return sum;
    }
   

2. 此题考验数学思维

五、1.两数之和

1. 把问题归结为：使遍历数组，对于遍历到的每个数a，看能否在map中找到target - a

2. map键值对的插入方法

    map.insert(pair\<int, int\>(a, b))
   

3. 自动声明变量的关键字auto