9.26新鲜热乎的狗狗昂塞

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

第一题:
比较简单遍历所有可能就行了

1. def uniqueSubsetSum(A):
   
2.     ans = {0}  # set initialization
   
3.     N = len(A)
   
4.     for i in range(N):
   
5.         cur_ans = {A[i]}
   
6.         for s in ans:
   
7.             cur_ans.add(s+A[i])
   
8.         ans = ans.union(cur_ans)
   
9.     return list(ans)

复制代码

第二题的话，有点小复杂，我感觉前面一些人说的不确定对不对，可以看思路，就是找特殊点

1. def kthUser(logs, k):
   
2.     ans, must, possible = [], [], []
   
3.     for _, s, e in logs:
   
4.         ans.append(s)
   
5.         ans.append(e)
   
6. 
   
7.     ans = sorted(ans)
   
8.     for t in ans:
   
9.         cur_must, cur_possible = [], []
   
10.         for user_id, s, e in logs:
    
11.             if t >= e:
    
12.                 cur_must.append(user_id)
    
13.             if s <= t < e:
    
14.                 cur_possible.append(user_id)
    
15.             must.append(cur_must)
    
16.             possible.append(cur_possible)
    
17. 
    
18.     res = set()
    
19.     for idx, must_values in enumerate(must):
    
20.         if k - len(possible[idx]) <= len(must_values) < k:
    
21.             for i in possible[idx]:
    
22.                 res.add(i)
    
23. 
    
24.     return list(res)
    
25. 
    
26. 
    
27. logs = [[1,20,30], [2,0,50], [3,45,70], [4,35,55]]
    
28. for k in [1, 2, 3, 4]:
    
29.     print "k=%s" % k, kthUser(logs, k)

复制代码

第三题，宝宝不会，没想出来。求详细论证第三题

第四题，如果单纯计算岛屿的数量直接用dfs就可以求出来，但是要求distinct，其实就是对岛屿做一个归一化处理而已，其实全部上下左右移动好，求一个唯一key就行了

1. def NumberOfDistinctIsland(matrix):
   
2.     import sys
   
3. 
   
4.     def dfs(i, j, group):
   
5.         if i >= N or j >= M:
   
6.             return None
   
7. 
   
8.         if matrix[i][j] == 1:
   
9.             group.append((i, j))
   
10.             matrix[i][j] = 0
    
11.             dfs(i+1, j, group)
    
12.             dfs(i, j + 1, group)
    
13.             dfs(i + 1, j + 1, group)
    
14. 
    
15.     def transform(group):
    
16.         group = sorted(group)
    
17.         min_i, min_j = sys.maxint, sys.maxint
    
18.         for i, j in group:
    
19.             min_i = min(i, min_i)
    
20.             min_j = min(j, min_j)
    
21.         key = ""
    
22.         for i, j in group:
    
23.             key += "%s,%s" % (i-min_i, j-min_j)
    
24.         return key
    
25. 
    
26.     N = len(matrix)
    
27.     M = len(matrix[0])
    
28.     groups = []
    
29.     for i in range(N):
    
30.         for j in range(M):
    
31.             if matrix[i][j] == 1:
    
32.                 group = []
    
33.                 dfs(i, j, group)
    
34.                 groups.append(transform(group))
    
35.     return len(set(groups))
    
36. 
    
37. 
    
38. matrix = [
    
39. [1, 1, 1, 0, 0, 0],
    
40. [1, 1, 0, 0, 0, 0],
    
41. [0, 0, 0, 1, 0, 0],
    
42. [1, 1, 1, 0, 0, 0],
    
43. [1, 1, 0, 0, 1, 1]]
    
44. 
    
45. print NumberOfDistinctIsland(matrix)

复制代码

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

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)

复制代码