当前位置: 首页 > news >正文

力扣每日一题 3211. 生成不含相邻零的二进制字符串

给你一个正整数 n

如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1",则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串,可以以任意顺序排列。

只要看懂了题目意思,这个题目就无脑暴力就可以了。

第一种方法:用递归,只要考虑根据前面填的数字,后面可以填哪些数字就可以了。

题目要求的就是二进制串没有连续的0出现。

我们可以直接枚举字符串的位置 i 填 1 还是 0:

如果前一个位置是0,那这个位置自然只能是1.

如果前一个位置是1,那这个位置不管是0还是1都可以。

枚举从i=1开始,到 i=n 结束把字符串填入数组即可。

class Solution {
public:void dfs(string s, int len){if (len == 0){ans.push_back(s);return;}if (s[s.length()-1]=='0') dfs(s+"1", len-1);else{dfs(s+"0", len-1);dfs(s+"1", len-1);}}vector<string> validStrings(int n) {ans.clear();str="";nlen = n;dfs("0", n-1);dfs("1", n-1);return ans;}
private:string str;vector<string> ans;int nlen;
};

第二种方法:直接枚举所有二进制长度为n的整数,判断是否满足条件,满足就把数字的二进制填进数组即可。

最容易想到的检查方法就是写出它的二进制,然后遍历找有没有连续的0.

不过其实还有种更快的方法检查,那就是位运算。怎么算呢?我们知道 x & (x >> 1) 的结果可以判断x是否有连续的1,那么我们只要稍微改一下,把x取反,就可以判断有没有连续的0了。

那怎么取反呢?

创建一个低 n 位全为 1 的二进制数 mask = (1 << n) - 1。
计算 x ^ mask,由于 0 和 1 异或后变成了 1,1 和 1 异或后变成了 0,所以 x 的低 n 位都取反了。

class Solution {
public:vector<string> validStrings(int n) {vector<string> ans;int mask = (1 << n) - 1;for (int i = 0; i < (1 << n); i++) {int x = mask ^ i;if (!(x >> 1 & x)) {ans.push_back(bitset<18>(x^mask).to_string().substr(18 - n));}}return ans;}
private:string str;vector<string> ans;int nlen;
};


http://www.mrgr.cn/news/61343.html

相关文章:

  • JS宏进阶:函数、对象和类(三)
  • 127.【C语言】补充:函数的三种调用约定
  • Hadoop3.3.4伪分布式环境搭建
  • 【RedisStack】Linux安装指南
  • 【1】Word:邀请函
  • vscode使用Marscode编程助手
  • 代码随想录 | Day35 | 动态规划 :最小花费爬楼梯不同路径不同路径II
  • Spring Cloud 和 Dubbo 的区别
  • 超好玩又简单-猜数字游戏(有手就行)
  • 【JavaEE】【多线程】定时器
  • 《机器学习by周志华》学习笔记-神经网络-03全局最小误差与局部极小误差
  • QT中使用图表之QChart绘制曲线图
  • Sqoop的安装配置及使用
  • Coredump-A: 配置相关:suid_dumpable
  • 大数据新视界 -- 大数据大厂之大数据重塑影视娱乐产业的未来(4 - 3)
  • 深度学习:Overfitting 成因及解决策略
  • Diving into the HAL-----Interrupts
  • AutoDIR: Automatic All-in-One Image Restoration with Latent Diffusion论文阅读笔记
  • 线上Bug排查清单,测试小哥拿走不谢!
  • Docker快速安装Grafana
  • 2807. 在链表中插入最大公约数 辗转相除和BigDecimal自带求公约数实现
  • Docker Compose一键部署Spring Boot + Vue项目
  • IDEA使用Maven Helper查看整个项目的jar冲突
  • Javaee:单例模式
  • linux 查看磁盘和内存的使用情况
  • 大模型提示词简介 举例