C++算法 枚举（下）

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

༺ 个人主页 · 纪念229 ༻

🏠我的博客主页🏠

༒专栏目录：《数据结构》༒

༒专栏目录：《算法》༒

༒专栏目录：《C++》༒

༒专栏目录：《MySQL数据库》༒

༒专栏目录：《前端开发》༒

༒其它有趣的计算机知识༒

༺世上本没有路，走的人多了自然就有了༻

本篇文章接上回扫雷算法题讲解还有关二进制枚举枚举的题目,希望对你有所帮助

题目链接: 扫雷 子集 费解的开关

文章目录

• 1.扫雷
• 2.子集
• 3.费解的开关

1.扫雷

具体结构这里就不讲解了，直接上核心思想

**//这里雷的排放我们对第一行第一个进行枚举分为放雷和不放雷

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;
int a1[N], a2[N];
int n;

int main()
{
cin >> n;

//我们从a1下标1开始枚举输入的数据 下标0计为0无雷，a1[i]的值为a2[i] – a1[i – 1] – a1[i – 2]如果放雷符合规则就记一次
for(int i = 1; i <= n; i++)
{
cin >> a2[i];
//第二列中有大于3的数无方案
if(a2[i] > 3){
cout << 0;
return 0;
}
}
int ret = 0;//定义一个ret计雷方案 个数
//我们设置a1[1]有雷
a1[1] = 1 ;
int flag = 1;//默认方案成功
for(int i = 2; i <= n; i++)
{
a1[i] = a2[i – 1] – a1[i – 1] – a1[i – 2];//这里是 a1[i] = a2[i – 1] – a1[i – 1] – a1[i – 2]不是a1[i] = a2[i] – a1[i – 1] – a1[i – 2]
if(a1[i] <0 || a1[i] > 1) //a1[i]不为0或1说明此方案失败 这里用||用&&不存在这样的数
{
flag = 0;
break;
}
}
//最后我们还要验证a1[n + 1] = a2[n] – a[n] – a[n – 1];因为要求a2[i] = a1[n- 1] + a1[n] + a1[n + 1]我们要求所有有效数据格都符合该规则
if(a2[n] != a1[n – 1] + a1[n] + a1[n + 1]) flag = 0;
if(flag == 1) ret++;

// 我们设置a1[1]没有雷
//先清空s1数据为0
memset(a1,0,sizeof a1); //memset和memcpy的头文件是cstring不是string
a1[1] = 0 ;
flag = 1;//默认方案成功
for(int i = 2; i <= n; i++)
{
a1[i] = a2[i – 1] – a1[i – 1] – a1[i – 2];
if(a1[i] <0 || a1[i] > 1) //a1[i]不为0或1说明此方案失败
{
flag = 0;
break;
}
}
if(a2[n] != a1[n – 1] + a1[n] + a1[n + 1]) flag = 0;
if(flag == 1) ret++;
cout << ret;
return 0;
}

输入n后我们确定a2要输入多少行从1开始到n利用for循环遍历

这里只有一个要求输入的东西不大于3因为a2[i]只能测到a1[i – 1] a1[i] a1[i + 1] 所以a2[i]大于三是不存在的若是有直接返回0说明此雷的设计方案没有成立的

for(int i = 1; i <= n; i++)
{
cin >> a2[i];
//第二列中有大于3的数无方案
if(a2[i] > 3){
cout << 0;
return 0;
}
}

我们知道输入完a2后我们要根据a1[1]枚举有雷和无雷两种情况（a1[0]默认为0无雷a1[n + 1]默认为无雷）若是两种情况都符合规则那么就有2种方案合理（最多有2种方案合理最少没有方案0种）

我们定义一个ret为雷的设计规则合理数目刚开始为0

在定义一个flag为1默认该规则符合 我们先枚举a[1]有雷

判断规则为a1[i] = a2[i -1] – a1[i – 1] – a1[i – 2];这么设计是因为a1[0]和a1[1]已经设计好了我们要从a1[2]开始所以 a1[2] = a2[1] – a1[1] – a1[0];以此类推我们的for循环从2开始到n即可在运算过程中若是a1[i]大于1或小于0就设置flag为0brak退出循环，出了循环后最后我们还要判断a1[n + 1] = a2[n] – a1[n] – a1[n – 1];不成立的话就将flag为0

然后我们判断flag为1为1的话就符合雷的设计规则将ret ++

for(int i = 2; i <= n; i++)
{
a1[i] = a2[i – 1] – a1[i – 1] – a1[i – 2];//这里是 a1[i] = a2[i – 1] – a1[i – 1] – a1[i – 2]不是a1[i] = a2[i] – a1[i – 1] – a1[i – 2]
if(a1[i] <0 || a1[i] > 1) //a1[i]不为0或1说明此方案失败 这里用||用&&不存在这样的数
{
flag = 0;
break;
}
}
//最后我们还要验证a1[n + 1] = a2[n] – a[n] – a[n – 1];因为要求a2[i] = a1[n- 1] + a1[n] + a1[n + 1]我们要求所有有效数据格都符合该规则
if(a2[n] != a1[n – 1] + a1[n] + a1[n + 1]) flag = 0;
if(flag == 1) ret++;

然后我们接着枚举a1[1]无雷

在枚举前我们要memset(a1, 0, sizeof a1);不用没关系反正第一个和最后一个都是0其它的都是赋值的

逻辑与有雷没区别这里我就不讲了 就是把a1[1] = 0 而不是 a1[1] = 1;

// 我们设置a1[1]没有雷
//先清空s1数据为0
memset(a1,0,sizeof a1); //memset和memcpy的头文件是cstring不是string
a1[1] = 0 ;
flag = 1;//默认方案成功
for(int i = 2; i <= n; i++)
{
a1[i] = a2[i – 1] – a1[i – 1] – a1[i – 2];
if(a1[i] <0 || a1[i] > 1) //a1[i]不为0或1说明此方案失败
{
flag = 0;
break;
}
}
if(a2[n] != a1[n – 1] + a1[n] + a1[n + 1]) flag = 0;
if(flag == 1) ret++;

最后打印ret即可 cout << ret;

二进制枚举

2.子集

这里利用的是二进制枚举的方式将该整形数组的子集枚举出来

我们首先得到该整形数组的个数n将 1 << n （2^n）利用这个我们可以遍历出所有子集的情况比如说32位…1011我们就枚举出整形数组下标为0，1，3所指向的数据作为一个子集我们从0开始到 2 ^ n – 1 00000001 00000010 …可以枚举出所有整形数组的子集最后打印出这个数组字符串即可

//一个数组集合找子集我们可以利用二进制枚举解题(就是利用给出数组的个数利用二进制枚举解题)
// 用到该位是否为1 x >> i & 1和 1 << n中从0到 2^n – 1的数
//我们利用32为第0为为1就有1第1为为1就为2….类推分出子集组合
//我们找到子集元素中最大的数据在32位的第几位(当该位已及之前的低位都为1时说明枚举结束)

class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
//定义一个数组元素数整形数组（装子集的容器）
vector<vector<int>> a;
int n = nums.size();
//列出子集
//我们利用for循环下标小于1 << n的数据二进制就可以遍历从0到该数据位数 – 1 的所有位数上的数据
//我们对这些数据都进行for循环下标小于n（移动位不超过n）如果某位为1那么该下标上的数据会入整形数组
for(int st = 0; st < (1 << n); st++)//st作为数据(进行for循环不是作为下标)被第二个循环遍历组合成子集（与数组的类型无关）(1 << n 就是 2^n – 1)
{
//定义一个整型数组来装子集最后将子集放入a即可
vector<int> b;//作为子集装组合数
for(int i = 0; i < n; i++)
{
//判断st数据在某位上为1（如果为1说明该位（下标）可以进入子集作为组合）
if(st >> i & 1) b.push_back( nums[i]);//最开始st为0无论如何都入不了b所以一定会有一个空的b子集放入a中 这里是 >> i不是 << i(这么移的话第一个都为0) 而且这里是 st >> i & 1 目的看我们要求的位是否为1st >> i == 1这样不行它的意思是移动后的数据是否为1
}
//最后将b子集放入a中
a.push_back(b);//如果nums
}

return a;
}
};

该题是核心代码模式 题目它给了一个vector nums整形数组返回只是一个元素为字符串的的数组

首先我们定一个vector<vector> a作为装子集的容器 然后我们将该整形数组的个数数出来定义为n 0到1 << n -1就是我我们要枚举枚举的所有方式 每个值所对应的二进制值 000110011从左到右下标从0开始下标为1所对应的整型数组下标上的数字就作为一个数据加入子集

vector<vector<int>> a;
int n = nums.size();

利用内外双循环外循环我们用st遍历这些数据直到 1 << n – 1 内循环我们利用下标从0到n 我们用 st >> i(将st转换为二进制在往左移动i位)然后将结果按位与1

我们定义一个vectorb数组（子集）装可以作为子集的元素

按位与的意思是两数据对应位的二进制值都为1才为1否则就为0 按位与1 1的二进制位为 0000000001所以我们 st >> i向左移动i位其实除了第0为其它的位数结果一定都为0因为 1的二进制除了第0为其它都为0 0与0 与1按位与都为0 若是st移位后位数为0的数据不为1结果就不为0为1我们就可以判断整形数组在该位作为枚举的值（作为子集元素）我们就将b调用push_back(nums[i])即可

每次st进行一次循环我们将子集b放入用push_back a数组中

刚开始st为0所以b循环结束为空将空子集b放入a中然st每次加1它的二进制随之改变子集的元素每次当然也不同知道最后 st为 2^n – 1的时候32位从0到n – 1位都为1我们将整形数组的所有元素作为子集b放入a中我们把所有的子集枚举完成返回a即可（由于b在内循环和外循环之间所以我们不用重置b因为每次st枚举子集的时候b实例化都为空）

//列出子集
//我们利用for循环下标小于1 << n的数据二进制就可以遍历从0到该数据位数 – 1 的所有位数上的数据
//我们对这些数据都进行for循环下标小于n（移动位不超过n）如果某位为1那么该下标上的数据会入整形数组
for(int st = 0; st < (1 << n); st++)//st作为数据(进行for循环不是作为下标)被第二个循环遍历组合成子集（与数组的类型无关）(1 << n 就是 2^n – 1)
{
//定义一个整型数组来装子集最后将子集放入a即可
vector<int> b;//作为子集装组合数
for(int i = 0; i < n; i++)
{
//判断st数据在某位上为1（如果为1说明该位（下标）可以进入子集作为组合）
if(st >> i & 1) b.push_back( nums[i]);//最开始st为0无论如何都入不了b所以一定会有一个空的b子集放入a中 这里是 >> i不是 << i(这么移的话第一个都为0) 而且这里是 st >> i & 1 目的看我们要求的位是否为1st >> i == 1这样不行它的意思是移动后的数据是否为1
}
//最后将b子集放入a中
a.push_back(b);//如果nums
}

return a;

3.费解的开关

这里由于时间原因下一个复杂的开关我介绍不完我就讲解一下核心的逻辑和用到的二进制运算符的用法，有兴趣的可以做一下

这里用的也是二进制枚举 我们只要看到只有01元素的题我们就可以用二进制枚举来解题

题目意思是要我们多组输入5*5的灯组判断6次以内是否可以将所有的灯全按亮

这里按灯只有开和关两种状态我们输入的5*5的数字字符’1’表示灯亮’0’表示灯暗

我们每次按灯都会让上下左右的灯都改变改变其状态 我们定义一个整形数组每一个元素都代表着二进制（利用二进制看灯的开关状态） 在输入5*5的字符在内循环内我们反着记第j位输入的字符为’0’我们就将a[i] += 1 < < j;(这里我们不适应该’1’放入32位中某位的1吗（我们反着记0为灯亮1为灯暗有利于我们对二进制位数的运算）) 循环结束我们就得到了灯刚开始的状态 因为是多组遍历我们我每次刚开始进入内外双循环时我们先memset a为0

在这里我们定义一个ret用来装按的最少的次数开始我们定义为0xf3f3f3f（一个极大的数） 这里我们枚举出第一行的所有按灯的方式 这里我们定义一个cunt来记录按了多少次灯 我们在全局在定义一个b为了保证每次第一行按的方式时都是原来灯组的状态 只有一个a数据会改变 所以我们memcpy(b, a, sizeof a);

然后我们修改该行在修改下一行再更新下一行的按法直到a[4]我们判断是否为0为0的话说明可以全亮 我们就把ret和cunt去最小的赋值给 ret

最后我们判断ret是否大于6大于的话就打印-1说明6次以内无法全按完小于6打印ret即可然后循环多组判断是否6次以内就可以按完

文章到此就告一段落，希望对你有所帮助，感谢观看！