leetcode位运算(3211. 生成不含相邻零的二进制字符串)

前言

经过前期的基础训练以及部分实战练习，粗略掌握了各种题型的解题思路。接下来重点专项练习，加强重难点知识的练习。

描述

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的

子字符串

中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

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

示例 1：

输入： n = 3

输出： ["010","011","101","110","111"]

解释：

长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输入： n = 1

输出： ["0","1"]

解释：

长度为 1 的有效字符串有："0" 和 "1"。

提示：

• 1 <= n <= 18

实现原理与步骤

本题使用了移位、异或、或、与的二进制bit位的大部分操作。对二进制bit位不熟悉的可以多加练习

1.构建n位的全1的掩码mask。

2.遍历n位的二进制数，将i与mask异或将0转换成1后为x。

3.x>>1&x判断是存在连续的1.

4.通过1<<n|i，将n为的二进制最高位前加1.再通过substring输出。

代码实现

import java.util.*;
public class Main3 {

    public static void main(String[] args) {
        Main3 main3=new Main3();
        List<String> res=main3.validStrings(3);
        System.out.println(res.toString());
    }
    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        //构建位数为n的掩码，示例1中n为3，则mask为111
        int mask = (1 << n) - 1;
        for (int i = 0; i < (1 << n); i++) {
            //i与比特位都是1的mask异或，则标记0的位置位1.
            int x = mask ^ i;
            //x左移1位后与自身与为0，则x不存在练习的1.
            if (((x >> 1) & x) == 0) {
                 //此处Integer.toBinaryString由于会自动移除前面的0，则最第一位补1再通过substring移除
                ans.add(Integer.toBinaryString((1 << n) | i).substring(1));
            }
        }
        return ans;
    }
}