【STL容器使用案例】雀魂启动 (map容器\[]重载)
牛客上的一题: 雀魂启动看了大佬的dfs用的是两个vector容器(一个计数,一个计牌,还要排序)#include <bits/stdc++.h>using namespace std;bool isHu(vector<int> nums){//其实是一个dfs的过程if (nums.empty())return true;//递归出口int cnt = count(num
·
牛客上的一题: 雀魂启动
看了大佬的dfs用的是两个vector容器(一个计数,一个计牌,还要排序)
#include <bits/stdc++.h>
using namespace std;
bool isHu(vector<int> 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<int>(nums.begin() + 2, nums.end())) ) return true;
}
if (cnt >= 3){//取刻子(三个相同的数字)
if ( isHu(vector<int>(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<int> 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 <bits/stdc++.h>
using namespace std;
// flag 控制可不可以有雀头
bool isHu(map<int,int> 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<int,int> nums;//有序
vector<int> 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[ ] 的效率更高。(看某一网站的总结,本人为仔细看过源码)(其实不用在意这一点效率吧)
更多推荐
已为社区贡献2条内容
所有评论(0)