哈希表刷题笔记
AC 自动机
6345
2022.01.01
发布于 未知归属地
哈希表C++哈希字符串哈希哈希函数滚动哈希学习分享

前言

哈希表是一种通过计算代替比较的查找数据结构，它的身影实在太过于常见，现在的高级语言基本都内置了，无论是写项目，面试还是什么，哈希表基本是不可能离开的。将 hash 表的 value 变成是否存在，就变成 set 集合，也是非常常见的一个数据结构，主要用来判断是否 key 存在。本文就记录我刷哈希表的一些笔记。

分析

查找表有哈希表和集合，而集合基本就是在哈希表的基础上封装了一层，加了判重功能，故主要分析哈希表的实现。

哈希表是一种查找数据结构，即给定 key，找到对应的 value。相对于二分，查找树这些基于比较的数据结构，查找表能够将复杂度均衡在 ，而这也是它应用如此广泛的原因。

从数学的角度来看，哈希表就是一个单射，即 key→value 的映射。而从设计哈希表的角度上来看，我们主要考虑的就有：映射的方法，value 存在什么地方。

理想的映射自然是一一映射最好，但是实际上这很好能够实现， 故很多时候我们可能不同的 key 会映射到同一个 value 上，这就是哈希冲突，而这也是哈希表需要考虑的地方。

总的来说，设计哈希表，主要就是考虑这两点：哈希函数的设计+冲突的处理。

哈希函数

所谓哈希表函数，即 hash(key)=int，即把一个不同数据类型的 key 映射到一个整数上。而根据不同的类型，映射的函数也有所不同。

一般来说，设计哈希函数有这些设计原则：

  1. 映射均匀分布到桶中
  2. 雪崩效应，小的变动会使得 hash 改变非常大
  3. 利用原空间的数据特征

比如 int，float，char 这些本身就是整数存储的类型，通常可以直接用 key 来表示结果，而像 string，数组这些数据结构，则需要把每个元素都映射到结果中，至于树，图这些更加复杂的结构，还需要考虑映射节点间的关系等等。

一般在刷题中，比较常见的就是 int，char，string 这几个，int 和 char 直接映射到本身，而 string 则通常使用 RBKD 算法，即每位乘以一个系系数然后相加。

数组索引

拿到哈希函数的结果之后，我们还需要得到对应存储内存（数组）的具体索引，通常我们直接对数组长度取余即可。而像 java 这些语言的设计，还使用了位运算来取余等一些技巧。

扰动函数

在对数组取余获取索引时，有可能数组长度比较小，而哈希值很大，那么就可能冲突的概率很大。如

11000000000%10

12000000000%10

13000000000%10

上面就都冲突了，故我们通常会对哈希值扰动一遍，即把不同位扰动到其它位去，如 java8 就是把高 16 位和低 16 位异或。

哈希冲突

从数学的角度上来说，哈希函数是一定会冲突的。因为哈希函数本质就是集合的映射，而被映射的集合空间固定，无限集合映射到有限集合中，自然会冲突。

那么我们该怎么处理冲突呢？方法也很多，可以继续在这个集合里找一个空闲的位置，也可以开新的空间来存冲突值，通常有开链表，再开个哈希表等等方法。通常比较常见的是在对应位置开一个链表来存储冲突值。

初始化容量

在平时刷题中，我们可能直接开一个很大的初始数组来存储数据，但是如果要有一个合理的设计，如语言的标准库设计，则通常是有一个初始值，然后在特定的时候扩大容量。

而初始值怎么设定，什么时候扩容，怎么扩容等等，都是需要思考的问题。也是面试中的高频考点。

通常来说，有两种方法：

  1. 以质数为准，初始化容量设置一个质数，扩容的时候扩到一个质数
  2. 初始化和扩容设为 2 的倍数

一般像语言都是用到第二种方法，如 java 的初始容量就是 16.

扩容

当需要扩容的时候，怎么扩容呢？前面说了，一般扩容找上一个质数，或倍增，而一般都是使用的倍增方式。

一般扩容都是扩充一倍，如 java 就是 16→32→64...

扩容的时候，就直接再开一个哈希表复制一遍吗？

一般的语言的确是这么处理的，不过在一些高性能，高并发的中间件中，却不能直接这么处理，比如 Redis 数据量就在于千万级别，如果直接这样处理的话，业务会收到非常大的影响。而 Redis 的处理方法是使用写时复制技术，开新哈希表但是不直接复制，而是只有当数据更新时才修改。

负载因子

什么时候扩容？这也是一个比较重要的问题，假设扩容是的容量为 n，而最大容量为 m，则我们通常称 n/m 为负载因子。

而负载因子怎么去选择，也是非常重要的一点，如果太低，那么空间利用率太低，而太高，冲突又太多，时间会变慢。按照泊松分布的计算，一般设置为 是比较合理的，而具体是多少则要看具体的语言设置了，比如 Go 就是 0.65，而 JAVA 则是 0.75.

相关

通常哈希表的题型和下面这些术语都比较相关：

滚动哈希：计算子串的哈希值，如 RK 算法

桶：分桶，桶排序等

布隆塞：过滤

一致性 hash ：分布式负载均衡

bitmap、数组模拟：集合，模拟

原地 hash：直接利用原来的数组进行 hash

hash 的本质就是：哈希函数+存储空间。

而哈希函数在做题时，有：整数直接，字母-’a’ 等。

存储空间有新开数组，用 bitmap，用一个 int，原数组（原地hash） 等等。

对于 c++，有下面 6 种相关的数据结构：

集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
set红黑树有序否否O(logn)O(logn)
multiset红黑树有序是否O(logn)O(logn)
unordered_set哈希表无序否否O(1)O(1)
映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率
map红黑树有序否否O(logn)O(logn)
multimap红黑树有序是否O(logn)O(logn)
unordered_map哈希表无序否否O(1)O(1)

题型

设计

设计哈希表、用哈希表设计新数据结构等。

  • list

    705. 设计哈希集合

    题意

    分析

    优化

    效率

    时间复杂度：

    空间复杂度：

    代码

    struct bucket {
    int key;
    bucket *next;
        
    bucket() : key(0),next(nullptr) {};
    bucket(int k,bucket *n) : key(k),next(n) {};
    bucket(int k) : key(k),next(nullptr) {};
};

class MyHashSet {
    // 负载因子
    float loadFactor=0.65f;
    // 初始容量
    int capacity=1<<4;
    // 实际个数
    int size=0;
    // 存放数据的桶
    vector<bucket*> buckets;
    
public:
    MyHashSet() {
        buckets.resize(capacity);        
    }
    
    MyHashSet(int cap,float fac) {
        capacity=cap;
        loadFactor=fac;
        buckets.resize(cap);
    }
    
    void add(int key) {
        if(size>capacity*loadFactor){                        
            resize();
        }
        
        int i=indexfor(hash(key));

        if(!buckets[i]){
            buckets[i]=new bucket(key);
            size++;
            return;
        }
        
        if(buckets[i]->key==key){
            return;
        }        
        
        // cout<<"*"<<endl;
        
        bucket *b=buckets[i];
        while(b->next){
            if(b->next->key==key){
                return;
            }
            b=b->next;
        }
        
        size++;        
        b->next=new bucket(key);
    }
    
    bool contains(int key) {
        // cout<<"contains:"<<key<<endl;
        
        bucket *b=buckets[indexfor(hash(key))];
        if(!b){
            return false;
        }
    
        if(b->key==key){
            return true;
        }
        
        // cout<<"#"<<endl;        
      
        while(b){
            if (b->key==key){
                return true;
            }
            b=b->next;
        }
        return false;
    }

    void remove(int key) {
        int i=indexfor(hash(key));
        if (!buckets[i]){
            return;
        }
        
        if(buckets[i]->key==key){
            buckets[i]=nullptr;
            size--;
            return;
        }
        
        // cout<<"*"<<endl;
        
        bucket *b=buckets[i];
        while(b->next){
            if(b->next->key==key){
                b->next=b->next->next;
                size--;
                return;
            }
        }
    } 
    
    void resize(){        
        int cap=capacity;        
        capacity<<=1;
        vector<bucket *> tmp(capacity);        
        
        for (int i=0;i<cap;i++){
            if(!buckets[i]){
                continue;
            }            
            tmp[indexfor(hash(buckets[i]->key))]=buckets[i];            
        }
        
        buckets.clear();        
        buckets=tmp;
    }

    // 根据 hashcode 获取数组索引
    int indexfor(unsigned long long h){
        // 先扰动一下
        h^=h>>16;
        
        // 然后对容量取余
        return h&(capacity-1);
    }
    
    unsigned long long hash(int key) {
        return key%1000000007;
    }
    
    // bdkr algorithm
    unsigned long long hash(string key){
        // why? 比 127 大的最小质数
        unsigned long long salt=131;
        unsigned long long h=0;
        
        for (int i=0;i<key.size();i++){
            h=h*salt+key[i];
        }
        
        return h;
    }
};

    706. 设计哈希映射

    题意

    分析

    优化

    效率

    时间复杂度：

    空间复杂度：

    代码

    动态扩容+拉链法解决冲突

    struct bucket {
    int key;
    int value;
    bucket *next;
    
    //rbhead
    
    bucket() : key(0),value(0),next(nullptr) {};
    bucket(int k,int v,bucket *n) : key(k),value(v),next(n) {};
    bucket(int k,int v) : key(k),value(v),next(nullptr) {};
};

class MyHashMap {
    // 负载因子
    float loadFactor=0.65f;
    // 初始容量
    int capacity=1<<4;
    // 实际个数
    int size=0;
    // 存放数据的桶
    vector<bucket*> buckets;
    
public:
    MyHashMap() {
        buckets.resize(capacity);        
    }
    
    MyHashMap(int cap,float fac) {
        capacity=cap;
        loadFactor=fac;
        buckets.resize(cap);
    }
    
    void put(int key, int value) {        
        if(size>capacity*loadFactor){            
            resize();
            cout<<"new cap:"<<capacity<<endl;
        }
        
        int i=indexfor(hash(key));

        if(!buckets[i]){
            size++;
            buckets[i]=new bucket(key,value);
            size++;
            return;
        }
        
        if(buckets[i]->key==key){
            buckets[i]->value=value;
            return;
        }
       
        // cout<<"*"<<endl;
        
        bucket *b=buckets[i];
        while(b->next){
            if(b->next->key==key){
                b->next->value=value;
                return;
            }
            b=b->next;
        }
        
        size++;        
        b->next=new bucket(key,value);
    }
    
    int get(int key) {    
        bucket *b=buckets[indexfor(hash(key))];
        if(!b){
            return -1;
        }
    
        if(b->key==key){
            return b->value;
        }
        
        // cout<<"#"<<endl;        
      
        while(b){
            if (b->key==key){
                return b->value;
            }
            b=b->next;
        }
        return -1;
    }

    void remove(int key) {
        int i=indexfor(hash(key));
        if (!buckets[i]){
            return;
        }
        
        if(buckets[i]->key==key){
            buckets[i]=nullptr;
            size--;
            return;
        }
        
        // cout<<"*"<<endl;
        
        bucket *b=buckets[i];
        while(b->next){
            if(b->next->key==key){
                b->next=b->next->next;
                size--;
                return;
            }
        }
    } 
    
    void resize(){        
        int cap=capacity;        
        capacity<<=1;
        vector<bucket *> tmp(capacity);        
        
        for (int i=0;i<cap;i++){
            if(!buckets[i]){
                continue;
            }            
            tmp[indexfor(hash(buckets[i]->key))]=buckets[i];            
        }
        
        buckets.clear();        
        buckets=tmp;
    }

    // 根据 hashcode 获取数组索引
    int indexfor(unsigned long long h){
        // 先扰动一下
        h^=h>>16;
        
        // 然后对容量取余
        return h&(capacity-1);
    }
    
    unsigned long long hash(int key) {
        return key%1000000007;
    }
    
    // bdkr algorithm
    unsigned long long hash(string key){
        // why? 比 127 大的最小质数
        unsigned long long salt=131;
        unsigned long long h=0;
        
        for (int i=0;i<key.size();i++){
            h=h*salt+key[i];
        }
        
        return h;
    }
};

    380. O (1) 时间插入、删除和获取随机元素

    题意

    实现 RandomizedSet 类：

    RandomizedSet() 初始化 RandomizedSet 对象
    bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
    bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
    int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
    你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

    分析

    1. 插入、删除都要 O（1），一般自然的想法是用链表
    2. 随机返回任意一项，我们通常是直接返回一个数，如果是数组的话，那么可以返回索引，但是如果是链表，就做不到了，因为链表在内存中是随机分布的。
    3. 综上，链表是不行了，那只能考虑数组。但是一般数组我们都说增删是 ，为什么？因为后面所有元素都要调整位置。但是反过来说，如果不需要更改位置呢？即每次都在末尾增删，显然就满足了。
    4. 插入我们可以每次插入在末尾，但是删除呢？元素不一定在末尾呀，那怎么搞？简单，我们换到末尾去就行，反正数组有序与否根本不重要。
    5. 但现在又有一个问题，我们怎么知道我们要删除的元素现在在哪个索引呢？都不知道在哪，怎么交换呢？
    6. 我们现在只知道值，要求索引，显然自然的想法就是再引入一个哈希表存 值-索引 的映射了。

    综上所述：

    1. 用数组+哈希表存数据
    2. 插入时直接插入到数组末尾
    3. 删除时，先把删除元素和末尾元素互换，再删除末尾元素
    4. 返回随机数，则直接开随机数获取索引

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class RandomizedSet {
    vector<int> nums;
    // value-index
    unordered_map<int,int> m;
    
public:
    RandomizedSet() {

    }
    
    bool insert(int val) {
        // cout<<endl;
        if (m.count(val)!=0){
            // show("insert b "+to_string(val)+":");        
            // show("insert a "+to_string(val)+":");            
            return false;
        }
        // show("insert b "+to_string(val)+":");        
        m[val]=nums.size();
        nums.push_back(val);        
        // show("insert a "+to_string(val)+":");            
        return true;
    }
    
    bool remove(int val) {
        // cout<<endl;
        if (m.count(val)==0){
            // show("remove b "+to_string(val)+":");          
            // show("remove a "+to_string(val)+":");            
            return false;
        }
        
        // show("remove b "+to_string(val)+":");
        int i=m[val];
        
        m[nums[nums.size()-1]]=i;
        // show("remove b "+to_string(val)+":");
        
        swap(nums[nums.size()-1],nums[i]);
        // show("remove b "+to_string(val)+":");
        
        m.erase(nums[nums.size()-1]);
        // show("remove b "+to_string(val)+":");
        
        nums.erase(nums.end()-1);        
        // show("remove a "+to_string(val)+":");            
        return true;
    }
    
    int getRandom() {
        return nums[rand()%nums.size()];
    }
    
    void show(string str){
        cout<<str<<"      ";
        for (auto i:nums){
            cout<<i<<"-";
        }
        cout<<"       map:  ";
        for (auto i:m){
            cout<<"     "<<i.first<<":"<<i.second<<",";
        }
        cout<<endl;
    }
};

    381. O (1) 时间插入、删除和获取随机元素 - 允许重复

    题意

    设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。

    注意：允许出现重复元素。

    insert(val)：向集合中插入元素 val。
    remove(val)：当 val 存在时，从集合中移除一个 val。
    getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

    分析

    380 的进阶，分析和 380 相同，只是允许插入重复元素，380 的分析如下

    1. 插入、删除都要 O（1），一般自然的想法是用链表
    2. 随机返回任意一项，我们通常是直接返回一个数，如果是数组的话，那么可以返回索引，但是如果是链表，就做不到了，因为链表在内存中是随机分布的。
    3. 综上，链表是不行了，那只能考虑数组。但是一般数组我们都说增删是 ，为什么？因为后面所有元素都要调整位置。但是反过来说，如果不需要更改位置呢？即每次都在末尾增删，显然就满足了。
    4. 插入我们可以每次插入在末尾，但是删除呢？元素不一定在末尾呀，那怎么搞？简单，我们换到末尾去就行，反正数组有序与否根本不重要。
    5. 但现在又有一个问题，我们怎么知道我们要删除的元素现在在哪个索引呢？都不知道在哪，怎么交换呢？
    6. 我们现在只知道值，要求索引，显然自然的想法就是再引入一个哈希表存 值-索引 的映射了。

    综上所述：

    1. 用数组+哈希表存数据
    2. 插入时直接插入到数组末尾
    3. 删除时，先把删除元素和末尾元素互换，再删除末尾元素
    4. 返回随机数，则直接开随机数获取索引

    而本题由于允许重复，所以不再是简单的 val-index 的映射，而应该是 val 和 index 的集合进行映射，即 val 的所有索引，代码变动主要就是在这里，故增删时维护 map 要变化一下。

    优化

    效率

    时间复杂度：

    空间复杂度：

    代码

    class RandomizedCollection {
    vector<int> nums;
    unordered_map<int,unordered_set<int>> m;
    
public:
    RandomizedCollection() {

    }
    
    bool insert(int val) {
        // cout<<endl;
        // show("insert("+to_string(val)+")");
        m[val].insert(nums.size());
        nums.push_back(val);
        // show("insert("+to_string(val)+")");
        return m[val].size()==1;
    }
    
    bool remove(int val) {
        // cout<<endl;
        // show("remove("+to_string(val)+")");
            
        if (m.count(val)==0 || m[val].empty()){
            // show("remove("+to_string(val)+")");   
            return false;
        }
        
        if (nums.size()==1){
            nums.erase(nums.begin());
            m[val].erase(m[val].begin());
            return true;
        }
        
        if (nums[nums.size()-1]==val){
            m[val].erase(nums.size()-1);
            nums.erase(nums.end()-1);
            // show("remove("+to_string(val)+")");        
            return true;
        }
        
        auto i=m[val].begin();
        int iv=*i;
        
        m[nums[nums.size()-1]].erase(nums.size()-1);              
        m[nums[nums.size()-1]].insert(iv);
        m[val].erase(i);
        
        swap(nums[iv],nums[nums.size()-1]);    
        nums.erase(nums.end()-1);
        
        // show("remove("+to_string(val)+")");        
        return true;
    }
    
    int getRandom() {
        return nums[rand()%nums.size()];
    }
    
    void show(string str){
        cout<<str<<" ";
        for (int i=0;i<nums.size();i++){
            cout<<nums[i]<<"-";
        }        
        
        cout<<"       map:  ";
        for (auto ss:m){
            cout<<ss.first<<":(";
            auto tt=ss.second;
            
            for (auto b=tt.begin();b!=tt.end();b++){
                cout<<*b<<",";
            }
            cout<<")";
        }
        
        cout<<endl;
    }
};

    1396. 设计地铁系统

    题意

    设计一个地铁系统

    分析

    这道题的难点在于理解题意，然后设计一个合适的数据结构。

    最终要求的是 startStation 到 endStation 的时间+趟数，那么自然的，我们可以用哈希表来存，key 就是两个站点，value 就是对应的时间+趟数。

    问题来了，我们该怎么维护这个 map 呢？显然是入站和出站的时候进行维护。

    由于题意中说了：一个乘客在同一时间只能在一个地铁站进入或者离开。也就是说，某个时刻，从 startStation→endStation 的计算是由一个用户计算出来的。而用户 id 就是维护出站入站之间的关系。

    当我们要计算两个站之间的距离时，显然需要出战的时候才能计算。所以维护 map 需要在出站的时候。

    而出站的时候我们知道用户 id，站名和出站时间，显然我们需要对应的入站时间。而又说了某个时刻用户是唯一的，所以自然要找对应用户的入站时间。

    所以自然的，我们应该再引入一个哈希表，存用户 id → 站名+入站时间。

    入站的时候直接存到 map 中，出站的时候先取对应用户的入站名和入站时间，计算两站距离，存到第一个 map 里，然后趟数+1 即可。最后计算的时候，直接从 hash 表里取站距离+趟数计算即可。

    优化

    nil

    效率

    时间复杂度：

    空间复杂度：

    代码

    class UndergroundSystem {
public:
    // id -> <stationName,time>
    unordered_map<int,pair<string,int>> m1;
    // <startStation,endStation>-><id,trip>
    unordered_map<string,pair<int,int>> m2;
    
    UndergroundSystem() {

    }
    
    void checkIn(int id, string stationName, int t) {
        m1[id]={stationName,t};        
    }
    
    void checkOut(int id, string stationName, int t) {
        auto i=m1[id];
        auto j=m2[i.first+","+stationName];
        m2[i.first+","+stationName]={j.first+t-i.second,j.second+1};
    }
    
    double getAverageTime(string startStation, string endStation) {
        auto i=m2[startStation+","+endStation];
        return (double)i.first/i.second;
    }
};

    1656. 设计有序流

    题意

    开一个大小为 n 的集合，每次往里面插入数据，同时维护一个 ptr 指针，这个指针是每次集合最前面为空的地方。如果插入的位置就是 ptr 处，则输出后面连续有数据的数据。

    分析

    1. 这题的难点在于理解题意，搞懂之后就是简单的模拟了
    2. 第二步是选择合适的数据结构，这题由于 ikKey 在 1~1000 间，且不重复，故自然的是使用一个数组即可。
    3. 选择好数据结构后，就是把题意模拟翻译即可。

    优化

    五

    效率

    时间复杂度：

    空间复杂度：

    代码

    class OrderedStream {
public:
    vector<string> nums;
    int ptr;
    
    OrderedStream(int n) {
        nums=vector<string>(n+1,"");
        ptr=1;
    }
    
    vector<string> insert(int idKey, string value) {
        vector<string> res;        
        nums[idKey]=value;
        if(ptr!=idKey){
            return {};
        }
    
        while(ptr<nums.size()&&nums[ptr]!=""){
            res.push_back(nums[ptr]);
            ptr++;                
        }        
        
        return res;
    }
};

    1797. 设计一个验证系统

    题意

    设计验证系统

    分析

    这题主要是题目的理解：

    1. 最基本的数据是 <tokenId,time> ，是个 string-int 的数据类型
    2. renew，generate 都操作都是直接拿到 tokenId 对应的 time，然后判断和当前 time 的大小进行判处理的
    3. 所以自然的，就使用哈希表来存这个键值对，value 存过期时间或生成时间都行
    4. 然后就是模拟对应的操作，展开即可

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class AuthenticationManager {
public:
    int t;
    unordered_map<string,int> m;

    AuthenticationManager(int timeToLive) {
        t=timeToLive;
    }
    
    void generate(string tokenId, int currentTime){              
        m[tokenId]=currentTime+t;
    }
    
    void renew(string tokenId, int currentTime) {
        if (!m.count(tokenId)) {
            return;
        }
        if (m[tokenId]>currentTime) {
            m[tokenId]=currentTime+t;
        }
    }
    
    int countUnexpiredTokens(int currentTime) {
        int cnt=0;
        
        for (auto i:m) {
            if (i.second>(currentTime)) {
                cnt++;
            }
        }
        return cnt;        
    }
};

    1912. 设计电影租借系统

存在性问题

存在性问题是指，对于 x，求满足条件的 y 是否存在，这种题通常可以使用哈希表来存，常见于前缀和的题目，或者 n 数和这种高频题。

  • list

    面试题 01.01. 判定字符是否唯一

    题意

    实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

    分析

    自然的想法需要统计频率，不过实际上只需判断是否存在，故用 set 就行，但题目又不用其它数据结构，自然只能直接用数组或其它的了。

    1. 用数组，扫描一遍计数，再扫一遍判断
    2. 给定的范围已定，故直接用个 int 模拟哈希表

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool isUnique(string astr) {
        int d=0;
        for (auto s:astr){
            if (getBit(d,s-'a')) {
                return false;
            }
            d=setBit(d,s-'a');
        }
        return true;
    }
    
    int getBit(int x,int pos){
        return (x>>pos)&1;
    }
    
    int setBit(int x,int pos){
        return x|(1<<pos);
    }
};

    771. 宝石与石头

    题意

    判断不同字符种类个数

    分析

    1. 扫描一遍将字符种类放到 set 中
    2. 再扫一遍判断

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_map<int,int> m;
        int res=0;
        
        for (auto i:jewels){
            m[i]++;
        }
        
        for (auto i:stones){
            if(m.count(i)!=0){
                res++;
            }
        }
        
        return res;
    }
};
    class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        unordered_set<int> m;
        int res=0;
        
        for (auto i:jewels){
            m.insert(i);
        }
        
        for (auto i:stones){
            if(m.count(i)!=0){
                res++;
            }
        }
        
        return res;
    }
};

    202. 快乐数

    题意

    判断数是不是快乐数

    分析

    这题就是经过一些计算，然后在一些数间进行转移，判断有没有环。

    最简单的就是开个 set 存已经访问过的数，如果再次出现，自然就有环。也可以使用快慢指针，类似于判断链表环，最后判断是否相遇即可。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：集合 、快慢指针

    代码

    class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> s;
        
        while(n!=1){
            s.insert(n);
            n=get(n);
            if(s.find(n)!=s.end()){
                return false;
            }
        }
        
        return true;
    }
    
    int get(int n){
        int res=0;
        
        while(n){            
            res+=(n%10)*(n%10);
            n/=10;
        }
        
        return res;
    }
};
    class Solution {
public:
    bool isHappy(int n) {
        int slow=n;
        int fast=n;
        
        while(slow!=1){
            slow=get(slow);
            fast=get(fast);
            fast=get(fast);
            if(slow!=1&&slow==fast){
                return false;
            }
        }
                
        return true;
    }
    
    int get(int n){
        int res=0;
        
        while(n){            
            res+=(n%10)*(n%10);
            n/=10;
        }
        
        return res;
    }
};

    1346. 检查整数及其两倍数是否存在

    题意

    判断数组里是否有两数使得 n=m*2

    分析

    遍历一遍，把前面的数放到哈希表里面，然后对当前的元素进行判断，当前的元素 *2 或

    /2 的元素如果在哈希表里，则就存在。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> s;
        
        for (auto i:arr){            
            if (s.find(i*2)!=s.end()){
                return true;
            }
            if (i%2==0&&s.find(i/2)!=s.end()){
                return true;
            }
            s.insert(i);            
        }
        
        return false;
    }   
};

    1624. 两个相同字符之间的最长子字符串

    题意

    给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 *，*计算长度时不含这两个字符。如果不存在这样的子字符串，返回 1 。

    分析

    1. 开哈希表存字符 key 第一次出现的索引
    2. 扫描数组，然后把前面的字符索引放到哈希表中
    3. 对当前字符进行判断，获取当前字符出现的首索引，然后更新结果

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        // value 为 key 第一次出现的索引
        unordered_map<char,int> m;
        int res=-1;
        
        for (int i=0;i<s.size();i++){
            if (m.count(s[i])==0){
                m[s[i]]=i;
                continue;
            }
            
            res=max(res,i-m[s[i]]);
        }
        
        return res==-1?-1:res-1;
    }
};

    819. 最常见的单词

    题意

    获取白名单中出现次数最多的字符串

    分析

    1. 分割句子获取单词序列（这个有点麻烦）
    2. 到黑名单中过滤一遍
    3. 再统计出现次数

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    string mostCommonWord(string p, vector<string>& b) {
        unordered_set<char> mark = {'!', '?', '\'', ',', ';', '.'};
        for(int i=0;i<p.size();i++){
            if(mark.count(p[i])){
                p[i]=' ';
            }else{
                p[i]=tolower(p[i]);
            }
        }

        unordered_set<string> limit;
        for (auto i:b){
            limit.insert(i);
        }        
        
        unordered_map<string,int> cnt;
        string res;
        int m=0;
        istringstream sin(p);
        string word;
        while(sin>>word){
            if (limit.find(word)!=limit.end()){
                continue;
            }
            
            cnt[word]++;                
        }
        
        for (auto i:cnt){
            if(i.second>m){
                m=i.second;
                res=i.first;
            }
        }
        
        return res;
    }    
};

    36. 有效的数独

    题意

    检测是否是数独

    分析

    翻译题意，就是判断每行，每列，每个小宫格是不是都没有重复元素。而判断重复元素，使用 set 即可。

    故直接模拟即可，遍历每行，每列，每个小宫格，行和列比较容易，小宫格的麻烦之处在于生成对应的坐标。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& nums) {
        unordered_set<int> s;
        
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){                
                if (nums[i][j]=='.'){
                    continue;
                }
                
                // cout<<nums[i][j]<<" ";
                if (s.find(nums[i][j])!=s.end()){
                    return false;
                }
                s.insert(nums[i][j]);
            }
            // cout<<endl;
            s.clear();
        }
        
        for (int j=0;j<9;j++){
            for (int i=0;i<9;i++){                
                if (nums[i][j]=='.'){
                    continue;
                }
                
                // cout<<nums[i][j]<<" ";
                if (s.find(nums[i][j])!=s.end()){
                    return false;
                }
                s.insert(nums[i][j]);
            }
            // cout<<endl;
            s.clear();
        }
        

        for (int i=0;i<9;i++){            
            for (int j=0;j<9;j++){
                int t1 = 3 * (i / 3) + j / 3;
                int t2 = 3 * (i % 3) + j % 3;

                if (nums[t1][t2]=='.'){
                    continue;
                }
                
                // cout<<"("<<t1<<","<<t2<<")"<<" ";
                // cout<<nums[t1][t2]<<endl;
                
                if (s.find(nums[t1][t2])!=s.end()){
                    return false;
                }
                s.insert(nums[t1][t2]);                                
            }
            // cout<<endl;
            s.clear();
        }
                
        return true;  
    }    
};

查重

判断元素是否重复

  • list

    804. 唯一摩尔斯密码词

    题意

    找到唯一的字符串

    分析

    1. 先把对应的字符串生成出来
    2. 再放到 set 里过一道判断即可

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        vector<string> n={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

        unordered_set<string> s;
        string str;
        int res=0;
        
        for (auto w:words){
            str.clear();
            for (auto i:w){
                str+=n[i-'a'];
            }
            if (s.find(str)!=s.end()){
                res++;
            }
            s.insert(str);
        }
        
        return words.size()-res;
    }
};

    1805. 字符串中不同整数的数目

    题意

    获取字符串中的数字，然后判个数

    分析

    1. 获取字符串中的数字
    2. 放到 set 里即可

    问题就在于字母获取字符串中的数字，这是典型的快慢指针的问题，也是个模拟题，不过需要注意一些细节（我 wa 了 5 次）

    基本的思想，就是：

    1. 快指针找到数字起点
    2. 设置左边界
    3. 快指针继续找数字右边界
    4. 去除左边界的 0

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int numDifferentIntegers(string word) {
        unordered_set<string> s;
        
        int l=0;
        int r=0;
        
        while(l<word.size()&&!isDight(word[l])){
            l++;
        }
        r=l;
        
        while(r<word.size()){
            while (r<word.size()&&!isDight(word[r])){
                r++;
            }
            l=r;
            
            while(r<word.size()&&isDight(word[r])){
                r++;
            }
            while(l<r&&word[l]=='0'&& l+1<r && isDight(word[l+1])){
                l++;
            }
            if (word.substr(l,r-l)!=""){
                s.insert(word.substr(l,r-l));                
            }
        }
                
        return s.size();
    }
    
    bool isDight(char c) {
        return c>='0'&&c<='9';
    }
};

    884. 两句话中的不常见单词

    题意

    找出出现一次的单词

    分析

    1. 将两字符串合并
    2. 获取所有单词，并放到哈希表中
    3. 遍历统计出现一次的单词

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<string> uncommonFromSentences(string s1, string s2) {
        string s=s1+" "+s2;
        unordered_map<string,int> m;
        int l=0;
        int r=0;
        vector<string> res;
        
        while(r<s.size()){
            if (s[r]!=' '){
                r++;
                continue;
            }
            m[s.substr(l,r-l)]++;;
            r++;
            l=r;            
        }
        m[s.substr(l,r-l)]++;;
        
        for (auto i:m){
            if(i.second==1){
                res.push_back(i.first);
            }
        }
        
        return res;
    }
};

    859. 亲密字符串

    题意

    判断 s1 是否交换一次可以得到 s2

    分析

    1. 如果长度不等，不可能
    2. 如果相等，且 s1 有重复元素，则可以，否则不行
    3. 找到两不等的字符，交换后判断

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool buddyStrings(string s1, string s2) {
        if (s1.size()!=s2.size()){
            return false;
        }
        if(s1==s2){
            unordered_set<char> s;
            for (auto i:s1){
                if (s.count(i)){
                    return true;
                }
                s.insert(i);
            }
            return false;
        }
                
        int l=-1;
        
        for (int i=0;i<s1.size();i++){
            if (s1[i]!=s2[i]) {                
                if (l==-1){
                    l=i;
                } else {
                    swap(s1[l],s1[i]);
                    return s1==s2;                    
                }
            }
        }
        
        return l==-1;
    }
};

去重

去除重复元素，比如问字符的种类

  • list

    929. 独特的电子邮件地址

    题意

    将邮件处理后，获取种类个数

    分析

    遍历邮件，然后模拟即可，用一个 set 来去重存结果。

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {
        unordered_set<string> s;
        string t;
        bool flag=false;
        int l=0;
        
        for (auto e:emails){
            t.clear();
            flag=false;
            l=0;
            
            for (int i=0;i<e.size();i++){
                if (!flag&&e[i]=='.'){
                    continue;
                }
                
                if (e[i]=='@'){
                    t+=e.substr(i,e.size()-i+1);
                    break;
                }                
                if (!flag&&e[i]!='+') {
                    t+=e.substr(i,1);
                    l=i; 
                    continue;
                }
                if (!flag && e[i]=='+'){
                    t+=e.substr(l+1,i-l-1);
                    flag = true;
                    continue;
                }
            }
            s.insert(t);
        }
        
        return s.size();
    }
};

分组、分桶

将元素分到特定的桶里面去

  • list

    49. 字母异位词分组

    题意

    给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

    字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

    分析

    根据题目，我们发现这是个典型的分组问题，而对于分组问题，我们通常开一些桶，扫描一遍，然后把它们映射到对于的桶中。

    桶这里开 string 数组，映射开哈希表，但是问题是，映射函数是什么？

    再看题目，要求的是字母异位词，什么是异位词？字母频率相同。那我们怎么用呢？再开个哈希表统计频率？没必要，因为频率相同也意味着排序后相同，所以我们可以把排序后的结果作为 key。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> m;
        vector<vector<string>> res;
        string ss;
        
        for (auto s:strs){
            ss=s;
            sort(s.begin(),s.end());
            m[s].push_back(ss);
        }
        
        for (auto i=m.begin();i!=m.end();i++){
            res.push_back(i->second);
        }
        
        return res;
    }
};

计数**、频率**

对于设计两个东西频率相关的，通常可以扫描一遍，一次增加，一次减少

  • list

    剑指 Offer 50. 第一个只出现一次的字符

    题意

    在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

    分析

    找到第一次只出现一次的字符，典型的个数统计问题，开个哈希表扫描两边即可，第一遍统计个数，第二遍找符合条件的。

    优化

    由于只含有小写字母，故可开个 26 大小的数组模拟

    效率

    时间复杂度：

    空间复杂度：

    代码

    哈希表

    class Solution {
public:
    char firstUniqChar(string s) {
        unordered_map<char,int> m;
        
        for (int i=0;i<s.size();i++){
            m[s[i]]++;
        }
        
        for (int i=0;i<s.size();i++){
            if (m[s[i]]==1){
                return s[i];
            }
        }
        
        return ' ';
    }
};

    数组模拟

    class Solution {
public:
    char firstUniqChar(string s) {
        vector<int> nums(27);
        
        for (int i=0;i<s.size();i++){
            nums[s[i]-'a']++;
        }
        
        for (int i=0;i<s.size();i++){
            if (nums[s[i]-'a']==1){
                return s[i];
            }
        }
        
        return ' ';
    }
};

    242. 有效的字母异位词

    题意

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

    分析

    开 hash 表，扫描一遍统计频率，再扫描一遍比较即可。

    优化

    由于只含有小写字母，故可开数组模拟。

    同时，第二遍扫描时，可以抵消之前的频次，最后判断是否为 0 即可。

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()){
            return false;
        }
        
        unordered_map<char,int> sMap;

        for (int i=0;i<s.size();i++){
            sMap[s[i]]++;
        }

        for (int i = 0;i<t.size();i++){
            if (sMap.count(t[i]) == 0) {
                return false;
            }
            if (sMap[t[i]] <= 0) {
                return false;
            }
            sMap[t[i]]--;
        }

        return true;
    }
};
    class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s==t){
            return false;
        }
        
        vector<int> nums(26);
        vector<int> numt(26);
        
        for (int i=0;i<s.size();i++){
            nums[s[i]-'a']++;
        }
        for (int i=0;i<t.size();i++){
            numt[t[i]-'a']++;
        }
        
        for(int i=0;i<26;i++){
            if(nums[i]!=numt[i]){
                return false;
            }
        }
        
        return true;
    }  
};
    class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s==t){
            return false;
        }
        
        vector<int> nums(26);
        
        for (int i=0;i<s.size();i++){
            nums[s[i]-'a']++;
        }
        for (int i=0;i<t.size();i++){
            nums[t[i]-'a']--;
        }
        
        for(int i=0;i<26;i++){
            if(nums[i]!=0){
                return false;
            }
        }
        
        return true;
    }  
};

    347. 前 K 个高频元素

    题意

    给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

    分析

    1. 开哈希表统计数字频率
    2. 频率数字作为一个整体，全部放到大顶堆中
    3. 获取大顶堆上面 k 个元素

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    struct cmp{
    bool operator() (pair<int,int> a,pair<int,int> b){
        return a.second<b.second;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        using e=pair<int,int>;
        priority_queue<e,vector<e>,cmp> q;
        vector<int> res;
        
        for (int i=0;i<nums.size();i++){
            m[nums[i]]++;
        }
        
        for (auto j:m){
            // cout<<j.first<<" "<<j.second<<endl;
            q.push(make_pair(j.first,j.second));
        }
        
        while(k--){
            // cout<<q.top().first<<" "<<q.top().second<<endl;            
            res.push_back(q.top().first);
            q.pop();
        }
        
        return res;
    }
};

    面试题 16.15. 珠玑妙算

    题意

    如果 s[i]==g[i] 则，a++，如果 g[i] 在 s 中，则 b++（要消除相等和比较过的）

    分析

    简单的模拟题

    1. 遍历，找到 s[i]==g[i] 的，并删除
    2. 统计 s 中的字符频率
    3. 遍历 g，消除 s 中的字符，存在着则 b++

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> masterMind(string s, string g) {
        int a=0;
        int b=0;
        
        for (int i=0;i<s.size();){
            if(s[i]==g[i]){
                a++;
                s.erase(s.begin()+i);
                g.erase(g.begin()+i);
            } else {
                i++;
            }            
        }
        
        unordered_map<char,int> ss;
        
        for (int i=0;i<s.size();i++){
            ss[s[i]]++;
        }
        for (int i=0;i<g.size();i++){
            if(ss[g[i]]>0){
                b++;
                ss[g[i]]--;
            }
        }

        return {a,b};
    }
};

    面试题 01.02. 判定是否互为字符重排

    题意

    判断是否是异位词

    分析

    异位词即字符频率相同，或者排序后相等，故可以排序，也可以用哈希表统计频率

    排序

    class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        return s1==s2;        
    }
};

    时间复杂度：，空间复杂度：

    哈希表

    1. 遍历 s1，频率++
    2. 遍历 s2，频率—
    3. 判断
    class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        vector<int> m(127);
        
        for (auto i:s1){
            m[i]++;
        }
        for (auto i:s2){
            m[i]--;
        }
        for (auto i:m){
            if (i!=0){
                return false;
            }                
        }
        
        return true;
    }
};

    时间复杂度：，空间复杂度：

    1512. 好数对的数目

    题意

    统计相同数的个数

    分析

    1. 先统计相同数的个数
    2. 然后就是个数组问题了

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        vector<int> cnt(101);
        int res=0;
        
        for (auto i:nums){        
            cnt[i]++;
        }
        
        for (int i=0;i<cnt.size();i++){
            res+=((cnt[i]*(cnt[i]-1))/2);
        }
        
        return res;
    }
};

    2085. 统计出现过一次的公共字符串

    题意

    给你两个字符串数组 words1 和 words2 ，请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。

    分析

    1. 开哈希表，扫描一遍统计频率
    2. 扫一遍 2，频率抵消
    3. 最后扫描哈希表看结果

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int countWords(vector<string>& words1, vector<string>& words2) {
        int res=0;
        unordered_map<string,int> m;
        
        for (auto i:words1){
            m[i]++;
        }
        
        for (auto i:words2){
            if(m[i]==1||m[i]==0){
                m[i]--;
            }
        }
        
        for (auto i:m){
            if(i.second==0){
                res++;
            }
        }
        
        return res;
    }
};

    1941. 检查是否所有字符出现次数相同

    题意

    给你一个字符串 s ，如果 s 是一个 好 字符串，请你返回 true ，否则请返回 false 。

    如果 s 中出现过的 所有 字符的出现次数 相同 ，那么我们称字符串 s 是 好 字符串。

    分析

    1. 扫描一遍计数
    2. 再扫一遍判断

    优化

    null

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool areOccurrencesEqual(string s) {
        vector<int> m(26);
        int cnt=0;
        
        for (auto i:s){
            m[i-'a']++;
        }
        
        for (int i=0;i<26;i++){
            if(cnt==0&&m[i]!=0){
                cnt=m[i];
            }
            
            if(m[i]!=0&&m[i]!=cnt){
                return false;
            }
        }
        
        return true;
    }
};

    2068. 检查两个字符串是否几乎相等

    题意

    检查两字符串的字符频率差

    分析

    1. 开一个数组记录字符频率
    2. 扫一遍字符串，一个计数增加，一个抵消
    3. 再扫一遍频率数组判断

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool checkAlmostEquivalent(string word1, string word2) {
        vector<int> nums(26);
        
        for (int i=0;i<word1.size();i++){
            nums[word1[i]-'a']++;
            nums[word2[i]-'a']--;
        }
        
        for (auto i:nums){
            if (i>3||i<-3){
                return false;
            }
        }
        
        return true;
    }
};

    1897. 重新分配字符使所有字符串都相等

    题意

    判断所有字符数量是否能被长度整除

    分析

    1. 开一个频次数组
    2. 扫描所有单词计数
    3. 遍历频次数组，判断是否能被长度整除

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool makeEqual(vector<string>& words) {
        vector<int> nums(26);
                
        for (auto w:words){
            for (auto i:w){
                nums[i-'a']++;
            }
        }
        
        for (int i=0;i<nums.size();i++){
            if (nums[i]%words.size()!=0){
                return false;
            }
        }
        
        return true;
    }
};

    1002. 查找共用字符

    题意

    找出几个集合的交集（集合可重复）

    分析

    1. 对每个字符串映射到一个字符频次数组上
    2. 所有字符频次最小值就是交集
    3. 遍历频次数组造结果数组

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<vector<int>> m;
        vector<int> t(26);
        vector<string> res;
        
        for (int i=0;i<words.size();i++){
            m.push_back(vector<int>(26));
            
            for (auto s:words[i]){
                m[i][s-'a']++;
            }            
        }

        for (int i=0;i<26;i++){
            t[i]=m[0][i];
            for (int j=0;j<m.size();j++){
                t[i]=min(t[i],m[j][i]);
            }
        }
        
        for (int i=0;i<26;i++){
            while(t[i]--){
                string s(1,'a'+i);
                res.push_back(s);
            }
        }
                
        return res;
    }
};

    383. 赎金信

    题意

    判断集合 a 是否是 b 的子集

    分析

    题目就是判断集合 a 是否是 b 的子集，如果集合没有重复元素的话，直接用 int+位运算就行，但是这题有重复元素，故需要开个频次数组，扫描两次，一次统计，一次抵消，最后看是否还有大于 0 的元素，即没有抵消掉的。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool canConstruct(string a, string b) {
        vector<int> n(26);
        
        for (auto i:a){
            n[i-'a']++;
        }
        for (auto i:b){
            n[i-'a']--;
        }
        
        for (auto i:n){
            if(i>0){
                return false;
            }
        }
        return true;
    }
};

    451. 根据字符出现频率排序

    题意

    给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

    分析

    单纯的模拟题

    1. 开一个频次数组记录频次
    2. 频次和字符组成 pair 放到大顶堆中
    3. pop 大顶堆构造结果

    优化

    null

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    string frequencySort(string s) {
        vector<int> cnt(128);
        string res;
        
        for (auto i:s){
            cnt[i]++;
        }
        
        using ty=pair<int,char>;
        priority_queue<ty,vector<ty>,less<ty>> t;
        
        for (int i=0;i<128;i++){
            t.push(make_pair(cnt[i],i));
        }

        while (!t.empty()){
            int i=t.top().first;
            while(i--){
                res+=t.top().second;
            }
            
            t.pop();
        }
        
        return res;
    }
};

    387. 字符串中的第一个唯一字符

    题意

    给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

    分析

    1. 开一个计数哈希
    2. 遍历字符串计数
    3. 再遍历字符串判断字符是否频次为 1

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> m;
        
        for (auto i:s){
            m[i]++;
        }
        
        for (int i=0;i<s.size();i++){
            if(m[s[i]]==1){
                return i;
            }
        }
        
        return -1;
    }
};
    class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> cnt(26);
        // unordered_map<char,int> m;
        
        for (auto i:s){
            // m[i]++;
            cnt[i-'a']++;
        }
        
        for (int i=0;i<s.size();i++){
            if(cnt[s[i]-'a']==1){
                return i;
            }
        }
        
        return -1;
    }
};

    1460. 通过翻转子数组使两个数组相等

    题意

    判断是否是异位词

    分析

    可以直接排序再比较，也可以开频次数组，扫描三次，一次增加，一次减少，一次判断即可。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        vector<int> cnt(1001);

        for (auto i:target){
            cnt[i]++;
        }
        for (auto i:arr){
            cnt[i]--;
        }
        for (auto i:cnt){
            if(i){
                return false;
            }
        }
        return true;
    }
};
    class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        sort(target.begin(),target.end());
        sort(arr.begin(),arr.end());
        
        for (int i=0;i<arr.size();i++){
            if(target[i]!=arr[i]){
                return false;
            }
        }
        
        return true;
    }
};

    1394. 找出数组中的幸运数

    题意

    找出 max(cnt[num]=num) 的 num

    分析

    1. 开频次数组，扫描统计频次
    2. 判断，获取最大值

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int findLucky(vector<int>& arr) {
        vector<int> cnt(501);
        int res=-1;
        
        for (auto i:arr){
            cnt[i]++;
        }
        
        for (int i=1;i<501;i++){
            if(i==cnt[i]){
                res=max(res,i);
            }
        }
        
        return res;
    }
};

    1365. 有多少小于当前数字的数字

    题意

    给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

    分析

    1. 开频次数组统计，使得 cnt[i] 表示 i 的频次
    2. 对频次数组求前缀和，使得 presum[i] 表示小于 i 的个数
    3. 构造结果数组

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> cnt(501);        
        vector<int> presum(502);        
        vector<int> res;
        int t;
        
        for (auto i:nums){
            cnt[i]++;
        }
        
        for (int i=1;i<501;i++){
            presum[i]=presum[i-1]+cnt[i-1];
        }
        
        for (int i=0;i<nums.size();i++){
            res.push_back(presum[nums[i]]);
        } 
            
        return res;
    }
};

    1207. 独一无二的出现次数

    题意

    给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

    如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

    分析

    1. 开个频次数组，遍历统计频次
    2. 开个 set 判重

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        vector<int> cnt(2002);
        for (auto i:arr){
            cnt[i+1000]++;
        }
        unordered_set<int> s;
        for (auto c:cnt){
            if(c==0){
                continue;
            }
            if (s.find(c)!=s.end()){
                return false;
            }
            s.insert(c);
        }
        return true;
    }
};

    1189. “气球” 的最大数量

    题意

    统计字符串包含 balloon 的次数

    分析

    1. 开频次数组，遍历统计频次
    2. 获取频次最小值

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int maxNumberOfBalloons(string text) {
        vector<int> cnt(5);
        int index;
        int res;
        
        for (auto i:text){            
            index=getIndex(i);
            if(index!=-1){
                cnt[index]++;
            }
        }
        
        if (cnt[2]%2!=0){
            cnt[2]--;
        }
        cnt[2]/=2;
        if (cnt[3]%2!=0){
            cnt[3]--;
        }
        cnt[3]/=2;
        
        res=cnt[0];
        for (auto i:cnt){
            if(i==0){
                return 0;
            }
            res=min(res,i);
        }
        
        return res;
    }
    
    int getIndex(char c){
        if (c=='b'){
            return 0;
        }
        if(c=='a'){
            return 1;
        }
        if(c=='l'){
            return 2;
        }
        if(c=='o'){
            return 3;
        }
        if(c=='n'){
            return 4;
        }
        return -1;
    }
};

    1832. 判断句子是否为全字母句

    题意

    判断字符串是否包含所有小写字母

    分析

    1. 开一个频次数组，遍历统计频次
    2. 遍历频次数组，判断是否所有频次都大于 0

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool checkIfPangram(string sentence) {
        vector<int> cnt(26);
        
        for (auto i:sentence){
            cnt[i-'a']++;
        }
        
        for (auto c:cnt){
            if (c==0){
                return false;
            }
        }
        
        return true;
    }
};

    1796. 字符串中第二大的数字

    题意

    给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 1 。

    分析

    1. 使用计数数组筛选出数字
    2. 从高位开始遍历计数数组，然后找出第二大的即可

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int secondHighest(string s) {
        vector<int> cnt(10);
        bool m=false;
        
        for (auto i:s){
            if (i>='0'&&i<='9'){
                cnt[i-'0']++;
            }
        }
        
        for (int i=9;i>=0;i--){
            if (!cnt[i]){
                continue;
            }
            if (!m){
                m=true;
                continue;
            }
            return i;
        }
        
        return -1;
    }
};

    1636. 按照频率将数组升序排序

    题意

    给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。

    分析

    1. 开频次哈希，遍历统计频次
    2. 遍历数字，将数字和对应的频次放到有限队列中（重写比较器、优先级）
    3. 把优先队列打到结果数组中

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    struct cmp{
    bool operator() (pair<int,int> a,pair<int,int> b){
        if (a.second!=b.second) {
            return a.second>b.second;
        }
        return a.first<b.first;
    }
};

class Solution {        
public:
    vector<int> frequencySort(vector<int>& nums) {
        // value-freq
        using t=pair<int,int>;
        priority_queue<t,vector<t>,cmp> n;
        unordered_map<int,int> cnt;
        vector<int> res;
        
        for (auto i:nums) {
            cnt[i]++;
        }
                
        for (int i=-100;i<101;i++){
            if (cnt[i]){
                n.push(make_pair(i,cnt[i]));                
            }
        }
        
        while(!n.empty()){
            int c=n.top().second;
            while(c--){
                res.push_back(n.top().first);                
            }
            n.pop();
        }
        
        return res;
    }
};

    1748. 唯一元素的和

    题意

    求所有只出现一次元素的和

    分析

    1. 开频次数组，遍历原数组，求出频次数组
    2. 遍历频次数组，将频次为 1 的元素求和

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        vector<int> cnt(101);
        int res=0;
        
        for (auto i:nums){
            cnt[i]++;
        }
        
        for (int i=0;i<cnt.size();i++){            
            if (cnt[i]==1){
                res+=i;
            }
        }
        
        return res;
    }
};

    961. 在长度 2N 的数组中找出重复 N 次的元素

    题意

    找出并返回重复了 n **次的那个元素。

    分析

    1. 开频次数组，遍历统计出频次数组
    2. 遍历统计数组，找出对应频次的元素

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {
        vector<int> cnt(10001);
        
        for (auto i:nums){
            cnt[i]++;
        }
        
        for (int i=0;i<10001;i++){
            if (cnt[i]==nums.size()/2){
                return i;
            }
        }
        
        return -1;
    }
};

    1790. 仅执行一次字符串交换能否使两个字符串相等

    题意

    判断两字符串是否只交换一个字符就相等

    分析

    1. 如果已经相等了，返回
    2. 如果要只交换一次就相等，则对应位置字符不等的情况必然为 2
    3. 判断不等的两字符只是相等

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        if (s1==s2){
            return true;
        }
        int a=-1;
        int b=-1;
        
        for (int i=0;i<s1.size();i++){
            if (s1[i]==s2[i]){
                continue;
            }
            if (a==-1){
                a=i;
                continue;
            }
            if (b==-1) {
                b=i;
                continue;
            }
            return false;
        }
                   
        return a!=-1&&b!=-1&&s1[a]==s2[b]&&s1[b]==s2[a];
    }
};

    2094. 找出 3 位偶数

    题意

    找出所有的 3 位偶数

    分析

    由于 3 位偶数比较少，因此我们可以通过枚举这些偶数，然后看是否原数组能够组成。而判断是否能组成，就是统计位数的个数，然后判断。

    故，我们先用个东西统计原数组数字个数，然后枚举偶数判断即可。由于是 0~9 的数，故直接开个数组统计即可。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        vector<int> nums(10);
        vector<int> t(10);
        vector<int> res;
        
        for (auto d:digits){
            nums[d]++;
        }
        
        for (int i=100;i<1000;i++){
            t=nums;
                        
            if(nums[i%10]<1 || (i%10 % 2) !=0){
                continue;
            }
            nums[i%10]--;
            
            if(nums[i/10%10]<1){
                nums=t;
                continue;
            }
            nums[i/10%10]--;
            
            if(nums[i/100%10]<1){
                nums=t;
                continue;
            }
            
            res.push_back(i);
            nums=t;
            
        }
        
        return res;
    }
};

映射

映射题是指一个字符串经过一些映射变到另一个字符串的题型。

  • list

    953. 验证外星语词典

    题意

    根据新的字母表排序

    分析

    1. 建立新字母表和原小写字母表的映射
    2. 将 words 替换成旧小写字母表的映射
    3. 变成 words 判断相邻大小

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool isAlienSorted(vector<string>& words, string order) {
        unordered_map<char,char> m;
        
        for (int i=0;i<order.size();i++){
            // cout << (char)('a'+i) <<" " << order[i] <<endl;
            m[order[i]]='a'+i;
        }
        
        for (int i=0;i<words.size();i++){
            for (int j =0;j<words[i].size();j++){
                words[i][j]=m[words[i][j]];
            }
        }
        
        for (int i=0;i<words.size()-1;i++){
            if (words[i]>words[i+1]){
                return false;
            }
        }
        
        return true;
    }
};

    205. 同构字符串

    题意

    两字符串进行双射，当不同时可映射到不同字符，但一个字符只能映射一次。

    分析

    1. 开两个哈希表存两个方向的映射
    2. 如果遍历的过程中，这个字符已经映射过，且不同，那么就映射失败

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char,char> m1;
        unordered_map<char,char> m2;
        
        for (int i=0;i<s.size();i++){
            if (m1.count(s[i])!=0&&m1[s[i]]!=t[i]){
                return false;
            }
            if (m2.count(t[i])!=0&&m2[t[i]]!=s[i]){
                return false;
            }
            m1[s[i]]=t[i];
            m2[t[i]]=s[i];
        }
        
        return true;
    }
};

    290. 单词规律

    题意

    205 的深入，一个字符串变成了取其中的子串进行映射

    分析

    相对于 205，增加了分解 s 字符串的过程，其它都是一样的。

    开两个哈希表存两个方向的映射，如果遍历的过程中，这个字符已经映射过，且不同，那么就映射失败。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    bool wordPattern(string pattern, string s) {        
        vector<string> str;
        
        int l=0;
        int r=0;
        
        while(r<s.size()){
            if (s[r]==' '){
                if (s[l]==' '){
                    str.push_back(s.substr(l+1,r-l-1));
                } else {
                    str.push_back(s.substr(l,r-l));
                }
                l=r;
            }
            r++;
        }
        if (s[l]==' '){
            str.push_back(s.substr(l+1,r-l-1));
        } else {
            str.push_back(s.substr(l,r-l));
        }
        
        if (str.size()!=pattern.size()){
            return false;
        }
                
        unordered_map<char,string> m1;
        unordered_map<string,char> m2;

        for (int i=0;i<str.size();i++){
            
            if (m2.count(str[i])!=0 && m2[str[i]]!=pattern[i]){
                return false;
            }
            if (m1.count(pattern[i])!=0 && m1[pattern[i]]!=str[i]){
                return false;
            }
            
            m2[str[i]]=pattern[i];
            m1[pattern[i]]=str[i];            
        }        
    
        return true;
    }
};

    17. 电话号码的字母组合

    题意

    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

    分析

    1. 开一个哈希表映射数字→字符集合
    2. 遍历给定的数字，然后几个集合做笛卡尔积即可

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char,unordered_set<char>> m;
        m['2']={'a','b','c'};
        m['3']={'d','e','f'};
        m['4']={'g','h','i'};
        m['5']={'j','k','l'};
        m['6']={'m','n','o'};
        m['7']={'p','q','r','s'};
        m['8']={'t','u','v'};
        m['9']={'w','x','y','z'};

        vector<string> res;
        string s;        
        
        if (digits.size()==1){
            for (auto i:m[digits[0]]){
                s.push_back(i);
                res.push_back(s);
                s.clear();
            }
            return res;
        }
        if (digits.size()==2){
            for (auto i:m[digits[0]]){
                for (auto j:m[digits[1]]){
                    s.push_back(i);
                    s.push_back(j);
                    res.push_back(s);
                    s.clear();
                }
            }
            
            return res;
        }
        if (digits.size()==3){
            for (auto i:m[digits[0]]){
                for (auto j:m[digits[1]]){
                    for (auto k:m[digits[2]]){
                        s.push_back(i);
                        s.push_back(j);
                        s.push_back(k);
                        res.push_back(s);
                        s.clear();
                    }
                }
            }            
            
            return res;
        }
        if (digits.size()==4){
            for (auto i:m[digits[0]]){
                for (auto j:m[digits[1]]){
                    for (auto k:m[digits[2]]){
                        for (auto n:m[digits[3]]){                        
                            s.push_back(i);
                            s.push_back(j);
                            s.push_back(k);
                            s.push_back(n);
                            res.push_back(s);
                            s.clear();
                        }
                    }
                }
            }            
            
            return res;
        }
        
        return res;
    }
};

    12. 整数转罗马数字

    题意

    整数转罗马数字

    分析

    1. 给出整数→罗马字符的映射
    2. 从最大的罗马数字开始，贪心向下获取字符

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    string intToRoman(int num) {
        vector<pair<int,string>> t= {
            {1000,"M"},
            {900,"CM"},    
            {500,"D"},
            {400,"CD"},
            {100,"C"},            
            {90,"XC"},            
            {50,"L"},            
            {40,"XL"},
            {10,"X"},
            {9,"IX"},
            {5,"V"},
            {4,"IV"},           
            {1,"I"},
        };
        
        string res;
        
        for (auto i:t){
            while(num>=i.first){
                res+=i.second;
                num-=i.first;
            }            
        }
                
        return res;
    }
};

    13. 罗马数字转整数

    题意

    罗马数字转整数

    分析

    1. 先构建罗马数字 → 数字 的映射
    2. 根据罗马数字的编码，如果当前字符映射的数字比右边映射的数字小，则会减去这个数，否则会加上这个数，故从左扫描一遍模拟即可。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char,int> m= {
            {'M',1000},
            {'D',500},
            {'C',100},            
            {'L',50},            
            {'X',10},
            {'V',5},
            {'I',1},
        };
        
        int res=0;
        
        for (int i=0;i<s.size();i++){
            if (i+1<s.size()&&m[s[i]]<m[s[i+1]]){
                res-=m[s[i]];
            } else {
                res+=m[s[i]];
            }
        }
        
        return res;
    }
};

原地哈希

原地哈希是指直接利用原数组进行哈希。通常是给一个数组，然后数的范围基本在 [0,n] 之间，然后后求缺失、重复的数，只需把数放到对应下标位置，然后再遍历判断即可。

  • list

    41. 缺失的第一个正数

    题意

    给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

    请你实现时间复杂度为 .

    额外哈希

    最简单的自然是开一个哈希表，然后第一遍遍历统计正整数，再遍历正整数，找第一个不存在的即可。

    class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> s;
        
        for (auto i:nums){            
            if (i>0&&i<=nums.size()){
                s.insert(i);
            }
        }
                
        for (int i=1;i<pow(2,31);i++){
            if(s.find(i)==s.end()){
                return i;
            }
        }
        
        return -1;
    }
};

    时间复杂度：，空间复杂度：

    原地哈希

    但是使用额外的哈希表需要 的空间复杂度，而题目要求不使用额外空间。

    我们先来考虑，如果不使用哈希表的话，我们会怎么做：

    1. 暴力
    2. 排序

    暴力和排序的空间复杂度都是 ，但是时间复杂度显然太高，而无论我们怎么继续优化，似乎都达不到线性的时间复杂度。

    似乎我们还是需要使用哈希表，但是题目又要求不使用额外的空间，这句话什么意思？不使用额外空间，那说明已经给定的空间不算咯。很好，我们似乎忽略了些什么，虽然不让使用额外空间，但是，给定的数组不就是一个数组吗？

    所谓哈希表：就是哈希函数+空间而已。而现在空间有了，问题就是证明设计哈希函数了。

    现在来看，题目还给了些什么条件：

    1. 未排序
    2. 数据有正有负
    3. 有重复元素

    而要求的是什么？没有出现的最小正整数。

    显然，只有正整数才是我们需要思考的，其它数直接无视即可。

    而我们使用哈希表的时候是证明做的？开哈希表判断一个正整数是否存在。而现在空间有了，哈希函数怎么写呢？

    我们知道，数组的索引是 0,1,2,.. ，而要求的是正整数 1,2,3..，自然的，我们可以这样设计哈希函数：f(x)=x-1

    那么算法步骤如下：

    1. 遍历数组
    2. 若数不是正整数，则无视
    3. 如果数已经映射到对于的空间上后，即 nums[i]=nums[nums[i]-1]，则无视
    4. 否则，将该数存到对应的空间上（但是对应空间上也有一个数，所以需要换到现在这数的位置上来）
    class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for (int i=0;i<nums.size();){            
            if (nums[i]>0 && nums[i]<=nums.size() && nums[i]!=nums[nums[i]-1]){
                swap(nums[i],nums[nums[i]-1]);
            } else {
                i++;
            }
        }
        
        for (int i=0;i<nums.size();i++){
            if (nums[i]!=i+1){
                return i+1;
            }
        }
        
        return nums.size()+1;
    }
};

    时间复杂度：，空间复杂度：

    448. 找到所有数组中消失的数字

    题意

    找出 [1,n] 中不存在的数字

    分析

    类似于 41 题，最简单的方法就是排序，但是这样复杂度不是线性的，而想要线性的时间复杂度，自然的想法是开一个哈希表暂存。当然这题由于数字的特殊性，所以我们直接开个数组，哈希函数就是 f(x)=x-1 即可。然后遍历一遍数组判断即可。

    优化

    实际上，我们没有必要新开一个数组暂存，我们可以利用原始数组进行哈希，哈希函数都不用变，只是哈希存不过之后，由于原理的位置也有元素，所以需要交换过来。同时，由于当前位置元素变动了，所以直到当前元素正确存放了元素，都要一直对当前元素哈希。

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
       for (int i=0;i<nums.size();) {
           if(nums[i]!=nums[nums[i]-1]){
               swap(nums[i],nums[nums[i]-1]);
           } else {
               i++;
           }
       }

        vector<int> res;
        
        for (int i=0;i<nums.size();i++){
            if(nums[i]!=i+1){
                res.push_back(i+1);
            }
        }
        
        return res;
    }
};

    442. 数组中重复的数据

    题意

    找出重复的元素

    分析

    和 448 基本一样，只是那个题要找缺失的，而这题找的是重复的元素。类似 448 的做法，原地哈希，把 nums[i] 放到 nums[nums[i]-1] 的位置上，注意交换后当前指针不移动，因为当前元素变化了。

    最后扫描的时候，对应位置数不相等的即是答案，448 存的是坐标+1，而这题存的就是数组里的元素。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int i=0;i<nums.size();){
            if (nums[i]!=nums[nums[i]-1]){
                swap(nums[i],nums[nums[i]-1]);
            } else {
                i++;
            }
        }
        
        for (int i=0;i<nums.size();i++){
            if(nums[i]!=i+1){
                res.push_back(nums[i]);
            }
        }        
        
        return res;
    }
};

    287. 寻找重复数

    题意

    寻找重复的数

    分析

    和 442 基本一样，只是 442 重复的元素不只一个，而这题只有一个。

    类似 448 的做法，原地哈希，把 nums[i] 放到 nums[nums[i]-1] 的位置上，注意交换后当前指针不移动，因为当前元素变化了。

    最后扫描的时候，对应位置数不相等的即是答案，448 存的是坐标+1，而这题存的就是数组里的元素。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (int i=0;i<nums.size();){
            if (nums[i]!=nums[nums[i]-1]){
                swap(nums[i],nums[nums[i]-1]);
            } else {
                i++;
            }
        }
        
        for (int i=0;i<nums.size();i++){
            if(nums[i]!=i+1){
                return nums[i];
            }
        }        
        
        return -1;
    }
};

    268. 丢失的数字

    题意

    给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

    分析

    类似于 41、448、442、287 等题，都是给一个数组，然后数的范围基本在 [0,n] 之间，然后求缺失、重复的数，这种题都是典型的利用原数组进行哈希，只是这题的范围包括了 0，那么哈希函数就变成了 f(x)=x 了，而且如果等于 n 则跳过不管。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i=0;i<nums.size();){   
            if(nums[i]<nums.size() && nums[i]!=i){
                swap(nums[i],nums[nums[i]]);
            } else {
                i++;
            }
        }
        for (int i=0;i<nums.size();i++){
            if(nums[i]!=i){
                return i;
            }
        }
        
        return nums.size();    
    }
};

滚动哈希

  • list

集合

集合运算，求交集等，一般使用 set 来做，或者数据范围较小的话，可以用 int 表示一个集合，然后位运算计算。

  • list

    349. 两个数组的交集

    题意

    给定两个数组，编写一个函数来计算它们的交集。

    分析

    1. 开一个 set，遍历一遍先放入集合
    2. 再扫一遍判断是否在集合中，并放入结果集合

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s;
        unordered_set<int> res;
        vector<int> r;
        
        for (int i=0;i<nums1.size();i++){
            s.insert(nums1[i]);
        }
        for (int i=0;i<nums2.size();i++){
            if(s.find(nums2[i])!=s.end()){
                res.insert(nums2[i]);
            }
        }
        for (auto i:res){
            r.push_back(i);
        }
        
        return r;
    }
};

    350. 两个数组的交集 II

    题意

    求数组交集，有重复元素

    分析

    349 的进阶版，允许重复，349 由于没有重复，故可以直接使用 set 来判断，而这题由于有重复，故要记录出现次数了，所以开 map 来存。

    1. 扫一遍数组 1，记录频次
    2. 扫数组 2，判断是否出现，并出现一次频次减少1

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> m;
        vector<int> res;
        
        for (int i=0;i<nums1.size();i++){
            m[nums1[i]]++;
        }
        
        for (int i=0;i<nums2.size();i++){
            if (m[nums2[i]]>0){
                res.push_back(nums2[i]);
                m[nums2[i]]--;                
            }
        }
        
        return res;
    }
};

    2032. 至少在两个数组中出现的值

    题意

    求集合交集的并集

    分析

    三个集合两两相交，然后再并即可。这题可以熟悉下标准库的用法。

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {
        set<int> t1;
        
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        sort(nums3.begin(),nums3.end());
        
        set_intersection(nums1.begin(),nums1.end(),
                         nums2.begin(),nums2.end(),inserter(t1,t1.begin()));
                
        set_intersection(nums1.begin(),nums1.end(),
                          nums3.begin(),nums3.end(),inserter(t1,t1.begin()));
        
        
        set_intersection(nums2.begin(),nums2.end(),
                          nums3.begin(),nums3.end(),inserter(t1,t1.begin()));
        
        
        vector<int> r;
             
        for (auto i:t1){
            r.push_back(i);
        }
             
        return r;
    }
};

    500. 键盘行

    题意

    判断字符串是否是另一个字符串的子集

    分析

    用 int 存字符串集合，然后用 & 运算取交集判断

    优化

    无

    效率

    时间复杂度：

    空间复杂度：

    代码

    class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        vector<string> res;
        
        int x1=0;
        int x2=0;
        int x3=0;
        int t=0;
        string s1="qwertyuiop";
        string s2="asdfghjkl";
        string s3="zxcvbnm";
        
        for (auto i:s1) {        
            x1=setBit(x1,i-'a');
        }
        for (auto i:s2) {
            x2=setBit(x2,i-'a');
        }
        for (auto i:s3) {
            x3=setBit(x3,i-'a');
        }
                
        for (auto w:words){
            t=0;
            for (auto c:w){
                t=setBit(t,(char)(c|32)-'a');
            }
            if((x1&t)==t || (x2&t)==t || (x3&t)==t){
                res.push_back(w);
            }
        }                
        
        return res;
    }
    
    int setBit(int x,int pos){
        return x|(1<<pos);
    }
};

总结

哈希表的重要性不言而喻，不像字符串、数组、栈队列这些数据结构，哈希表不光要做它的应用，还需要掌握它的原理和设计以及一些参数的原理，而从面试的角度来看，甚至后者还要重要许多。哈希表的题重点来说单独来看不是很难，主要就是去重，存在性问题，集合处理等等题型，而稍微困难一点的题通常都是和其它知识点结合起来的，比如滑动窗口+哈希表就是一个非常常见的考点。哈希表的做题要掌握的有哈希函数+存储空间的选择，可以直接开数组，可以字符 -’a’，可以用 int 模拟，还可以原地处理等等。

参考

哈希表

分享｜2021 秋招算法总结 8 - 哈希篇

哈希函数

哈希表

查找表类算法

hash 算法的数学原理是什么，如何保证尽可能少的碰撞？

为什么要整数哈希

What integer hash function are good that accepts an integer hash key?

Hash function for floats

Why does HashMap require that the initial capacity be a power of two?

hashing 的一些正确姿势

Why is the bucket size 16 by default in HashMap?

JDK 源码中 HashMap 的 hash 方法原理是什么？

哈希表之 bkdrhash 算法解析及扩展

如何对一个 hash 表扩容？

Redis 的 hashtable 是如何扩容的

good hash table primes

What is the significance of load factor in HashMap?

面试官：为什么 HashMap 的加载因子是 0.75？

HashMap 的 defaultLoadFactor 的一种推导计算思路

评论 (5)