狗家电面跪经

电面， 感觉是白人小哥。  给一个 字符串, 只包含 1 和 0，  比如 “10010111101”，  另外给一个数字 k. 比如 k = 2. 我们知道两位bit  可以组成的数 有 "00" ,&

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

， 感觉他还是不满意。 第二天hr 通知拒了，  哎。 还是自己刷题太少了， 发个面经 攒攒人品吧。

用长度为k的滑动窗口找，set里最后有2^k个就全部找到了。这样的思路👀行不行？

可以fail fast一些情况，比如长度为n的字串，最多有n-k+1中可能长度为k的子串，如果2^k > n - k + 1，直接可以fail掉

试着写了下。

1. boolean valid(String s, int k) {
   
2.         int total = 1 << k;
   
3.         if (s.length() < total + k - 1) return false;
   
4. 
   
5.         HashSet<Integer> set = new HashSet<>();
   
6. 
   
7.         int mask = 0;
   
8.         for (int j = 0; j < k; j++) {
   
9.             mask <<= 1;
   
10.             mask |= 1;
    
11.         }
    
12. 
    
13.         int n = 0;
    
14.         int i;
    
15.         for (i = 0; i < k; i++) {
    
16.             n = n << 1;
    
17.             n |= s.charAt(i) - '0';
    
18.         }
    
19.         set.add(n);
    
20.         for (; i < s.length(); i++) {
    
21.             n = n << 1;
    
22.             n |= s.charAt(i) - '0';
    
23.             n &= mask;
    
24.             set.add(n);
    
25.         }
    
26.         return set.size() == total;
    
27.     }

复制代码

直观想法扫一遍，用left shift 和mod 或bitwise and 维护一个k-bit 数字，每个数字扔进set，看最后有没有2^k个，时间O(n) 空间O(2^k)

我去。。。。蠡口1023最新一题， 你上周做contest的话就有了

没关系 再努力

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

kaipeng21 发表于 2019-3-30 06:53
不太一样吧，这题给的是”00”, “01”, “10”, “11” ，1023要的是”0”, “1”, “10”, ...，而且这 ...

额。。。如果实在要说不一样的话，就是少一些可能性吧，本质差不多