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

Google OA 试题讨论

🔗
 楼主| Mr.111 2016-8-20 04:42:58 | 只看该作者
全局:
taobingxue 发表于 2016-8-20 04:36
大O的定义就是忽略常数的…… 所有时间复杂度都是只管数量级的?

a

我就是想了很久很久也没想出来怎么做到O(N),然后在网上看了很多回答都不是很正确。我自己最多也就是做到了和你一样的O(2N)。这才发帖求助,其实研究了这么久也感觉不太可能完全做到O(N)。至少时间和空间复杂度里至少有1个做不到。
回复

使用道具 举报

🔗
dydcfg 2016-8-20 04:59:18 | 只看该作者
全局:
Mr.111 发表于 2016-8-20 03:33
我觉得你的方法没有达到空间复杂度O(N)的要求。最后是要返回一个总和的INT,过程中如果重复储存路径那不 ...

空间复杂度是O(N),prefixString就是一个string变量,最长就是N.
因为输入是按照层次给的,比如当前在/f1/f2文件夹下面有俩图片p1.jpg,p2.jpg那么他们都是prefixString都一样.
回复

使用道具 举报

🔗
 楼主| Mr.111 2016-8-20 05:40:32 | 只看该作者
全局:
本帖最后由 Mr.111 于 2016-8-20 10:03 编辑
dydcfg 发表于 2016-8-20 04:59
空间复杂度是O(N),prefixString就是一个string变量,最长就是N.
因为输入是按照层次给的,比如当前在/f1/f ...

我刚刚试了一下你的方法,发现有个问题。如果是下面的输入:
  1. d1
  2. _d11
  3. __d111
  4. ___p1.gif
  5. _d12
  6. __p2.gif
复制代码
那么,d12的prefix string怎么改?prefix string只有一个,那么/d1/d11/d111是p1.gif的prefix string,然后如何把这个prefix string改成/d1/d12?如果遍历这个prefix string然后改的话,那么时间复杂度应该也就不是O(N)了吧



回复

使用道具 举报

🔗
stellari 2016-8-21 13:07:57 | 只看该作者
全局:
Mr.111 发表于 2016-8-20 04:27
这个解法我想过类似的,不过我个人觉得时间复杂度应该是O(2N)。但是之前算法课上说前面一个这么小的常数 ...

O(N)的意思不是说“最多不会超过N条(常数时间的)指令”,而是说"不会超过kN条指令",其中k为任意大的常数。所以从概念上来说,恒有O(N) = O(2N) = O(3N)... = O(10000N) =...,大O记号中,N前的常数是不会改变时间复杂度的,所以一般人们也不会用O(2N)这种说法。否则,如果N前的常数有实际意义,那么任何循环都是O(3N)以上级别的,因为循环变量自加,比较循环结束条件,跳转至循环开始处都需要至少各一条指令。

你想表达的意思应该用one-pass, two-pass表述更合适些。而@taobingxue给出的做法已经是one-pass的O(N)了。写成代码大概是这个样子的(python 3):
  1. import sys;
  2. import os;

  3. imFormats = set([".jpeg", ".gif", ".png"]);
  4. retval = 0;
  5. stack = [0];

  6. i = 0;
  7. while True:
  8.         currentLine = sys.stdin.readline();   #读一行
  9.         curLevel = len(currentLine) - len(currentLine.lstrip());   # 当前深度=前面有几个空格
  10.         currentStrip = currentLine.strip();
  11.         if not currentStrip:   
  12.                 break;
  13.        
  14.         curLen = len(currentStrip);
  15.         filename, fileext = os.path.splitext(currentLine.strip());    # 取得扩展名
  16.         # 如果当前行的深度小于栈长,说明当前的栈顶存的不是当前行的父目录。
  17.         # 于是不停pop直到找到父目录位置
  18.         while (curLevel + 1 < len(stack)):      
  19.                 stack.pop();
  20.         #找到以后把当前文件的全路径长度写入栈顶。
  21.         stack.append(stack[-1]+curLen+1);
  22.                
  23.         # 如果文件是图片,那么栈顶的值就应被加入最终结果
  24.         if (fileext in imFormats):
  25.                 retval += stack[-1];
  26.                 retval %= 1000000007

  27. print(retval);
复制代码
回复

使用道具 举报

🔗
zj45499 2016-8-21 13:13:17 | 只看该作者
全局:
这个OA不是不挂人么....
回复

使用道具 举报

🔗
citynart 2016-8-21 14:01:40 | 只看该作者
全局:
第二题stack。再说OA不会挂吧
回复

使用道具 举报

🔗
wujingzhishui 2016-8-21 15:15:34 | 只看该作者
全局:
gaocan1992 发表于 2016-8-21 14:01
第二题stack。再说OA不会挂吧

OA 不挂人是什么意思啊
回复

使用道具 举报

🔗
citynart 2016-8-22 04:24:45 | 只看该作者
全局:
wujingzhishui 发表于 2016-8-20 23:15
OA 不挂人是什么意思啊

据说google OA做的好坏都可以
回复

使用道具 举报

🔗
 楼主| Mr.111 2016-8-22 11:29:12 | 只看该作者
全局:
stellari 发表于 2016-8-21 13:07
O(N)的意思不是说“最多不会超过N条(常数时间的)指令”,而是说"不会超过kN条指令",其中k为任意大的常 ...

认真查了一下之前学习算法的资料,结果和原理完全如同@stellari 大神说的。只能怪我之前的算法基础没有很牢固。最重要感谢@stellari 大神提供的代码。谢谢!
回复

使用道具 举报

🔗
 楼主| Mr.111 2016-8-22 11:30:05 | 只看该作者
全局:
本帖最后由 Mr.111 于 2016-8-22 11:32 编辑
zj45499 发表于 2016-8-21 13:13
这个OA不是不挂人么....

真的吗?那后续结果是什么?
回复

使用道具 举报

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

本版积分规则

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