淘宝客需要自己做网站吗,四川遂宁做网站的公司,建设部人事考试网站官网,wordpress分页重写1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣#xff08;Leetcode#xff09;
目录 一、题目
二、题目解读 三、代码 一、题目
给定一个二进制字符串 s 和一个正整数 n#xff0c;如果对于 [1, n] 范围内的每个整数#xff0c;其二进制表示都是 s 的 子字符串 Leetcode
目录 一、题目
二、题目解读 三、代码 一、题目
给定一个二进制字符串 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 就是 11 n 10⁹
二、题目解读 1、暴力Ⅰ 我们可以遍历1到n看是否其二级制是s的子字符串。在这个过程我们可以进行倒序进行判断先判断较大的数。 可能有人会说这样不会超时吗 举例说明。如果 n7单看闭区间 [4,7]有 4 个互不相同的整数它们的二进制长度均为 3。如果要让字符串 s 包含这 4 个数s 中至少要有 4 个长为 3 的互不相同的子串。考虑到这些子串可以有重叠部分设 s 的长度为 m则应满足 m≥3(4−1)6否则直接返回false。想象一个长为 3 的滑动窗口在 s 中滑动至少要得到 4 个子串。随着 n 的变大m 的长度也应当随之变大。本题 m 至多为 1000而 n 却高达 10⁹ 。 所有如果 n≥2014n可以直接返回 false。 Ⅱ、 反过来想把 s 的子串都转成二进制数如果数字在 [1,n] 内就保存到一个哈希表中。如果哈希表的大小最终为 n就说明 [1,n] 的二进制都在 s 里面。 2、滑动窗口 1、根据 n 和 m字符串长度 的值来提前判断是否要返回 false。 2、只需要考虑长为 k 和 k1 的这两组二进制数 s 是否都有因此可以用长为 k 和 k1 的滑动窗口实现从而做到线性时间复杂度。 3、进一步地由于区间 [2ᴷ,n] 内的所有数右移一位可以得到区间 [2ᴷ⁻¹,n/2 ]所以对于 [2ᴷ⁻¹,2ᴷ−1]只需从 n/21 开始考虑。 三、代码 代码Ⅰ
class Solution {public boolean queryString(String s, int n) {for (int i n; i 1; i--) {if (!s.contains(Integer.toBinaryString(i))) {return false;}}return true;}
} 代码Ⅱ
class Solution {public boolean queryString(String S, int n) {HashSetInteger set new HashSet();char[] s S.toCharArray();for (int i 0, m s.length; i m; i) {int x s[i] - 0;if (x 0) continue; // 二进制数从 1 开始for (int j i 1; x n; j) {set.add(x);if (j m) break;x (x 1) | (s[j] - 0); // 子串 [i,j] 的二进制数}}return set.size() n;}
}
滑动窗口
class Solution {public boolean queryString(String s, int n) {if (n 1)return s.contains(1);int k 31 - Integer.numberOfLeadingZeros(n); // n 的二进制长度减一if (s.length() Math.max(n - (1 k) k 1, (1 (k - 1)) k - 1))return false;return check(s, k, n / 2 1, (1 k) - 1) check(s, k 1, 1 k, n);}// 对于长为 k 的在 [lower, upper] 内的二进制数判断这些数 s 是否都有private boolean check(String s, int k, int lower, int upper) {if (lower upper) return true;var seen new HashSetInteger();int mask (1 (k - 1)) - 1;int x Integer.parseInt(s.substring(0, k - 1), 2);for (int i k - 1, m s.length(); i m; i) {// mask 可以去掉最高比特位从而实现滑窗的「出」// 1 | (s.charAt(i) - 0) 即为滑窗的「入」x ((x mask) 1) | (s.charAt(i) - 0);if (lower x x upper)seen.add(x);}return seen.size() upper - lower 1;}
} 超详细题解可看
1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣Leetcode
