google店面

刚放下电话：
1. 给一个字符串，删除其中的a，然后把b变成bb，需要inplace的做；

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

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

2015-9-22 16:24):
求大米

if (new_len > len) return; 是字符串长度不能变长，只能变小吗？

cbwcs 发表于 2015-9-23 02:19
第一题：如果新的长度变短，就从前往后填；如果变长，就从后往前填。

有问题，BCAA这种情况，虽然字符串整体变短了，但是存在局部变长的情况。如果从前往后填，初始index1,index2都是0，就会出Bug；
感觉不论从前往后，还是从后往前，都不完全正确；
建议两次遍历，第一次删除A，并计算新长度和B的数量，第二次添加B

if (new_len > len) return; 是字符串长度不能变长，只能变小吗？因为必须inplace？

1. void process(char *str, int len) {
   
2.     int cnta = 0, cntb = 0;
   
3.     for (int i=0; i<len; i++)
   
4.         if (str[i] == 'a')
   
5.             cnta++;
   
6.         else if (str[i] == 'b') cntb++;
   
7.         
   
8.     int new_len = len-cnta+cntb;
   
9.     if (new_len > len) return;
   
10. 
    
11.     for (int i=aidx,j=aidx; i<len; i++)
    
12.         if (str[i] != 'a') str[j++] = str[i];
    
13.     for (int i=len-cnta-1,j=new_len-1; i>=0; i--) {
    
14.         str[j--] = str[i];
    
15.         if (str[i] == 'b') str[j--] = str[i];
    
16.     }
    
17.     str[new_len] = '\0';
    
18.     return;
    
19. }
    
20. 
    
21. int f(int n) {
    
22.     if (n < 2) return 1;
    
23.     vector<int> dp(n+1);
    
24.     dp[0] = dp[1] = 1;
    
25.     for (int i=2; i<=n; i++) {
    
26.         dp[i] = 0;
    
27.         for (int j=0; j<n; j++)
    
28.             dp[i] += dp[j]*dp[n-1-j];
    
29.     }
    
30.     return dp[n];
    
31. }

复制代码

感谢分享 要求边打电话边写代码吗
第二题我的代码不知道对不对

1. int difftype(int n){
   
2. if(n==0) return 1;
   
3. int res=0;
   
4. for(int i=0;i<=n-1;i++){
   
5. res+=difftype(i)*difftype(n-1-i);
   
6. }
   
7. return res;
   
8. }

复制代码

重复计算很多 可以用动态规划记下计算过的值
1,3 期待大神解答

3题， 一个原因， 可能是访问的人太多，  加一个load balancer,  然后后面多加几个服务器， 用load balancer 分流到这几个服务器上

楼主牛逼 感谢分享

1. 首先计算新字符串的长度，然后从后边往前填入？（java党，只能当成字符数组了）
2. 递归结局？如果要快速一些的话，可以记录搜索过的值，但是要用额外空间

第一题：如果新的长度变短，就从前往后填；如果变长，就从后往前填。

1. def noOfBiTrees(n):
   
2.     opt = [False for i in range(0, n+1)]
   
3.     findOpt(n, opt)
   
4.     return opt[n]
   
5. def findOpt(n, opt):
   
6.     if n <=1:
   
7.         opt[n] = 1
   
8.         return 1
   
9.     if opt[n]:
   
10.         return opt[n]
    
11.     re = 0
    
12.     for i in range(0, n):
    
13.         re += noOfBiTrees(i)*noOfBiTrees(n-1-i)
    
14.     opt[n] = re
    
15.     return re
    

复制代码

DP with memorization