bb 店面

前几天的bb电面，问了一下简历，给了一道算法题，字符串消消乐，
当有超过连续3个相同字母时，就忽略掉这个字母，比如"aaab" -

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

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

ack，把思路说了。
聊天聊得还可以（自我感觉），看面试官能不能手下留情给个onsite吧

贡献一下我的stack O(n)代码，求加米

1. import java.util.Stack;
   
2. 
   
3. public class ThreeCharDeduct {
   
4.     static String reduce(String s) {
   
5.         Stack<Character> stack = new Stack<>();
   
6.         char[] a = s.toCharArray();
   
7.         for (char c : a) {
   
8.             if (stack.size() < 2) {
   
9.                 stack.push(c);
   
10.             } else {
    
11.                 char first = stack.pop();
    
12.                 char second = stack.pop();
    
13.                 if (c == first && c ==second) {
    
14.                     continue;
    
15.                 } else {
    
16.                     stack.push(second);
    
17.                     stack.push(first);
    
18.                     stack.push(c);
    
19.                 }
    
20.             }
    
21.         }
    
22.         StringBuilder sb = new StringBuilder();
    
23.         for (char c : stack) {
    
24.             sb.append(c);
    
25.         }
    
26.         return sb.reverse().toString();
    
27.     }
    
28. 
    
29.     public static void main(String[] args) {
    
30.         System.out.println(reduce("aaab"));
    
31.         System.out.println(reduce("aabbeeeba"));
    
32.     }
    
33. }
    

复制代码

谢谢楼主。
请问一个问题：
  aaabbeeeeba -> bbeeeeba ->bbba -> a;
  aaabbeeeeba -> aaabbba -> aaaa ->""
这两种case你怎么处理的？

感觉这题是很难。

递归该怎么写啊

colin_ding 发表于 2018-9-30 09:11
谢谢楼主。
请问一个问题：
  aaabbeeeeba -> bbeeeeba ->bbba -> a;

所以是递归啊，发现不能再合并了就直接return呗

amanUSC 发表于 2018-9-30 09:13
递归该怎么写啊

1. String solve(String s) {
   
2.     if (noNeedToCompress(s)) return s;
   
3.     // do the compress here
   
4.    
   
5.     return solve(ss);
   
6. }
   
7. 大概这样，直接stack写最优解比较好
   
8. 
   
9. boolean noNeedToCompress(String s) {
   
10.    
    
11. }

复制代码

我想到的是两个stack，一个 存字母，一个存对应的个数，这样的行吗

amanUSC 发表于 2018-9-30 09:20
我想到的是两个stack，一个 存字母，一个存对应的个数，这样的行吗

不用一个stack就可以，stack里最多存两个相同的

楼主的投的18还是19啊

熊猫杀很大缺积分 发表于 2018-9-30 09:25
楼主的投的18还是19啊

1919，zszs

lifefailure 发表于 2018-9-30 09:25
1919，zszs

-= =- 完蛋了, 感觉自己凉凉