楼主: hyperspace
跳转到指定楼层
上一主题 下一主题
收起左侧

gg全套

🔗
regist1234 2016-9-27 13:57:01 | 只看该作者
全局:
店面第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第三题,不是店面
回复

使用道具 举报

🔗
liurudahai 2016-10-2 14:46:21 | 只看该作者
全局:
hyperspace 发表于 2016-9-15 04:33
我的方法是有一个boolean[4]。分别代表上下左右有没有口子。

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

使用道具 举报

🔗
liurudahai 2016-10-2 14:52:44 | 只看该作者
全局:
hyperspace 发表于 2016-9-15 05:12
嗯第二题是heap
第三题就存每行的和 然后edge case就算的时候判断一下。。

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

使用道具 举报

🔗
liurudahai 2016-10-2 14:55:26 | 只看该作者
全局:
shuiguo 发表于 2016-9-15 13:48
为什么是O(n)?

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

使用道具 举报

🔗
liurudahai 2016-10-2 14:57:35 | 只看该作者
全局:
jy_121 发表于 2016-9-16 02:35
嗯嗯, 我用的递归是从两头到中间,我只是有点不确定时间复杂度是不是O(n).

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

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

使用道具 举报

🔗
liurudahai 2016-10-2 15:00:54 | 只看该作者
全局:
第三题突然发现是leetcode原题
回复

使用道具 举报

🔗
sunnyroom 2016-10-9 05:50:54 | 只看该作者
全局:
readman 发表于 2016-9-15 04:15
是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构

你好,能详细讲讲怎么union find吗?
回复

使用道具 举报

🔗
printf_ll 2016-10-10 01:22:58 | 只看该作者
全局:
电面贴个java的实现,跑了几个test case都通过了,用循环实现
  1. public class Chunk {

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

  39. }
复制代码

补充内容 (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))就行
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表