【STL容器使用案例】雀魂启动 (map容器[]重载)

牛客上的一题: 雀魂启动
看了大佬的dfs用的是两个vector容器（一个计数，一个计牌，还要排序）

#include 
using namespace std;

bool isHu(vector nums){//其实是一个dfs的过程
    if (nums.empty())    return true;//递归出口
    int cnt = count(nums.begin(), nums.begin()+4, nums[0]);//记录与首元素相同的数字的个数
    if (nums.size() % 3 != 0 && cnt >= 2){//取雀头（只会取一次）
        if ( isHu(vector(nums.begin() + 2, nums.end())) )   return true;
    }
    if (cnt >= 3){//取刻子（三个相同的数字）
        if ( isHu(vector(nums.begin() + 3, nums.end())) )    return true;
    }
    if(count(nums.begin(), nums.end(), nums[0]+1) > 0 && count(nums.begin(), nums.end(), nums[0] + 2) > 0){//取顺子
        int val = nums[0];
        nums.erase(nums.begin());//去掉一个首元素（顺子的第一个）
        nums.erase(find(nums.begin(), nums.end(), val + 1));//去掉一个首元素+1（顺子的第二个）
        nums.erase(find(nums.begin(), nums.end(), val + 2));//去掉一个首元素+2（顺子的第三个）
        if (isHu(nums)) return true;
    }
    return false;
}
int main(){
    vector nums(13), res;//已有的13张牌
    for (int i = 0; i < 13; ++i)    cin >> nums[i];
    sort(nums.begin(), nums.end());//先排序
    for (int i = 1; i <= 9; ++i){//遍历下一张可能的牌
        if (count(nums.begin(), nums.end(), i) == 4)    continue;//最多就4张，真的不能再多了
        nums.insert(lower_bound(nums.begin(), nums.end(), i), i);//插入i
        if(isHu(nums))     res.push_back(i);   //判断是否ok
        nums.erase(lower_bound(nums.begin(), nums.end(), i));//恢复原始nums数组
    }
    if (res.empty()) cout << 0 << endl;
    else    for (const auto &v : res)   cout << v <<" ";
    return 0;
}

觉得可以改成一个map容器（可以计数有可以记数，还自动排好序了），相比vector不用去想下标如何移动，所以写了一个map版本的。虽然比较慢，但是大家可以参考一下。（特别是对于map容器的理解有一定要求，比如map重载的[]） 还有比较坑的一点是要注意雀头的数量，有些情况是会可以形成多个雀头而导致诈胡的情况,比如程序末尾注释的第三个测试用例。

#include 
using namespace std;

// flag 控制可不可以有雀头
bool isHu(map nums,bool flag){//其实是一个dfs的过程
    if (nums.empty()){
        return true;//递归出口
    }
    //记录与首元素相同的数字的个数，因为数组有序，并且最多出现4次，所以不用遍历所有区间
    int key = nums.begin()->first;
    int cnt = nums[key];


    //注意：下面的几个if不能加上else奥，因为每种情况都需要考虑
    if (cnt >= 3){//尝试取一个刻子（三个相同的数字）
        nums[key]-=3;
        if(nums[key]==0){
            nums.erase(key);
        }
        if (isHu(nums,flag)){
            return true;
        }
        nums[key]+=3;
    }


    //取了雀头之后的size肯定能被3整除（因为除了雀头都是三个一组取的）
    if (cnt >= 2 && flag){//当前两个元素相等时，尝试以他两作为雀头
        flag=false;
        nums[key]-=2;
        if(nums[key]==0){
            nums.erase(key);
        }
        if (isHu(nums,flag)){//已经有了雀头就不能再有了
            return true;
        }
        flag=true;
        nums[key]+=2;
    }

    //首元素以顺子的形式出现
    //先判断首元素+1和+2的元素是否存在，只有同时存在才有可能构成顺子
    if(nums.size()<3){
        return false;
    }
    auto it1 = nums.begin();
    int key1=it1->first;
    it1++;
    int key2=it1->first;
    it1++;
    int key3=it1->first;
    if(nums[key1]>0&&nums[key2]>0&&nums[key3]>0&&key1==key2-1&&key1==key3-2){
        //把该顺子从数组中去掉，继续判断剩下的顺子
        nums[key1]--;
        if(nums[key1]==0) nums.erase(key1);
        nums[key2]--;
        if(nums[key2]==0) nums.erase(key2);
        nums[key3]--;
        if(nums[key3]==0) nums.erase(key3);

        if (isHu(nums,flag)) return true;

        nums[key1]++;
        nums[key2]++;
        nums[key3]++;
    }
    return false;
}

int main(){
    map nums;//有序
    vector res;
    int temp;
    for (int i = 0; i < 13; ++i){
        cin >> temp;
        nums[temp]++;
    }
    for (int i = 1; i <= 9; ++i){//遍历下一张可能的牌
        if (nums[i]  == 4){
            continue;//最多就4张，真的不能再多了
        }

        nums[i]++;//插入i
        if(isHu(nums,true)){
            res.push_back(i);   //判断是否ok
        }
        nums[i]--;//恢复原始nums数组
        if(nums[i]==0) nums.erase(i);
    }
    if (res.empty()){
        cout << 0 << endl;
    }
    else{
        for (const auto &v : res){
            cout << v <<" ";
        }
    }
    return 0;
}
// 3 3 3 4 4 4 6 6 6 8 8 9 9
// 1 5 5 5 4 4 4 6 6 6 8 8 8
// 1 1 1 3 4 5 5 5 5 6 7 9 9

其中map容器重载了[]，当用它来访问一个不存在的key的时候他会自动插入。
那[]和insert有什么区别呢?总得来说：当实现“向 map 容器中添加新键值对元素”的操作时，insert() 成员方法的执行效率更高。而在实现“更新 map 容器指定键值对的值”的操作时，operator[ ] 的效率更高。（看某一网站的总结，本人为仔细看过源码）（其实不用在意这一点效率吧）