G onsite 2015/02/09

tianyangche 发表于 2015-2-11 06:46
我刚开始想错了，后来经他提示想出了解法。用分治法来做。for循环从0开始，每次分成左右两边，左边的结果 ...

楼主，能不能麻烦再说清楚点？
二分的话是类似找partition line么？ 1 | 2 3 4,  1 2 | 3 4, 1 2 3 | 4????  然后对left right 分别做递归？

水逼一枚 发表于 2015-2-18 08:35
楼主，能不能麻烦再说清楚点？
二分的话是类似找partition line么？ 1 | 2 3 4,  1 2 | 3 4, 1 2 3 | 4? ...

我觉得lz应该是这个意思，枚举分割点

水逼一枚 发表于 2015-2-18 08:35
楼主，能不能麻烦再说清楚点？
二分的话是类似找partition line么？ 1 | 2 3 4,  1 2 | 3 4, 1 2 3 | 4? ...

yeah, you are right.

中庸人90 发表于 2015-2-18 08:17
求指教怎么构造所有有效的逆波兰式？

这个构造规则就是只要操作符的数目小于当前操作数的数目。比如 (3 4)，你只能往它俩后面插一个二元操作符

为什么我觉得最后一个是最难的。请问lz 怎么解 能否 站内信我一下？

CrossTheWall 发表于 2015-2-19 11:59
这个构造规则就是只要操作符的数目小于当前操作数的数目。比如 (3 4)，你只能往它俩后面插一个二元操作符 ...

多谢！后来想出来了，觉得跟leetcode 的 那道generate parentheses很像。

中庸人90 发表于 2015-2-19 14:57
多谢！后来想出来了，觉得跟leetcode 的 那道generate parentheses很像。

是的，但是代码实现比那个要难。因为在某个数的后面，你可以选择随便插一个操作符，也可以选择什么也不插入

第一题貌似用递归分左右两边就替代了括号的功能了哈 这样可以嘛？
def genNums(A):
    if not A: return A
    if len(A)==1: return  [A[0]]
    res = []
    for i in range(1, len(A)-1):
        left = genNums(A[:i])
        right = genNums(A[i:])
        for x in left:
                for y in right:
                    res.extend([x+y, x-y, x*y, x/y])
    return res

def getNum(target, A):
      return target in genNums(A)

tianyangche 发表于 2015-2-10 05:51
不知道何为并查集~小弟把这道题看作是一道图题，每个人建一个Person类，里面有他的id，还有一个list，用 ...

实现了一遍

1. graph = {1:[2],2:[1],3:[4],4:[3],4:[5],5:[4]}
   
2. def find(graph):
   
3.         visit = {}
   
4.         res = []
   
5.         for key in graph.keys():
   
6.                 visit[key] = False
   
7.         for key in graph.keys():
   
8.                 if visit[key] == True:
   
9.                         continue
   
10.                 que = [key]
    
11.                 temp = []
    
12.                 while que:
    
13.                         cur = que.pop()
    
14.                         temp.append(cur)
    
15.                         visit[cur] = True
    
16.                         for item in graph[cur]:
    
17.                                 if not visit[item]:
    
18.                                         que.append(item)
    
19.                 res.append(temp)
    
20. 
    
21.         return  res
    
22. 
    
23. print find(graph)

复制代码