google onsite 2/29

楼主是在moutain view面的吗？

Czon 发表于 2016-3-2 01:26
楼主麻烦问一下第二题存了index以后怎么处理

https://leetcode.com/problems/lo ... istinct-characters/

singledog2016 发表于 2016-3-21 07:08
楼主是在moutain view面的吗？

是的，不过不是main campus,是一个building名字是CL开头的区域，离main campus几迈的距离吧

strobogrammatic number那个follow up可以把数字都生成出来然后一个个数吗？

第二题follow up hashmap还是可以存occurence吧，

1. public class LongestSubstringWithAtMostKDistinctCharactersStream {
   
2. 
   
3.         static class StreamReader {
   
4.                 int pos = 0;
   
5.                 String str;
   
6. 
   
7.                 public StreamReader(String str) {
   
8.                         this.str = str;
   
9.                 }
   
10. 
    
11.                 char next() {// return next character
    
12.                         return str.charAt(pos++);
    
13.                 }
    
14. 
    
15.                 boolean hasNext() {
    
16.                         return pos < str.length();
    
17.                 }
    
18.         }
    
19. 
    
20.         public static String lengthOfLongestSubstringKDistinct(StreamReader s, int k) {
    
21.                 if (s == null || !s.hasNext()) {
    
22.                         return "";
    
23.                 }
    
24.                 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    
25.                 int max = 0;
    
26.                 StringBuilder sb = new StringBuilder();
    
27.                 String res = "";
    
28.                 while (s.hasNext()) {
    
29.                         char c = s.next();
    
30.                         sb.append(c);
    
31.                         if (!map.containsKey(c)) {
    
32.                                 map.put(c, 1);
    
33.                                 while (sb.length() > 0 && map.size() > k) {
    
34.                                         char ch = sb.charAt(0);
    
35.                                         sb.deleteCharAt(0);
    
36.                                         map.put(ch, map.get(ch) - 1);
    
37.                                         if (map.get(ch) == 0) {
    
38.                                                 map.remove(ch);
    
39.                                         }
    
40.                                 }
    
41.                         } else {
    
42.                                 map.put(c, map.get(c) + 1);
    
43.                         }
    
44.                         if (sb.length() > max) {
    
45.                                 max = sb.length();
    
46.                                 res = sb.toString();
    
47.                         }
    
48.                 }
    
49. 
    
50.                 return res;
    
51.         }
    
52.        
    
53.         public static void main(String[] args) {
    
54.                 StreamReader sr = new StreamReader("ababcbcbaaabbdef");
    
55.                 System.out.println(lengthOfLongestSubstringKDistinct(sr, 2));
    
56.                 StreamReader sr1 = new StreamReader("ababc");
    
57.                 System.out.println(lengthOfLongestSubstringKDistinct(sr1, 2));
    
58.                
    
59.         }
    
60. }
    

复制代码

补充内容 (2016-3-26 05:00):
用一个stringbuilder存下substring, 然后用deleteCharAt(0)进行移动

bobzhang2004 发表于 2016-3-26 04:59
第二题follow up hashmap还是可以存occurence吧，

follow up的时候LZ一开始是说拿stringbuilder存一下临时的string,面试官说如果string里面出现的字符种类很少但个数很多，比如ababbabababababba这样，一直只有a和b出现，但是字符种类就只有两个，那么临时的string就很长，因为follow up说的就是很长很长的string,要求的返回值也只是两个index,面试官觉得这样空间消耗太大，让我优化，于是才说了后面的解法

hzyslddm 发表于 2016-3-28 06:13
follow up的时候LZ一开始是说拿stringbuilder存一下临时的string,面试官说如果string里面出现的字符种类 ...

楼主那个最长假期问题的递推式没看懂，是不是有typo,能再解释一下吗？谢谢！

singledog2016 发表于 2016-3-28 09:09
楼主那个最长假期问题的递推式没看懂，是不是有typo,能再解释一下吗？谢谢！

回复错了，请无视

第四题如果题意有且只有一个不同的意思是A中的一个字母被原位替换的话变成B，这题是可以做到O(n^2)的
一个O(n^3)的解法是这样：

1. 找到s[i] != s[j]的pair (i < j)
2. 我们将s[i]和s[j]视作A和B中那个不同字母，从i和j分别向左右扩展，例如s[i-1]==s[j-1]就可以向左扩展
3. 最后我们可以找到以i,j为不同的长pair，[i-x, i+y] 和[j-x, j+y]，将总数增加 ans += y + x + 1;
4. return ans

这个方法可以进一步优化为O(n^2)

补充内容 (2016-5-31 08:57):
错了，应该是，ans += (y + 1) * (x + 1);
乘法原理

补充内容 (2016-5-31 08:59):
打不出来[~i~]前面那些s后面都有个i

dietpepsi 发表于 2016-5-31 08:55
第四题如果题意有且只有一个不同的意思是A中的一个字母被原位替换的话变成B，这题是可以做到O(n^2)的
一个 ...

很巧妙，怎么优化成 O（n^2) 呢？我感觉可以pro-process 一下, 拿到一个(i, j)和（x,y）的二维dp array

补充内容 (2016-7-31 11:43):
为啥不能直接编辑，只好补充了。。。

O（n^2) 的一种优化思路是：第一层循环针对 i， j之间的差值从1 到 len － 1， 这样的好处是不需要i，j每次都加1，而是可以从每次s［i ＋ y］ ！＝ s［j ＋ y］ 地方开始