fb家新鲜电面面经

youto 发表于 2016-10-29 09:31
请问楼主，第二题是说找一个substring是alphabet字符串的anagram形式？最短的话不就是和alphabet字符一样长 ...

最好的情况是每个字母在substring里只出现一次，而且没有其他字母，但是题目的意思是找一个包括alphabet里面所有字母的最短字符串，这个字符串不一定是anagram.

oxfordjin11 发表于 2016-10-30 02:25
最好的情况是每个字母在substring里只出现一次，而且没有其他字母，但是题目的意思是找一个包括alphabet ...

那就是说minimum substring window分两种情况，如果有substring只包含了alphbet的，那就是结果；没有的话，就是lc上的那种做法，找到最短的substring能够包含alphbet，但是可能还有其他字符，比如alphbet是abc，但是结果是bnac

1. Move zeros 我就假设是要求把数组中zero in place移到末尾。对于是否要求非零元素的相对位置不变（stable vs unstable），就是时间O(2n) vs O(n)的区别。关键是当前遇到0时，是和后面第一个非零元素交换(O(2n))还是最后一个非零元素交换(O(n)):

1. // stable O(2n)
   
2. void moveZerosToEnd1(vector<int>& a) {
   
3.   int n = a.size(); if (n < 2) return;
   
4.   int i = 0; // first index of zero value
   
5.   while (i < n) {
   
6.     if (a[i] != 0) i++;
   
7.     else {
   
8.       int j = i+1; // first index of non-zero value after i
   
9.       while (j < n && a[j] == 0) j++;
   
10.       if (j == n) return;
    
11.       swap(a[i], a[j]);
    
12.       i = j;
    
13.     }
    
14.   }
    
15. }
    
16. 
    
17. // unstable O(n)
    
18. void moveZerosToEnd2(vector<int>& a) {
    
19.   int n = a.size(); if (n < 2) return;
    
20.   int i = 0; // first index of zero value
    
21.   int j = n-1; // last index of non-zero value
    
22.   while (i < n) {
    
23.     if (a[i] == 0) {
    
24.       while (j > i && a[j] == 0) j--;
    
25.       if (j == i) return;
    
26.       swap(a[i], a[j]);
    
27.     }
    
28.     i++;
    
29.   }
    
30. }

复制代码

2.minimum substring window. 这个题和求longest substr with at most k distinct chars类似。我用two pointers i, j 指向substring的头尾，让j向前进，同时保持substring字符频率统计，直到当所有要求字符都出现时记录当前长度及substring。然后移动i, 同时减小字符频率统计直到有一个要求字符被丢掉时停止，再前进j, 不断重复。这个题我觉得思路不难，但实现起来不容易写。（真正要是在interview时我写得还是慢。。。）
因为给定的alphabet是个string, 我需要转化成unordered_set<char> (hashset)提高时间效率。整体i, j至多扫描string一遍O(N) + 转化alphabet为hashset的O(M)时间。
大家还有什么办法？

1. string minSubstr(string& s, string& alphabet) {
   
2.   int n = s.length(), m = alphabet.size();
   
3.   string res; // result to hold required min substring
   
4.   if (n < m || n == 0) return res;
   
5.   int i = 0, j = -1, minlen = n;
   
6.   unordered_map<char, int> freq; // char frequency of substring
   
7.   unordered_set<char> chars; // all chars in alphabet
   
8.   for (char& c:alphabet) chars.insert(c); // O(m)
   
9.   
   
10.   while (++j < n) { // O(n)
    
11.     // if a new char in alphabet encountered
    
12.     if (chars.count(s[j]) && !freq.count(s[j])) m--;
    
13.     freq[s[j]]++;
    
14.    
    
15.     // have all chars in alphabet
    
16.     while (m == 0) {
    
17.       if (j-i+1 < minlen) { // better substring found
    
18.         minlen = j-i+1; res = s.substr(i, j-i+1);  
    
19.       }
    
20.       i++; // drop first char in substring
    
21.       if (--freq[s[i]] == 0) {
    
22.         freq.erase(s[i]);
    
23.         if (chars.count(s[i])) m++; // miss a char in alphabet
    
24.       }
    
25.     }
    
26.   }
    
27.   return res;
    
28. }

复制代码

补充内容 (2016-10-30 05:41):
若根本找不到要求的substring我的算法就返回空string