Google OA 试题讨论

taobingxue 发表于 2016-8-20 04:36
大O的定义就是忽略常数的…… 所有时间复杂度都是只管数量级的？

a

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

Mr.111 发表于 2016-8-20 03:33
我觉得你的方法没有达到空间复杂度O(N)的要求。最后是要返回一个总和的INT，过程中如果重复储存路径那不 ...

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

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)了吧

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

复制代码

这个OA不是不挂人么....

第二题stack。再说OA不会挂吧

gaocan1992 发表于 2016-8-21 14:01
第二题stack。再说OA不会挂吧

OA 不挂人是什么意思啊

wujingzhishui 发表于 2016-8-20 23:15
OA 不挂人是什么意思啊

据说google OA做的好坏都可以

stellari 发表于 2016-8-21 13:07
O(N)的意思不是说“最多不会超过N条（常数时间的）指令”，而是说"不会超过kN条指令"，其中k为任意大的常 ...

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

zj45499 发表于 2016-8-21 13:13
这个OA不是不挂人么....

真的吗？那后续结果是什么？