gg全套

店面第3题，我有一个time complexity=O(n), space complexity=O(n^2)的方法。
称原矩阵为M。

- 初始化（O(n^2)复杂度）:
再开两个m*n的矩阵L and R，分别记录原矩阵元素同行左侧数字的和 以及 同行右侧数字的和。
开一个大小为m的数组A，记录每一行的和。

- update(i,j,value)
更新M[i][j] ---- O(1)
更新A[i]     ---- O(1)
更新L[a][j] for a>i   ----- O(n)
更新R[a][j] for a<i   ----- O(n)

- sum(x1,y1,x2,y2)
计算第i行y1与y2之间的和，without loss of generality suppose y1<=y2，和为A[i]-R[i][y2]-L[i][y1]   ----- O(1)
一共需要计算(|x2-x1|)行  ---- |x2-x1| * O(1) = O (n)
对这些和求总和  ----- O(n)



补充内容 (2016-9-27 14:08):
不需要R矩阵，只需要维护A,M和L就可以了，因为R[i][j] == A[i]-L[i][j]-M[i][j]

补充内容 (2016-9-27 14:09):
哦是onsite第三题，不是店面

hyperspace 发表于 2016-9-15 04:33
我的方法是有一个boolean[4]。分别代表上下左右有没有口子。

然后从其中一个管子开始，然后遍历其他管子DFS递归么？每次看有没有管子能接上，能接上再继续?

hyperspace 发表于 2016-9-15 05:12
嗯第二题是heap
第三题就存每行的和 然后edge case就算的时候判断一下。。

只存每行和SUM O（N）是怎么做到的
第二题如果用HEAP，就无所谓SET特别大了吧，反正HEAP就是K的大小，一个一个点读入就可以了

shuiguo 发表于 2016-9-15 13:48
为什么是O（n）？

从两边往中间遍历，如果看到一样的就截开，一直都是不一样的中间就作为一整块输出

jy_121 发表于 2016-9-16 02:35
嗯嗯， 我用的递归是从两头到中间，我只是有点不确定时间复杂度是不是O(n).

请问为啥要递归呢，直接遍历不就行了吗？比如teammate，从两边遍历t和e不一样，然后接下来，te和te一样了，截出来，a和a一样，截出来，m和m一样，截出来

如果是teabcdefgte的话，一样把te和te截出来，但是中间没有一一样的了，两边指针相遇的时候直接把中间作为一整块输出就是te|abcdefg|te

第三题突然发现是leetcode原题

readman 发表于 2016-9-15 04:15
是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构

你好，能详细讲讲怎么union find吗？

电面贴个java的实现，跑了几个test case都通过了，用循环实现

1. public class Chunk {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 // TODO Auto-generated method stub
   
5.                 Chunk c=new Chunk();
   
6.                 System.out.println(c.findPali("teammate"));
   
7.         }
   
8.        
   
9.         private int findPali(String str){
   
10.                 int result=0;
    
11.                 if(str.length()==0) return 0;
    
12.                 int start=0,end=str.length()-1;
    
13.                 while(start<end){
    
14.                         if(str.charAt(start)==str.charAt(end)){
    
15.                                 result+=2;
    
16.                                 start++;end--;
    
17.                         }else{
    
18.                                 int p=start,q=end;
    
19.                                 boolean find=false;
    
20.                                 while(q>start&&(end-q+1)*2<=str.length()){
    
21.                                         if(str.charAt(q)==str.charAt(start)&&str.substring(start,start+end-q+1).equals(str.substring(q,end+1))){                                               
    
22.                                                         result+=2;
    
23.                                                         start=start+end-q+2;
    
24.                                                         end=q-1;
    
25.                                                         find=true;
    
26.                                                         break;
    
27.                                                
    
28.                                         }else{
    
29.                                                 q--;
    
30.                                         }
    
31.                                 }
    
32.                                 if(!find){
    
33.                                         result+=1;
    
34.                                         return result;
    
35.                                 }
    
36.                         }
    
37.                 }
    
38.                 return result;
    
39.         }
    
40. 
    
41. }

复制代码

补充内容 (2016-10-10 01:24):
if(str.charAt(q)==str.charAt(start)&&str.substring(start,start+end-q+1).equals(str.substring(q,end+1)))
这条有点重复了，只要判断str.substring(start,start+end-q+1).equals(str.substring(q,end+1))就行