新开刷卡贴

From 2018-12-22

1. 
   
2. # log(n)
   
3. class Solution(object):
   
4. 
   
5.         @staticmethod
   
6.         def multiply(x, y):
   
7.                 x1, x2, x3, x4 = x
   
8.                 y1, y2, y3, y4 = y
   
9.                 return (x1 * y1 + x2 * y3, x1 * y2 + x2 * y4, x3 * y1 + x4 * y3, x3 * y2 + x4 * y4)
   
10. 
    
11.         @staticmethod
    
12.         def matrix_pow(matrix, n):
    
13.                 if n == 1:
    
14.                         return matrix
    
15. 
    
16.                 if n % 2 == 1:
    
17.                         return Solution.multiply(matrix,
    
18.                                                                          Solution.multiply(Solution.matrix_pow(matrix, (n-1)/2),
    
19.                                                                                                             Solution.matrix_pow(matrix, (n-1)/2)))
    
20.                 else:
    
21.                         return Solution.multiply(Solution.matrix_pow(matrix, n/2),
    
22.                                                      Solution.matrix_pow(matrix, n/2))
    
23. 
    
24. 
    
25.         def get(self, n):
    
26.                 if n == 1 or n == 2: return 1
    
27.                 # pow((0, 1, 1, 1), n - 1) * (1, 1)
    
28.                 x1, x2, x3, x4 = Solution.matrix_pow((0, 1, 1, 1), n - 1)
    
29.                 return x1 + x2
    
30. 
    
31. 
    
32. if __name__ == "__main__":
    
33.         obj = Solution()
    
34.         for i in range(1, 100):
    
35.                 print("i: %s, fabo: %s" % (i, obj.get(i)))
    

复制代码

补充内容 (2018-12-22 20:51):
time complexity: log(N)

Leetcode 518, 代码写了好一会儿

1. 
   
2. class Solution(object):
   
3.     def change(self, amount, coins):
   
4.         """
   
5.         :type amount: int
   
6.         :type coins: List[int]
   
7.         :rtype: int
   
8.         """
   
9.         if len(coins) == 0:
   
10.                 return 1 if amount == 0 else 0
    
11. 
    
12.         coins = sorted(coins)
    
13.         dp = []
    
14.         # dp[amount][idx]
    
15.         # amount starting from 1
    
16.         # idx starting from 0
    
17.         # initialization
    
18.         # idx = len(coins) - 1 or amount = 0
    
19.         for j in range(amount + 1):
    
20.                 dp.append([1 if j == 0 else 0] * len(coins))  # one possible way when amount = 0
    
21.                 if j % coins[-1] == 0:  # integer division
    
22.                         dp[j][-1] = 1
    
23. 
    
24.         for i in range(1, amount + 1):
    
25.                 for j in range(len(coins) - 1)[::-1]:
    
26.                         dp[i][j] = dp[i][j + 1] + (dp[i - coins[j]][j] if i - coins[j] >= 0 else 0)
    
27. 
    
28.         return dp[amount][0]
    
29. 
    
30. 
    
31. if __name__ == "__main__":
    
32.         obj = Solution()
    
33.         # print(obj.change(25, [1, 2, 5]))
    
34.         print(obj.change(10, [5]))
    
35.         

复制代码

补充内容 (2018-12-22 21:59):
使用dp

Leetcode 264

1. 
   
2. 
   
3. class Solution(object):
   
4.     def nthUglyNumber(self, n):
   
5.         """
   
6.         :type n: int
   
7.         :rtype: int
   
8.         """
   
9.         tag2, tag3, tag5 = 0, 0, 0
   
10.         ans = []
    
11.         ans.append(1)
    
12.         for _ in range(n - 1):
    
13.                 ans.append(min(2 * ans[tag2], 3 * ans[tag3], 5 * ans[tag5]))
    
14. 
    
15.                 while 2 * ans[tag2] <= ans[-1]: tag2 += 1
    
16.                 while 3 * ans[tag3] <= ans[-1]: tag3 += 1
    
17.                 while 5 * ans[tag5] <= ans[-1]: tag5 += 1
    
18.         return ans
    

复制代码

补充内容 (2018-12-22 22:24):
Time complexity: O(N)

Leetcode 886

1. import collections
   
2. 
   
3. class Solution(object):
   
4.     def __init__(self):
   
5.         self.ans = True
   
6. 
   
7.     def dfs(self, p, graph, colors):
   
8.         for next in graph[p]:
   
9.             if colors[next] == 0:
   
10.                 colors[next] = -1 * colors[p]
    
11.                 self.dfs(next, graph, colors)
    
12.             else:
    
13.                 if colors[next] == colors[p]:
    
14.                     self.ans = False
    
15.                     break
    
16. 
    
17.     def possibleBipartition(self, N, dislikes):
    
18.         colors = [0] * (N + 1)  # 0 => initial, 1 => read, -1 => blue
    
19.         graph = collections.defaultdict(list)
    
20.         for pairs in dislikes:
    
21.             graph[pairs[0]].append(pairs[1])
    
22.             graph[pairs[1]].append(pairs[0])
    
23. 
    
24.         for p in range(1, N + 1):
    
25.             if colors[p] == 0 and p in graph:
    
26.                 colors[p] = 1
    
27.                 self.dfs(p, graph, colors)
    
28.                 if not self.ans:
    
29.                     return False
    
30.         return True
    
31. 
    
32. 
    
33. if __name__ == "__main__":
    
34.         obj = Solution()
    
35.         print(obj.possibleBipartition(3, [[1,2],[1,3],[2,3]]))

复制代码

Leetcode 449, 利用BST的性质，直接将前序遍历的结果保存

1. # Definition for a binary tree node.
   
2. # class TreeNode(object):
   
3. #     def __init__(self, x):
   
4. #         self.val = x
   
5. #         self.left = None
   
6. #         self.right = None
   
7. 
   
8. class Codec:
   
9. 
   
10.     def serialize(self, root):
    
11.         """Encodes a tree to a single string.
    
12.         
    
13.         :type root: TreeNode
    
14.         :rtype: str
    
15.         """
    
16.         # using prior reversal
    
17.         import json
    
18.         ans = []
    
19.         def rev(ans, root):
    
20.             if not root:
    
21.                 return
    
22.             ans.append(root.val)
    
23.             rev(ans, root.left)
    
24.             rev(ans, root.right)
    
25.         
    
26.         rev(ans, root)
    
27.         return json.dumps(ans)
    
28.         
    
29. 
    
30.     def deserialize(self, data):
    
31.         """Decodes your encoded data to tree.
    
32.         
    
33.         :type data: str
    
34.         :rtype: TreeNode
    
35.         """
    
36.         import json
    
37.         data = json.loads(data)
    
38.         return self.deser(data)
    
39.    
    
40.     def deser(self, data):   
    
41.         if not data:
    
42.             return None
    
43.         
    
44.         root = TreeNode(data[0])
    
45.         i = 1
    
46.         while i < len(data) and data[i] < data[0]:
    
47.             i += 1
    
48.         root.left = self.deser(data[1:i])
    
49.         root.right = self.deser(data[i:])
    
50.         return root
    
51.         
    
52. 
    
53. # Your Codec object will be instantiated and called as such:
    
54. # codec = Codec()
    
55. # codec.deserialize(codec.serialize(root))

复制代码

top k smallest numbers in the array, 使用最大堆, python 自带最小堆，我们使用最小堆来实现一个最大堆然后来实现该功能

1. # https://docs.python.org/2/library/heapq.html
   
2. import sys
   
3. import heapq
   
4. import sys
   
5. 
   
6. class TopKHeap(object):
   
7.     # implementation the max-heap
   
8.     def __init__(self, k):
   
9.         self.k = k
   
10.         self.data = []
    
11. 
    
12.     def push(self, elem):
    
13.         elem = sys.maxsize - elem
    
14.         if len(self.data) < self.k:
    
15.             heapq.heappush(self.data, elem)
    
16.         else:
    
17.             topk_small = self.data[0]
    
18.             if elem > topk_small:
    
19.                 heapq.heapreplace(self.data, elem)  
    
20. 
    
21.     def topk(self):
    
22.         return [int(sys.maxsize - elem) for elem in self.data]
    
23. 
    
24. 
    
25. def main():
    
26.     # have to using the max-heap, default using min-heap
    
27.     list_num = [1, 2, 10, 4, 5, 6, 7, 8, 9, -1]
    
28.     th = TopKHeap(5)
    
29. 
    
30.     for i in list_num:
    
31.         th.push(i)
    
32. 
    
33.     print th.topk()
    
34. 
    
35. if __name__ == "__main__":
    
36.     main()

复制代码

翻转一个stack，仅仅使用递归，有点小意思

1. 
   
2. # merely using recursion
   
3. class Solution(object):
   
4.         def reverse_stack(self, stack):
   
5.                 if len(stack) == 0:
   
6.                         return []
   
7. 
   
8.                 top = stack.pop()
   
9.                 self.reverse_stack(stack)
   
10.                 self.send_bottom(stack, top)
    
11.                 return stack
    
12. 
    
13.         def send_bottom(self, stack, top):
    
14.                 if len(stack) == 0:
    
15.                         stack.append(top)
    
16.                 else:
    
17.                         t_top = stack.pop()
    
18.                         self.send_bottom(stack, top)
    
19.                         stack.append(t_top)
    
20. 
    
21. 
    
22. if __name__ == "__main__":
    
23.         obj = Solution()
    
24.         print(obj.reverse_stack([1, 2, 3, 4, 5, 6]))

复制代码

Leetcode 962, Maximum Width Ramp

1. 
   
2. import sys
   
3. class Solution:
   
4.     def maxWidthRamp(self, A):
   
5.         """
   
6.         :type A: List[int]
   
7.         :rtype: int
   
8.         """
   
9.         uniq = {}
   
10.         for idx, elem in enumerate(A):
    
11.             uniq[elem] = [idx, uniq[elem][1] if elem in uniq else idx]
    
12. 
    
13.         # (number, right-most index, left-most index)
    
14.         uniq = [(k, v[0], v[1]) for k, v in uniq.items()]
    
15. 
    
16.         uniq = sorted(uniq, key=lambda x: x[0])
    
17. 
    
18.         ans, m = 0, sys.maxsize
    
19.         for elem in uniq:
    
20.             m = min(m, elem[2])
    
21.             ans = max(ans, elem[1] - m)
    
22. 
    
23.         return ans
    

复制代码

Leetcode 963,

1. import collections
   
2. import sys
   
3. class Solution:
   
4. 
   
5.     def minAreaFreeRect(self, A):
   
6.         """
   
7.         :type points: List[List[int]]
   
8.         :rtype: float
   
9.         """
   
10.         def get_len(p1, p2):
    
11.             return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
    
12. 
    
13.         h_vectors = collections.defaultdict(list)
    
14.         N = len(A)
    
15.         for i in range(N):
    
16.             for j in range(i + 1, N):
    
17.                 vector = (A[j][0] - A[i][0], A[j][1] - A[i][1])
    
18.                 pos = -1 if vector[1] < 0 or (vector[1] == 0 and vector[0] < 0) else 1
    
19.                 # the order is important
    
20.                 h_vectors[(vector[0] * pos, vector[1] * pos)].append((i, j) if pos == 1 else (j, i))
    
21. 
    
22.         ans = sys.maxsize
    
23.         for vector, lines in h_vectors.items():
    
24.             if len(lines) >= 2:
    
25.                 for i in range(len(lines)):
    
26.                     for j in range(i + 1, len(lines)):
    
27.                         p1, p2 = A[lines[i][0]], A[lines[i][1]]
    
28.                         p3, p4 = A[lines[j][0]], A[lines[j][1]]
    
29.                         if (p1[0] - p3[0]) * (p1[0] - p2[0]) + (p1[1] - p3[1]) * (p1[1] - p2[1]) == 0:  # perpendicular
    
30.                             ans = min(get_len(p1, p2) * get_len(p1, p3), ans)
    
31. 
    
32.         return 0 if ans == sys.maxsize else ans

复制代码