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

455. Assign Cookies 这道题很好！

1. '''
   
2. Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
   
3. 
   
4. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
   
5. 
   
6. Example 1:
   
7. 
   
8. Input: g = [1,2,3], s = [1,1]
   
9. Output: 1
   
10. Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
    
11. And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
    
12. You need to output 1.
    
13. Example 2:
    
14. 
    
15. Input: g = [1,2], s = [1,2,3]
    
16. Output: 2
    
17. Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
    
18. You have 3 cookies and their sizes are big enough to gratify all of the children,
    
19. You need to output 2.
    
20. 
    
21. Constraints:
    
22. 
    
23. 1 <= g.length <= 3 * 104
    
24. 0 <= s.length <= 3 * 104
    
25. 1 <= g[i], s[j] <= 231 - 1
    
26. '''
    
27. 
    
28. def findContentChildren(self, g: List[int], s: List[int]) -> int:
    
29.         g = sorted(g)
    
30.         g = g[::-1]
    
31.         s = sorted(s)
    
32.         start = 0
    
33.         end = len(s)-1
    
34.         n = len(g)
    
35.         ans = 0
    
36.         while start<n and end>=0:
    
37.             if g[start]<=s[end]:
    
38.                 start+=1
    
39.                 end-=1
    
40.                 ans+=1
    
41.             else:
    
42.                 start+=1
    
43.         return ans

复制代码

1103. Distribute Candies to People

给大人分糖果，两个循环，提前构筑结果数列

1. '''
   
2. We distribute some number of candies, to a row of n = num_people people in the following way:
   
3. 
   
4. We then give 1 candy to the first person, 2 candies to the second person, and so on until we give n candies to the last person.
   
5. 
   
6. Then, we go back to the start of the row, giving n + 1 candies to the first person, n + 2 candies to the second person, and so on until we give 2 * n candies to the last person.
   
7. 
   
8. This process repeats (with us giving one more candy each time, and moving to the start of the row after we reach the end) until we run out of candies.  The last person will receive all of our remaining candies (not necessarily one more than the previous gift).
   
9. 
   
10. Return an array (of length num_people and sum candies) that represents the final distribution of candies.
    
11. 
    
12. 
    
13. 
    
14. Example 1:
    
15. 
    
16. Input: candies = 7, num_people = 4
    
17. Output: [1,2,3,1]
    
18. Explanation:
    
19. On the first turn, ans[0] += 1, and the array is [1,0,0,0].
    
20. On the second turn, ans[1] += 2, and the array is [1,2,0,0].
    
21. On the third turn, ans[2] += 3, and the array is [1,2,3,0].
    
22. On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].
    
23. Example 2:
    
24. 
    
25. Input: candies = 10, num_people = 3
    
26. Output: [5,2,3]
    
27. Explanation:
    
28. On the first turn, ans[0] += 1, and the array is [1,0,0].
    
29. On the second turn, ans[1] += 2, and the array is [1,2,0].
    
30. On the third turn, ans[2] += 3, and the array is [1,2,3].
    
31. On the fourth turn, ans[0] += 4, and the final array is [5,2,3].
    
32. '''
    
33. 
    
34. def distributeCandies(self, candies: int, num_people: int) -> List[int]:
    
35.         result = [0] * num_people
    
36.         r = 0
    
37.         while candies > 0:
    
38.             for i in range(num_people):
    
39.                 portion = r * num_people + (i+1)
    
40.                 if portion <= candies:
    
41.                     result[i] += portion
    
42.                     candies -= portion
    
43.                 else:
    
44.                     result[i] += candies
    
45.                     return result
    
46.             r += 1
    
47.         return result

复制代码

1128. Number of Equivalent Domino Pairs - 字典法的终结篇，亚麻神题

下面两个方法，由于使用了defaultdict()，所以就不需要额外对字典中没有的KEY赋初始值了，else: dic[tuple(sorted(c))] = 1。另外列表不能直接在字典里当KEY，所以用tulpe()封装一下。

1. '''
   
2. Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) - that is, one domino can be rotated to be equal to another domino.
   
3. 
   
4. Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].
   
5. 
   
6. Example 1:
   
7. 
   
8. Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
   
9. Output: 1
   
10. '''
    
11. 
    
12. def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
    
13.         dic = {}
    
14.         count = 0   
    
15.         for c in dominoes:
    
16.             if tuple(sorted(c)) in dic:
    
17.                 count += dic[tuple(sorted(c))]
    
18.                 dic[tuple(sorted(c))] += 1
    
19.             else:
    
20.                 dic[tuple(sorted(c))] = 1
    
21.         return count
    
22.    
    
23. def numEquivDominoPairs(self, dominoes):
    
24.         dic = defaultdict(int)
    
25.         count = 0   
    
26.         for c in dominoes:
    
27.             if tuple(sorted(c)) in dic:
    
28.                 count += dic[tuple(sorted(c))]
    
29.             dic[tuple(sorted(c))] += 1
    
30.         return count

复制代码

[/i][/i]

1237. Find Positive Integer Solution for a Given Equation - 双循环

1. '''
   
2. Given a function  f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.
   
3. 
   
4. The function is constantly increasing, i.e.:
   
5. 
   
6. f(x, y) < f(x + 1, y)
   
7. f(x, y) < f(x, y + 1)
   
8. The function interface is defined like this:
   
9. 
   
10. interface CustomFunction {
    
11. public:
    
12.   // Returns positive integer f(x, y) for any given positive integer x and y.
    
13.   int f(int x, int y);
    
14. };
    
15. For custom testing purposes you're given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you'll know only two functions from the list.  
    
16. 
    
17. You may return the solutions in any order.
    
18. 
    
19. 
    
20. 
    
21. Example 1:
    
22. 
    
23. Input: function_id = 1, z = 5
    
24. Output: [[1,4],[2,3],[3,2],[4,1]]
    
25. Explanation: function_id = 1 means that f(x, y) = x + y
    
26. Example 2:
    
27. 
    
28. Input: function_id = 2, z = 5
    
29. Output: [[1,5],[5,1]]
    
30. Explanation: function_id = 2 means that f(x, y) = x * y
    
31. 
    
32. 
    
33. Constraints:
    
34. 
    
35. 1 <= function_id <= 9
    
36. 1 <= z <= 100
    
37. It's guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
    
38. It's also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000
    
39. '''
    
40. 
    
41. def findSolution(customfunction, z):
    
42.         result = []
    
43.         x = y = 1
    
44.         while customfunction.f(x,y) < z:
    
45.             while customfunction.f(x,y) < z:
    
46.                 y += 1
    
47.             if customfunction.f(x,y) == z:
    
48.                 result.append([x,y])
    
49.             x += 1
    
50.             y = 1
    
51.         if customfunction.f(x,y)==z:
    
52.             result.append([x,y])
    
53.         return result

复制代码

楼主非常励志！点赞

楼主很励志,建议建立一个github 保留自己的代码记录,更方便.

Anonyknight 发表于 2020-10-24 13:02
楼主很励志,建议建立一个github 保留自己的代码记录,更方便.

已经搞定开始上传和全世界的刷子一起共享了，你的建议让三分地每天损失了10多个流量，哈哈哈哈哈。

李浩泉 发表于 2020-10-23 13:45
我也有刷ML的题，今天做了好几道Maximum Likelihood Estimate (MLE) 和 Maximum A Posteriori (MAP) 的题 ...

可以预见楼主将来成为面霸！如果建了github请分享呀

李浩泉 发表于 2020-10-23 13:45
我也有刷ML的题，今天做了好几道Maximum Likelihood Estimate (MLE) 和 Maximum A Posteriori (MAP) 的题 ...

Maximum Likelihood Estimate (MLE) 和 Maximum A Posteriori (MAP) 这些都有啥题啊？