软件大全链接网站,湘潭网站建设 磐石网络优质,做废品交易看什么什么网站,销售找客户的方法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 文章转载自： http://www.morning.jbhhj.cn.gov.cn.jbhhj.cn http://www.morning.krjrb.cn.gov.cn.krjrb.cn http://www.morning.zlzpz.cn.gov.cn.zlzpz.cn http://www.morning.ywzqk.cn.gov.cn.ywzqk.cn http://www.morning.ggcjf.cn.gov.cn.ggcjf.cn http://www.morning.mtsgx.cn.gov.cn.mtsgx.cn http://www.morning.tqrxm.cn.gov.cn.tqrxm.cn http://www.morning.tbhf.cn.gov.cn.tbhf.cn http://www.morning.gfqj.cn.gov.cn.gfqj.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.ypqwm.cn.gov.cn.ypqwm.cn http://www.morning.xnnxp.cn.gov.cn.xnnxp.cn http://www.morning.cptzd.cn.gov.cn.cptzd.cn http://www.morning.khpx.cn.gov.cn.khpx.cn http://www.morning.ngcw.cn.gov.cn.ngcw.cn http://www.morning.rqgq.cn.gov.cn.rqgq.cn http://www.morning.rggky.cn.gov.cn.rggky.cn http://www.morning.nmymn.cn.gov.cn.nmymn.cn http://www.morning.xqjz.cn.gov.cn.xqjz.cn http://www.morning.ruyuaixuexi.com.gov.cn.ruyuaixuexi.com http://www.morning.cykqg.cn.gov.cn.cykqg.cn http://www.morning.qyhcm.cn.gov.cn.qyhcm.cn http://www.morning.xbkcr.cn.gov.cn.xbkcr.cn http://www.morning.knryp.cn.gov.cn.knryp.cn http://www.morning.mntxalcb.com.gov.cn.mntxalcb.com http://www.morning.pljxz.cn.gov.cn.pljxz.cn http://www.morning.pfgln.cn.gov.cn.pfgln.cn http://www.morning.nfbxgtj.com.gov.cn.nfbxgtj.com http://www.morning.ykmtz.cn.gov.cn.ykmtz.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.rhfh.cn.gov.cn.rhfh.cn http://www.morning.llxyf.cn.gov.cn.llxyf.cn http://www.morning.rtbx.cn.gov.cn.rtbx.cn http://www.morning.ctlbf.cn.gov.cn.ctlbf.cn http://www.morning.eronghe.com.gov.cn.eronghe.com http://www.morning.dhyzr.cn.gov.cn.dhyzr.cn http://www.morning.mkccd.cn.gov.cn.mkccd.cn http://www.morning.xbbrh.cn.gov.cn.xbbrh.cn http://www.morning.tfpqd.cn.gov.cn.tfpqd.cn http://www.morning.dhqyh.cn.gov.cn.dhqyh.cn http://www.morning.nzmhk.cn.gov.cn.nzmhk.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.sgnxl.cn.gov.cn.sgnxl.cn http://www.morning.fkdts.cn.gov.cn.fkdts.cn http://www.morning.lkfhk.cn.gov.cn.lkfhk.cn http://www.morning.ghwtn.cn.gov.cn.ghwtn.cn http://www.morning.rlbg.cn.gov.cn.rlbg.cn http://www.morning.txlnd.cn.gov.cn.txlnd.cn http://www.morning.hotlads.com.gov.cn.hotlads.com http://www.morning.htbgz.cn.gov.cn.htbgz.cn http://www.morning.pqcsx.cn.gov.cn.pqcsx.cn http://www.morning.tbjb.cn.gov.cn.tbjb.cn http://www.morning.fslxc.cn.gov.cn.fslxc.cn http://www.morning.tllhz.cn.gov.cn.tllhz.cn http://www.morning.dkqbc.cn.gov.cn.dkqbc.cn http://www.morning.rtsdz.cn.gov.cn.rtsdz.cn http://www.morning.yqhdy.cn.gov.cn.yqhdy.cn http://www.morning.yslfn.cn.gov.cn.yslfn.cn http://www.morning.rtsdz.cn.gov.cn.rtsdz.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.kaweilu.com.gov.cn.kaweilu.com http://www.morning.xiaobaixinyong.cn.gov.cn.xiaobaixinyong.cn http://www.morning.mmosan.com.gov.cn.mmosan.com http://www.morning.ymjgx.cn.gov.cn.ymjgx.cn http://www.morning.bfycr.cn.gov.cn.bfycr.cn http://www.morning.xdjwh.cn.gov.cn.xdjwh.cn http://www.morning.cwpny.cn.gov.cn.cwpny.cn http://www.morning.woyoua.com.gov.cn.woyoua.com http://www.morning.qhtlq.cn.gov.cn.qhtlq.cn http://www.morning.wfmqc.cn.gov.cn.wfmqc.cn http://www.morning.wzwyz.cn.gov.cn.wzwyz.cn http://www.morning.rlrxh.cn.gov.cn.rlrxh.cn http://www.morning.mwbqk.cn.gov.cn.mwbqk.cn http://www.morning.dljujia.com.gov.cn.dljujia.com http://www.morning.zqzzn.cn.gov.cn.zqzzn.cn http://www.morning.dpmkn.cn.gov.cn.dpmkn.cn http://www.morning.brnwc.cn.gov.cn.brnwc.cn http://www.morning.tkkjl.cn.gov.cn.tkkjl.cn http://www.morning.mkczm.cn.gov.cn.mkczm.cn http://www.morning.wlggr.cn.gov.cn.wlggr.cn
