Google 2/25 onsite面经

写了下第二轮的代码

1. public class StringEncodeAndDecode {
   
2.        
   
3.         public static void main(String[] args) {
   
4.                 System.out.println(encodeForQ1("abbbbbbbbbbbbbc"));
   
5.                 String enStr = encodeFollowUp("a5xbc");
   
6.                 System.out.println(enStr);
   
7.                 System.out.println(decodeFollowUp(enStr));
   
8.         }
   
9.        
   
10.         public static String encodeForQ1(String str) {
    
11.                 if (str == null || str.length() == 0) {
    
12.                         return "";
    
13.                 }
    
14.                 int i = 0;
    
15.                 StringBuilder sb = new StringBuilder();
    
16.                 while (i < str.length()) {
    
17.                         int j = i + 1;
    
18.                         while (j < str.length() && str.charAt(j) == str.charAt(i)) {
    
19.                                 j++;
    
20.                         }
    
21.                         int diff = j - i;
    
22.                         String s = String.valueOf(diff) + "x"+ str.charAt(i);
    
23.                         if (s.length() < diff) {
    
24.                                 sb.append(s);
    
25.                         } else {
    
26.                                 sb.append(str.substring(i, j));
    
27.                         }
    
28.                         i = j;
    
29.                 }
    
30.                
    
31.                 return sb.toString();
    
32.         }
    
33.        
    
34.         public static String encodeFollowUp(String str) {
    
35.                 if (str == null || str.length() == 0) {
    
36.                         return "";
    
37.                 }
    
38.                 int i = 0;
    
39.                
    
40.                 StringBuilder sb = new StringBuilder();
    
41.                 while (i < str.length()) {
    
42.                         char curChar = str.charAt(i);
    
43.                         int j = i + 1;
    
44.                         while (j < str.length() && str.charAt(j) == curChar) {
    
45.                                 j++;
    
46.                         }
    
47.                         int diff = j - i;
    
48.                         String s = String.valueOf(diff) + "x"+ curChar;
    
49.                         if (s.length() < diff || curChar == 'x' || Character.isDigit(curChar)) {
    
50.                                 sb.append(s);
    
51.                         } else {
    
52.                                 sb.append(str.substring(i, j));
    
53.                         }
    
54.                         i = j;
    
55.                 }
    
56.                
    
57.                 return sb.toString();
    
58.         }
    
59.        
    
60.         // a1x51xxbc
    
61.         public static String decodeFollowUp(String str) {
    
62.                 if (str == null || str.length() == 0) {
    
63.                         return "";
    
64.                 }
    
65.                 int i = 0;
    
66.                 StringBuilder sb = new StringBuilder();
    
67.                 while (i < str.length()) {
    
68.                         int index = str.indexOf('x', i);
    
69.                         if (index == -1) {
    
70.                                 sb.append(str.substring(i));
    
71.                                 break;
    
72.                         } else {
    
73.                                 int j = index - 1;
    
74.                                 while (j >= i && Character.isDigit(str.charAt(j))) {
    
75.                                         j--;
    
76.                                 }
    
77.                                 if (j >= i) {
    
78.                                         sb.append(str.substring(i, j + 1));
    
79.                                 }
    
80.                                 int count = Integer.valueOf(str.substring(j + 1, index));
    
81.                                 for (int k = 0; k < count; k++) {
    
82.                                         sb.append(str.charAt(index + 1));
    
83.                                 }
    
84.                                 i = index + 2;
    
85.                         }
    
86.                 }
    
87.                
    
88.                 return sb.toString();
    
89.         }
    
90.        
    
91. }
    

复制代码

请问楼主送HC了吗，同一天面的，完全没消息

ninacc 发表于 2016-3-4 13:30
请问楼主送HC了吗，同一天面的，完全没消息

我当晚就收到进hc的邮件了。
But， 你虽没有好消息，也没有坏消息啊! 这都过去一周了，我隐隐觉得你比我希望更大，应该是strongly recommended秒杀型的？

问一下哈，最后一轮的follow up 不用 union find可不可以？
每次把1改0时候看看这个0上下左右有没有0，没有就直接return false？（第一个0额外处理下）

william_gong 发表于 2016-3-4 22:50
问一下哈，最后一轮的follow up 不用 union find可不可以？
每次把1改0时候看看这个0上下左右有没有0，没 ...

那如果有0呢

panlong222 发表于 2016-3-4 23:48
那如果有0呢

有0就返回true吧？

william_gong 发表于 2016-3-5 00:02
有0就返回true吧？

你第一步左上角放个0， 第二步右下角放个0，第三步左上角0的旁边放个0， 然后你返回true了？

panlong222 发表于 2016-3-5 00:06
你第一步左上角放个0， 第二步右下角放个0，第三步左上角0的旁边放个0， 然后你返回true了？

第二步那里不就已经false了？

william_gong 发表于 2016-3-5 02:29
第二步那里不就已经false了？

第一步true 第二步false 第三步false
而你的算法第三步是true， 懂了伐？

panlong222 发表于 2016-3-4 09:24
我当晚就收到进hc的邮件了。
But， 你虽没有好消息，也没有坏消息啊! 这都过去一周了，我隐隐觉得你比我 ...

刚才忍不住问HR,说周一打电话，也不说送HC了没，觉得不妙了。。。觉得楼主面的好，good luck!