狗狗家的onsite

yangzhit 发表于 2016-12-4 06:55
楼主在哪里面，我也是12/1面，在tech corner

我在building 1201。你面得咋样啊？

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

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

ychen622 发表于 2016-12-6 00:48
抱歉。m是substring里unique character的个数。

额 多谢 那这个例子里面为啥return 8? 不应该是abcde return5么？

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

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

2008 发表于 2016-12-6 02:21
这个题你没看明白，其实不容易。
'ababababcdedede' --> return 8
ab是个m=2的unique字串，重复了4次， ...

多谢解释。然而还是没看懂啊。。有原题链接么？

小A要当码农 发表于 2016-12-6 02:34
多谢解释。然而还是没看懂啊。。有原题链接么？

这题做的很繁琐，有好办法请告知
维护一个pattern，如果有match了，还要维护一个tmp match.

1. #include <string>
   
2. #include <set>
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. int eval(string &s) {
   
7.   string pattern="";
   
8.   set<char> spat;
   
9.   int count=0;
   
10.   int tmp_count=0;
    
11.   string tmp="";
    
12. 
    
13.   for(int i=0; i<s.length(); i++) {
    
14.     if(tmp!="") {
    
15.       if(pattern[tmp.length()]==s[i]) {
    
16.         tmp+=s[i];
    
17.         if(pattern.length()==tmp.length()) {
    
18.           tmp_count++;
    
19.           tmp="";
    
20.           if(tmp_count*pattern.length()>count) {
    
21.             count=tmp_count*pattern.length();
    
22.           }
    
23.         }
    
24.       } else {
    
25.         set<char> stmp;
    
26.         int j=i;
    
27.         for(; j>=i-tmp.length(); j--) {
    
28.           if(stmp.count(s[j])) break;
    
29.           else stmp.insert(s[j]);
    
30.         }
    
31.         spat=stmp;
    
32.         pattern=s.substr(j, i-j);
    
33.         tmp_count=1;
    
34.       }
    
35.     } else {
    
36.       if(spat.count(s[i])) {
    
37.         if(s[i]==pattern[0]) {
    
38.           tmp=s[i];
    
39.           if(tmp_count==0) tmp_count=1;
    
40.         } else {
    
41.           int j=i-pattern.length();
    
42.           for(; s[j]!=s[i]; j++) {
    
43.             spat.erase(s[j]);
    
44.           }
    
45.           pattern=s.substr(j, i-j);
    
46.           tmp=s[j];
    
47.           tmp_count=1;
    
48.          }
    
49.       } else {
    
50.         spat.insert(s[i]);
    
51.         pattern+=s[i];
    
52.         tmp_count=1;
    
53.       }
    
54.     }
    
55.   }
    
56.   return count;
    
57. }
    
58. 
    
59. int main() {
    
60.   string s="ababababababcdeabcdeabcdedede";
    
61.   cout<<s<<endl;
    
62.   cout<<eval(s)<<endl;
    
63.   return 0;
    
64. }
    

复制代码

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

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