生成不含相邻零的二进制字符串

100328. 生成不含相邻零的二进制字符串

给你一个正整数 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

相似题目

不含连续1的非负整数

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<string> validStrings(int n) { } };

javascript 解法, 执行用时: 8 ms, 内存消耗: 53.8 MB, 提交时间: 2024-10-29 08:46:31

/**
 * @param {number} n
 * @return {string[]}
 */
var validStrings = function(n) {
    const res = [];
    function dfs(arr) {
        if (arr.length === n) {
            res.push(arr.join(''));
            return;
        }
        if (arr.length === 0 || arr[arr.length - 1] === '1') {
            arr.push('0');
            dfs(arr);
            arr.pop();
        }
        arr.push('1');
        dfs(arr);
        arr.pop();
    }
    dfs([]);
    return res;
};

php 解法, 执行用时: 115 ms, 内存消耗: 21.4 MB, 提交时间: 2024-07-09 09:57:43

class Solution {

    /**
     * @param Integer $n
     * @return String[]
     */
    function validStrings($n) {
        $ans = [];
        $max = 2**$n; // 2^n
        
        for ($i = 0; $i < $max; $i++) {
            $x = $max - 1 ^ $i; // 1<<n - 1 ^ i
            // 检查 x 的二进制表示中，是否没有相邻的 1
            // PHP 中没有直接的位操作检查连续位，因此我们需要通过转换二进制字符串来检查
            $binStr = decbin($x); // 转换为二进制字符串
            $length = strlen($binStr);
            $hasAdjacentOnes = false;
            
            for ($j = 0; $j < $length - 1; $j++) {
                if ($binStr[$j] == '1' && $binStr[$j + 1] == '1') {
                    $hasAdjacentOnes = true;
                    break;
                }
            }
            
            if (!$hasAdjacentOnes) {
                // 使用 str_pad 填充前导零
                $ans[] = str_pad(decbin($i), $n, '0', STR_PAD_LEFT);
            }
        }
        
        return $ans;
    }
}

golang 解法, 执行用时: 6 ms, 内存消耗: 6.3 MB, 提交时间: 2024-07-09 09:54:36

func validStrings(n int) (ans []string) {
	for i := 0; i < 1<<n; i++ {
		x := 1<<n - 1 ^ i
		if x>>1&x == 0 {
			ans = append(ans, fmt.Sprintf("%0*b", n, i))
		}
	}
	return
}

cpp 解法, 执行用时: 13 ms, 内存消耗: 14.1 MB, 提交时间: 2024-07-09 09:54:15

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) == 0) {
                ans.push_back(bitset<18>(i).to_string().substr(18 - n));
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 3 ms, 内存消耗: 44.5 MB, 提交时间: 2024-07-09 09:54:01

class Solution {
    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        int mask = (1 << n) - 1;
        for (int i = 0; i < (1 << n); i++) {
            int x = mask ^ i;
            if (((x >> 1) & x) == 0) {
                ans.add(Integer.toBinaryString((1 << n) | i).substring(1));
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 76 ms, 内存消耗: 17.4 MB, 提交时间: 2024-07-09 09:52:09

class Solution:
    def validStrings(self, n: int) -> List[str]:
        ans = []
        mask = (1 << n) - 1
        for i in range(1 << n):
            x = mask ^ i
            if (x >> 1) & x == 0:
                ans.append(f"{i:0{n}b}")
        return ans

上一题

下一题

详情