leetcode 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串-耗时96内存94

Problem: 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

耗时96%，内存94%，用到了位运算的，固定长度是k，所以共有从0～2 k − 1 2^{k-1}2k−1共2 k 2^{k}2k个数字，若以s的长度一定>large，稍稍放宽一点就是n不能小于large*2

使用滚动计算出长度为k的子串代表的十进制数字num，考虑到长度固定是k，所以需要将最高位的第k位置0然后右移一位加上s[i]-‘0’，large = (((1<<k) - 1) >> 1);

当k=3时，(1<<k)=8(1000)，(1<<k) - 1)=7(111), (((1<<k) - 1) >> 1)=3(011)，此时最高位第3位刚好是0其他低位都是1

此时num &= large;刚好将最高位第k位的数字置0，其他低位保持不变

num = (num << 1) + (s[i]-‘0’);就是右移一位然后加上(s[i]-‘0’)

只需要用状态数组标记，最后检查0～2 k − 1 2^{k-1}2k−1共2 k 2^{k}2k个数的状态是否都是true也就是都出现过即可

Code

class Solution { public: bool hasAllCodes(string s, int k) { int len = pow(2, k), num = 0, n = s.size(); int large = (((1<<k) - 1) >> 1); if(n < large * 2) return false; if(k==1) { if(s.find('0')!=string::npos && s.find('1')!=string::npos) return true; else return false; } vector<bool> status(len, false); for(int i = 0; i < k; i++) { num = (num << 1) + (s[i]-'0'); } status[num] = true; for(int i = k; i < n; i++) { num &= large; num = (num << 1) + (s[i]-'0'); status[num] = true; } for(int i = 0; i < len; i++) { if(status[i]==false) return false; } return true; } };