Microsoft on-campus interview30分钟

609064231 发表于 2016-10-17 05:58
你这只考虑了counter是个位数啊
counter大于等于10呢

你自己不能加几行代码？

1. public class microsoft_practice_string_compression {
   
2.        
   
3.        
   
4.         public static void compression(char[] ch)
   
5.         {
   
6.                 int counter =1;
   
7.                 int j =0;
   
8. 
   
9.                 for(int i =0;i < ch.length;i++)
   
10.                 {
    
11.                                 while((i+1<ch.length) && ch[i]==ch[i+1])
    
12.                                 {
    
13.                                         counter++;
    
14.                                         i++;
    
15.                                 }
    
16.                                 ch[j++] = ch[i];
    
17.                                 if(counter<10)
    
18.                                 {
    
19.                                         ch[j++] = (char) (counter+'0');
    
20. 
    
21.                                 }
    
22.                                 else
    
23.                                 {
    
24.                                         int temp =0;
    
25.                                         int start = j;
    
26.                                         while(counter>0)
    
27.                                         {
    
28.                                                 temp = counter%10;
    
29.                                                 ch[j++] =(char) (temp+'0');
    
30.                                                 counter= counter/10;
    
31.                                         }
    
32.                                         int end = j-1;
    
33.                                         while(start < end)
    
34.                                         {
    
35.                                                 char tempChar = ch[start];
    
36.                                                 ch[start] = ch[end];
    
37.                                                 ch[end] = tempChar;
    
38.                                                 start++;
    
39.                                                 end--;
    
40.                                         }
    
41.                                 }
    
42.                                 counter=1;
    
43. 
    
44.                 }
    
45.                 while(j!=ch.length)
    
46.                 {
    
47.                         ch[j++] ='\0';
    
48.                 }
    
49.                 for(char c: ch)
    
50.                 {
    
51.                         System.out.println(c);
    
52.                 }
    
53.         }
    
54.         public static void main(String[] args)
    
55.         {
    
56.                 String str = "aaabbbccc";
    
57.                 char [] test = str.toCharArray();
    
58.                 String str1 = "aaaaab";
    
59.                 char[] test1 = str1.toCharArray();
    
60.                 String str2 = "aaaaba";
    
61.                 char[] test2 = str2.toCharArray();
    
62.                 String str3 = "aa";
    
63.                 char[] test3 = str3.toCharArray();
    
64.                 String str4 = "aabb";
    
65.                 char[] test4 = str4.toCharArray();
    
66.                 String str5 = "aaaaaabbbbbbbbbbbbbbbbbbbbbcccccccccccccc";
    
67.                 char[] test5 = str5.toCharArray();
    
68.                 String str6 = "hhhhhhhhhhhhhhhh";
    
69.                 char[] test6 = str6.toCharArray();
    
70.                 System.out.println("test");
    
71.                 compression(test);
    
72.                 System.out.println("test1");
    
73.                 compression(test1);
    
74.                 System.out.println("test2");
    
75.                 compression(test2);
    
76.                 System.out.println("test3");
    
77.                 compression(test3);
    
78.                 System.out.println("test4");
    
79.                 compression(test4);
    
80.                 System.out.println("test5");
    
81.                 compression(test5);
    
82.                 System.out.println("test6");
    
83.                 compression(test6);
    
84.         }
    
85. }

复制代码

xiaozhuxiaozhu 发表于 2016-10-17 06:43
你自己不能加几行代码？

请教下如果考虑输入为 abbb， abcccccc这样的话，该怎么处理呢？

skinnyman 发表于 2016-10-17 14:28
请教下如果考虑输入为 abbb， abcccccc这样的话，该怎么处理呢？

这种算是invalid的input吧？

xiaozhuxiaozhu 发表于 2016-10-17 15:15
这种算是invalid的input吧？

这两个都是valid input，只要输出不超过输入就是valid，如果是abbb，返回a1b3，如果是abcccccc，返回a1b1c6,都是valid的，你有O（n）的in place吗？

abbb 和 abccccc, abcdddddddd 这些情况，因为写入count的时候会覆盖掉后面的字母，我没有想出in-place的办法来。大家有什么想法么？

skinnyman 发表于 2016-10-18 12:30
abbb 和 abccccc, abcdddddddd 这些情况，因为写入count的时候会覆盖掉后面的字母，我没有想出in-place的办 ...

同问 觉得不能in place 这就是一个case..

skinnyman 发表于 2016-10-18 12:30
abbb 和 abccccc, abcdddddddd 这些情况，因为写入count的时候会覆盖掉后面的字母，我没有想出in-place的办 ...

哎，反正我是不太会写，网上也没找到好solution。。

这个也忒麻烦吧。我的想法是单个数的出现导致坑爹的事情发生，如开头是abcdefg的情况，用几个变量记录，如a处，能提供1位，需要2位，并记录起始位置；b处，能提供2位，需要4位。。。到能够满足的地方，也就是提供位数终于大于需要位数时，倒着数回来。正常情况也是倒着数回来。而且尾数又出现单个就不必担心，中间肯定能补上。明天我试着写写看，欢迎交流

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

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

zjhsyfz 发表于 2016-10-18 14:09
这个也忒麻烦吧。我的想法是单个数的出现导致坑爹的事情发生，如开头是abcdefg的情况，用几个变量记录，如a ...

做等大神上代码~~