Quora OA 面经

a289206397 发表于 2019-9-22 11:26
楼主啊，第四题既然只有0和1的话，把0和1出现的次数统计一下，找到min的那个乘以2不就是可能得最长值么

抱歉我没有太懂你的思路，我寻思子串要连续的话，统计的时候是存dp（i,j）么？

weicfd 发表于 2019-9-22 12:09
抱歉我没有太懂你的思路，我寻思子串要连续的话，统计的时候是存dp（i,j）么？

1. int MaxSubStr(string str){
   
2.     int len = str.length();
   
3.     int* dp = new int[len+1];
   
4.     //dp下标从1开始
   
5.     dp[1] = (str[0] - '0') == 1?1:-1;
   
6.     for(int i = 2;i <= len;i++){
   
7.         dp[i] = (str[i-1] - '0') == 1?1:-1;
   
8.         dp[i] += dp[i-1];
   
9.     }
   
10.     //统计最大01字串
    
11.     int start = 0,end = 0,max = 0,begin;
    
12.     map<int,int> m;
    
13.     for(int i = 1;i <= len;i++){
    
14.         // 不同dp值原始起点
    
15.         begin = m[dp[i]];
    
16.         if(begin == 0 && dp[i] != 0){
    
17.             m[dp[i]] = i;
    
18.         }
    
19.         else{
    
20.             //更新最大子串
    
21.             if(i - begin > max){
    
22.                 max = i - begin;
    
23.                 start = begin;
    
24.                 end = i;
    
25.             }
    
26.         }
    
27.     }
    
28.     return str.substr(start,max).length();
    
29. }
    

复制代码

自己写了个O(n * n）的[/i][/i][/i][/i][/i]

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

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

楼主请问是内推还是海投？

Airone 发表于 2019/09/22 12:39:09
楼主请问是内推还是海投？

学校招聘会上海投的

楼主第四题你举的例子最长应该还是6吧，index1到index6有三个1和三个0

最后一题如果是用O（N^2）的话不是简单的计算PREFIX SUM就行了吗。。。何必DP呢。。。

preSum  可以优化成O（n）来做

a289206397 发表于 2019-9-22 11:26
楼主啊，第四题既然只有0和1的话，把0和1出现的次数统计一下，找到min的那个乘以2不就是可能得最长值么

不太对吧 eg: 1100000011

Apollo_tong 发表于 2019-9-26 07:40
不太对吧 eg: 1100000011

哈哈，一开始我这个想法确实不对，应该DP的。