class Solution {
public:
bool queryString(string s, int n) {
}
};
1016. 子串能表示从 1 到 N 数字的二进制串
给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。
子字符串 是字符串中连续的字符序列。
示例 1：
输入：s = "0110", n = 3 输出：true
示例 2：
输入：s = "0110", n = 4 输出：false
提示：
1 <= s.length <= 1000s[i] 不是 '0' 就是 '1'1 <= n <= 109原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-05 18:54:19
func getBinary(a int) (res string) {
if a == 0 {
return "0"
}
for a > 0 {
if a&1 == 1 {
res = "1" + res
} else {
res = "0" + res
}
a >>= 1
}
return res
}
func queryString(s string, n int) bool {
limit := (1 << 9) - 1
if n > limit {
return false
}
for i := 1; i <= n; i++ {
if !strings.Contains(s, getBinary(i)) {
return false
}
}
return true
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-12-05 18:53:16
func queryString(S string, N int) bool {
var tmp string
var res = true
for i:=1; i<=N; i++ {
tmp = fmt.Sprintf("%b", i)
if !strings.Contains(S, tmp) {
res = false
break
}
}
return res
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-12-05 18:51:46
class Solution:
def queryString(self, S: str, n: int) -> bool:
res = True
if n < 2: return str(n) in S
for i in range(n >> 2, n + 1):
s = str(bin(i))[2:]
if s in S:
res &= True
else:
res &= False
break
return res
java 解法, 执行用时: 0 ms, 内存消耗: 39.6 MB, 提交时间: 2022-12-05 18:46:26
class Solution {
public boolean queryString(String S, int N) {
for(int i=1;i<=N;i++) {
if(!S.contains(Integer.toBinaryString(i)))
return false;
}
return true;
}
}