刷题记录帖子

LeetCode 478 Generate Random Point in a Circle (Python)
两种方法，参数方程和拒绝采样。

参考资料：
(1) 参数方程
这个还真是大意了，需要主要使得 probability 一致而不是让 radius 一致。

https://stackoverflow.com/questi ... -a-circle-uniformly

(2) 拒绝采样

这个更加方便而且简单易实现，不像前面一个有坑。

https://maxming0.github.io/2021/ ... -Point-in-a-Circle/

841        Keys and Rooms

其实问题是图的遍历，DFS 就可以解决

1. 
   
2. 
   
3. class Solution:
   
4.     def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
   
5.         visited = set()
   
6.         
   
7.         def DFS(room):
   
8.             visited.add(room)
   
9.             for key in rooms[room]:
   
10.                 if key not in visited:
    
11.                     DFS(key)
    
12.         DFS(0)
    
13.         return len(visited) == len(rooms)
    
14. 
    

复制代码

LeetCode 1396. Design Underground System (Python)

简单题，用两个 hashtable 解决

869        Reordered Power of 2

枚举法

LeetCode 966. Vowel Spellchecker (Python)

通过 # 来代替元音字母简化中间状态，简化计算。

LeetCode 923. 3Sum With Multiplicity (Python)

freq 的乘法原理

注意下 C_n^a 的计算公式 n!/(a! * (n-a)! )  == n * --- n-a+1 / a*---*1

LeetCode 870. Advantage Shuffle (Python)
记录下 B 的index-val list 来简化位置求解，贪心解决问题。

376. Wiggle Subsequence

其实就是 DP 主要是考虑 up 和 down 这两个不同的 trends 的大小，要记住下一个长度的更新要从对面取初始值。

916. Word Subsets

对于 B 求单独的 word 合集。

可以用 【0】 * 26 的数组统计出现次数。

1. class Solution(object):
   
2.     def wordSubsets(self, A, B):
   
3.         def count(word):
   
4.             ans = [0] * 26
   
5.             for letter in word:
   
6.                 ans[ord(letter) - ord('a')] += 1
   
7.             return ans
   
8. 
   
9.         bmax = [0] * 26
   
10.         for b in B:
    
11.             for i, c in enumerate(count(b)):
    
12.                 bmax[i] = max(bmax[i], c)
    
13. 
    
14.         ans = []
    
15.         for a in A:
    
16.             if all(x >= y for x, y in zip(count(a), bmax)):
    
17.                 ans.append(a)
    
18.         return ans

复制代码

LeetCode 647. Palindromic Substrings (Python)

DP 或者 Check possible centers of the Palindromic Substrings