Problem: 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串耗时96%内存94%用到了位运算的固定长度是k所以共有从02 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 (((1k) - 1) 1);当k3时(1k)8(1000)(1k) - 1)7(111), (((1k) - 1) 1)3(011)此时最高位第3位刚好是0其他低位都是1此时num large;刚好将最高位第k位的数字置0其他低位保持不变num (num 1) (s[i]-‘0’);就是右移一位然后加上(s[i]-‘0’)只需要用状态数组标记最后检查02 k − 1 2^{k-1}2k−1共2 k 2^{k}2k个数的状态是否都是true也就是都出现过即可Codeclass Solution { public: bool hasAllCodes(string s, int k) { int len pow(2, k), num 0, n s.size(); int large (((1k) - 1) 1); if(n large * 2) return false; if(k1) { if(s.find(0)!string::npos s.find(1)!string::npos) return true; else return false; } vectorbool 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; } };