9.26新鲜热乎的狗狗昂塞

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

DylanZhang 发表于 2018-10-5 00:15
这样好像同一个数可能被sum 两次，比如 4本来是算不出来的。但是2,可以算出来，4-2 = 2（true），结果4  ...

是的，我的想法错的，感谢指正

DylanZhang 发表于 2018-10-5 00:15
这样好像同一个数可能被sum 两次，比如 4本来是算不出来的。但是2,可以算出来，4-2 = 2（true），结果4  ...

所以可以反向更新dp array先到4再到2

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

二叉树游戏，大家有思路吗

1.

1. def uniqueSubsetSum(nums):
   
2.     nums = sorted(nums)
   
3.     L = len(nums)
   
4.     sums = {0}
   
5. 
   
6. 
   
7.     def helper(start, c_sum):
   
8.         if start >= L:
   
9.             return
   
10. 
    
11.         prev = float('inf')
    
12.         for i in range(start, L):
    
13.             if nums[i] == prev:
    
14.                 continue
    
15. 
    
16.             prev = nums[i]
    
17.             c_sum += nums[i]
    
18.             sums.add(c_sum)
    
19.             helper(i + 1, c_sum)
    
20.             c_sum -= nums[i]
    
21. 
    
22.     helper(0,0)
    
23. 
    
24.     return list(sums)
    
25. 
    
26. print uniqueSubsetSum( [1,2,2])

复制代码

2.

1. # should ask boundry include or not
   
2. # refer meeting room, [url]https://leetcode.com/problems/meeting-rooms-ii/solution/[/url]
   
3. def kthUser(log, K):
   
4.     starts = map(lambda x: [x[1], x[0]], log)
   
5.     ends = map(lambda x: [x[2], x[0]], log)
   
6. 
   
7.     starts = sorted(starts)
   
8.     ends = sorted(ends)
   
9. 
   
10.     i = j = 0
    
11.     activate_meetings = 0
    
12.     in_room = set()
    
13.     result = set()
    
14.     escaped = 0
    
15.     while i < len(starts) and j < len(ends):
    
16.         # print 'in the room', in_room
    
17.         # print 'escaped', escaped
    
18.         # print 'activate', activate_meetings
    
19.         if starts[i][0] < ends[j][0]:
    
20.             activate_meetings += 1
    
21.             #print 'adding to room', starts[i][1]
    
22.             in_room.add(starts[i][1])
    
23.             if activate_meetings + escaped>= K :
    
24.                 result |= in_room
    
25. 
    
26.             i += 1
    
27.         else:
    
28.             activate_meetings -= 1
    
29.             escaped += 1
    
30.             in_room.remove(ends[j][1])
    
31.             if escaped == K:
    
32.                 break
    
33.             j += 1
    
34. 
    
35.     print 'i,j', i, j
    
36.     print result
    

复制代码

3.

1. class TreeNode:
   
2.     def __init__(self, val, left, right, parent):
   
3.         self.val = val
   
4.         self.left = left
   
5.         self.right = right
   
6.         self.parent = parent
   
7. 
   
8. def treeGame(position):
   
9.     counts = [0, 0, 0] # parent, left, right
   
10. 
    
11.     def count(node):
    
12.         if node is None:
    
13.             return 0
    
14.         c = count(node.left) + count(node.right) + 1
    
15. 
    
16. 
    
17.         if position.left and position.left == node:
    
18.             counts[1] = c
    
19.         elif position.right and position.right == node:
    
20.             counts[2] = c
    
21. 
    
22.         return c
    
23. 
    
24.     counts[0] = count(root)
    
25.     counts[0] = counts[0] - counts[1] - counts[2] - 1
    
26. 
    
27. 
    
28.     i = max(*[(counts[idx], idx) for idx in range(3)])[1]
    
29. 
    
30.     if i == 0:
    
31.         return position.parent.val
    
32.     elif i == 1:
    
33.         return position.left.val
    
34.     else:
    
35.         return position.right.val
    
36. 
    
37. 
    
38. 
    
39. n1 = TreeNode(1, None, None, None)
    
40. n2 = TreeNode(2, None, None, None)
    
41. n3 = TreeNode(3, None, None, None)
    
42. n4 = TreeNode(4, None, None, None)
    
43. n5 = TreeNode(5, None, None, None)
    
44. n6 = TreeNode(6, None, None, None)
    
45. 
    
46. n1.left = n2
    
47. n1.right = n3
    
48. 
    
49. n2.left = n4
    
50. 
    
51. 
    
52. n1.right = n3
    
53. 
    
54. n3.left = n5
    
55. n3.right = n6
    
56. 
    
57. n4.parent = n2
    
58. n2.parent = n1
    
59. n3.parent = n1
    
60. n5.parent = n3
    
61. n6.parent = n3
    
62. 
    
63. root = n1
    
64. position = n2
    
65. 
    
66. 
    
67. print treeGame(position)

复制代码

4.

1. # lc 694
   
2. def numDistinctIslands(grid):
   
3.     results = set()
   
4.     seen = set()
   
5. 
   
6.     def explore(i, j, r0, c0):
   
7.         if 0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] and (i, j) not in seen:
   
8.             seen.add((i, j))
   
9.             shape.add((i-r0,j-c0))
   
10.             explore(i+1, j, r0, c0)
    
11.             explore(i-1, j, r0, c0)
    
12.             explore(i, j + 1, r0, c0)
    
13.             explore(i, j - 1, r0, c0)
    
14. 
    
15.     for i in range(len(grid)):
    
16.         for j in range(len(grid[0])):
    
17.             shape = set()
    
18. 
    
19.             explore(i, j, i, j)
    
20.             if shape:
    
21.                 results.add(frozenset(shape))
    
22. 
    
23.     return len(results)
    
24. 
    
25. grid = [[1,1,0,0,0],
    
26. [1,1,0,0,0],
    
27. [0,0,0,1,1],
    
28. [0,0,0,1,1],]
    
29. 
    
30. print numDistinctIslands(grid)
    
31. 
    
32. grid  = [[1,1,0,1,1],
    
33. [1,0,0,0,0],
    
34. [0,0,0,0,1],
    
35. [1,1,0,1,1]]
    
36. print numDistinctIslands(grid)
    
37. 
    
38. 
    
39. 
    
40. 
    
41. grid = [
    
42. [1, 1, 1, 0, 0, 0],
    
43. [1, 1, 0, 0, 0, 0],
    
44. [0, 0, 0, 1, 0, 0],
    
45. [1, 1, 1, 0, 0, 0],
    
46. [1, 1, 0, 0, 1, 1]]
    
47. 
    
48. print numDistinctIslands(grid)

复制代码