宁晋网站建设免费的网站域名查询app

题目描述

题解思路

长度为k的二进制子串所有取值的集合为[0, sum(k)]，其中sum(k)为1 + 2 + 4 + … + 1 << (k - 1)

我们只需要创建一个长度为sum(k) + 1的数组 f ，其中下标为 i 的元素用来标记字符串中子串取值为 i 是否不存在

我们只需要遍历字符串中所有长度为 k 的子串，然后将其数组 f 中二进制值标记为存在

最后

• 如果数组 f 中存在子串中不存在的二进制值，则结果为false
• 如果数组 f 中子串二进制值都存在，则结果为true

题解代码

impl Solution {pub fn has_all_codes(s: String, k: i32) -> bool {if k as usize >= s.len() {return false;}let s = s.as_bytes();let mut max_val = 0;let mut sum = 0;for i in 0..k as usize {max_val += 1 << i;if s[i] == b'1' {sum += 1 << i;}}let mut f = vec![true; max_val + 1];f[sum] = false;for i in k as usize..s.len() {if s[i - k as usize] == b'1' {sum -= 1;}sum >>= 1;if s[i] == b'1' {sum += 1 << (k - 1);}f[sum] = false;}for ok in f {if ok {return false;}}true}
}

题目链接

https://leetcode.cn/problems/check-if-a-string-contains-all-binary-codes-of-size-k/description/