LC Python 刷题笔记 有志者事竟成

字典法 - 509. Fibonacci Number

这道题非常好，利用子函数动态构建字典，主函数查询字典直接返回结果。

1. '''
   
2. The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
   
3. 
   
4. F(0) = 0,   F(1) = 1
   
5. F(N) = F(N - 1) + F(N - 2), for N > 1.
   
6. Given N, calculate F(N).
   
7. 
   
8. Example 1:
   
9. 
   
10. Input: 2
    
11. Output: 1
    
12. Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
    
13. Example 2:
    
14. 
    
15. Input: 3
    
16. Output: 2
    
17. Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
    
18. '''
    
19. 
    
20. N = 3
    
21. 
    
22. def fib(N):
    
23.     if N <= 1:
    
24.         return N
    
25.     return helper(N)
    
26.         
    
27. def helper(N):
    
28.     cache = {0: 0, 1: 1}
    
29.     for i in range(2, N+1):
    
30.         cache[i] = cache[i-1] + cache[i-2]
    
31.     return cache[N]
    
32. 
    
33. print(fib(N))

复制代码

字典法 - 219. Contains Duplicate II（类似2SUM NON-SORTED ARRAY，不能用双指针）

1. '''
   
2. Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
   
3. 
   
4. Example 1:
   
5. 
   
6. Input: nums = [1,2,3,1], k = 3
   
7. Output: true
   
8. Example 2:
   
9. 
   
10. Input: nums = [1,0,1,1], k = 1
    
11. Output: true
    
12. Example 3:
    
13. 
    
14. Input: nums = [1,2,3,1,2,3], k = 2
    
15. Output: false
    
16. '''
    
17. nums = [1,2,3,1,2,3]
    
18. k = 2
    
19. 
    
20. def containsNearbyDuplicate(nums, k):
    
21.     d = {}
    
22.     for i in range(len(nums)) :
    
23.         if nums[i] in d:
    
24.             if i - d[nums[i]] <= k:
    
25.                 return True
    
26.         d[nums[i]] = i
    
27.     return False
    
28. print(containsNearbyDuplicate(nums, k))

复制代码

所以是已经拿到30W了，还是想法？

呵呵 楼主加油吧

350. Intersection of Two Arrays II

1. '''
   
2. Given two arrays, write a function to compute their intersection.
   
3. 
   
4. Example 1:
   
5. 
   
6. Input: nums1 = [1,2,2,1], nums2 = [2,2]
   
7. Output: [2,2]
   
8. Example 2:
   
9. 
   
10. Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    
11. Output: [4,9]
    
12. '''
    
13. 
    
14. def intersect(self, nums1, nums2):
    
15.     return list((Counter(nums1) & Counter(nums2)).elements())

复制代码