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

# 965 Univalued Binary Tree

也是一道非常好的通过简单遍历，不需要算法就能解决的二叉树问题。

1. '''
   
2. A binary tree is univalued if every node in the tree has the same value.
   
3. 
   
4. Return true if and only if the given tree is univalued.
   
5. 
   
6. Example 1:
   
7. 
   
8. Input: [1,1,1,1,1,null,1]
   
9. Output: true
   
10. Example 2:
    
11. 
    
12. Input: [2,2,2,5,2]
    
13. Output: false
    
14. 
    
15. Note:
    
16. 
    
17. The number of nodes in the given tree will be in the range [1, 100].
    
18. Each node's value will be an integer in the range [0, 99].
    
19. '''
    
20. 
    
21. def isUnivalTree(self, root: TreeNode) -> bool:
    
22.     if not root: return False
    
23.     result = []
    
24.     current = []
    
25.     current.append(root)
    
26.         
    
27.     while current:
    
28.         next_level = []
    
29.         for n in current:
    
30.             result.append(n.val)
    
31.             if n.left:
    
32.                 next_level.append(n.left)
    
33.             if n.right:
    
34.                 next_level.append(n.right)
    
35.             current = next_level
    
36.     s = set(result)
    
37.     return len(s) == 1

复制代码

记得楼主前阵子拿到了facebook DE的面试，能更新一下后来的onsite情况么？十分感谢！

算法第五计：Greedy 贪心算法

It makes optimal choice at each stage with the intent of finding a global optimum.

# 763 Partition Labels

Complexity Analysis

Time Complexity：O(N), where N is the length of S.

Space Complexity：O(1) to keep data structure last of not more than 26 characters.

1. '''
   
2. A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.
   
3. 
   
4. 
   
5. 
   
6. Example 1:
   
7. 
   
8. Input: S = "ababcbacadefegdehijhklij"
   
9. Output: [9,7,8]
   
10. Explanation:
    
11. The partition is "ababcbaca", "defegde", "hijhklij".
    
12. This is a partition so that each letter appears in at most one part.
    
13. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
    
14. '''
    
15. 
    
16. def partitionLabels(self, S):
    
17.     last = {c: i for i, c in enumerate(S)}
    
18.     j = anchor = 0
    
19.     ans = []
    
20.     for i, c in enumerate(S):
    
21.         j = max(j, last[c])
    
22.         if i == j:
    
23.             ans.append(i - anchor + 1)
    
24.             anchor = i + 1
    
25.     return ans

复制代码

算法第六计：Divide and Conquer 分治法

It breaks down a problem into more sub-problem until these become simple enough to be solved directly.


# 53 Maximum Subarray

Complexity Analysis

Time complexity : O(NlogN)

Space complexity : O(logN)

1. '''
   
2. Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
   
3. 
   
4. Example:
   
5. 
   
6. Input: [-2,1,-3,4,-1,2,1,-5,4],
   
7. Output: 6
   
8. Explanation: [4,-1,2,1] has the largest sum = 6.
   
9. Follow up:
   
10. 
    
11. If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
    
12. '''
    
13. 
    
14.     def maxSubArray(self, nums):
    
15.         return self.helper(nums, 0, len(nums) - 1)
    
16.    
    
17.     def cross_sum(self, nums, left, right, p):
    
18.         if left == right:
    
19.                 return nums[left]
    
20. 
    
21.         left_subsum = float('-inf')
    
22.         curr_sum = 0
    
23.         for i in range(p, left - 1, -1):
    
24.             curr_sum += nums[i]
    
25.             left_subsum = max(left_subsum, curr_sum)
    
26. 
    
27.         right_subsum = float('-inf')
    
28.         curr_sum = 0
    
29.         for i in range(p + 1, right + 1):
    
30.             curr_sum += nums[i]
    
31.             right_subsum = max(right_subsum, curr_sum)
    
32. 
    
33.         return left_subsum + right_subsum   
    
34.    
    
35.     def helper(self, nums, left, right):
    
36.         if left == right:
    
37.             return nums[left]
    
38.         
    
39.         p = (left + right) // 2
    
40.             
    
41.         left_sum = self.helper(nums, left, p)
    
42.         right_sum = self.helper(nums, p + 1, right)
    
43.         cross_sum = self.cross_sum(nums, left, right, p)
    
44.         return max(left_sum, right_sum, cross_sum)
    
45.         

复制代码

如果不用分治法，也可以做。感觉coding里面的分治算法很像SQL里面的CTE或者in-line sub query。如果不能一口气写完，那就多分几个CTE出来，只要CTE足够多，最后不论多么复杂的query也能做出来。

1. def maxSubArray(self, nums: List[int]) -> int:
   
2.     n = len(nums)
   
3.     current_sum = nums[0]
   
4.     max_sum = current_sum
   
5.     i = 1
   
6.     while i < n :
   
7.         current_sum = max(nums, current_sum + nums)
   
8.         max_sum = max(max_sum, current_sum)
   
9.         i += 1
   
10.     return max_sum

复制代码

李浩泉 发表于 2020-07-30 09:19:03
没有频率，也没有顺序，就是平推，从#1 Two Sum开始，一直到最后的#1533        
Find the Index of the Large Integer。一边WFH，一边等待着机会

哈哈哈sql不算编程。过于真实

算法第七计：Dynamic Programming 动态规划


动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。


计算机归根结底只会做一件事：穷举。所有的算法都是在让计算机【如何聪明地穷举】而已，动态规划也是如此。


LC算题基本算法思想总结：

1. 穷举（Proof by exhaustion）

    1.1 算法第一计：Brute Force 暴力搜索
    1.2 算法第二计：Two Pointers 双指针（left / right；fast / slow）
    1.3 算法第三计：Iteration 迭代
    1.4 算法第四计：Recursion 递归

2. 贪婪
    2.1 算法第五计：Greedy 贪心算法

3. 分治
    3.1 算法第六计：Divide and Conquer 分治法

4. 动态规划
    4.1 算法第七计：Dynamic Programming 动态规划

5. 回溯
    5.1 算法第八计：Backtracking 回溯算法

6. 其它未分类
    6.1 算法第九计：Hash Table 哈希表
    6.2 算法第十计：Math 代数法
    6.3 算法第十一计：Union-Find 并查集
    6.4 算法第十二计：Sliding Window 滑动窗口

算法第七计：Dynamic Programming 动态规划

# 139 Word Break

1. '''
   
2. Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
   
3. 
   
4. Note:
   
5. 
   
6. The same word in the dictionary may be reused multiple times in the segmentation.
   
7. You may assume the dictionary does not contain duplicate words.
   
8. Example 1:
   
9. 
   
10. Input: s = "leetcode", wordDict = ["leet", "code"]
    
11. Output: true
    
12. Explanation: Return true because "leetcode" can be segmented as "leet code".
    
13. Example 2:
    
14. 
    
15. Input: s = "applepenapple", wordDict = ["apple", "pen"]
    
16. Output: true
    
17. Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
    
18.              Note that you are allowed to reuse a dictionary word.
    
19. Example 3:
    
20. 
    
21. Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
    
22. Output: false
    
23. '''
    
24. 
    
25. def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    
26.     dp = [False]*len(s)+[True]
    
27.     for i in range(len(s)-1, -1, -1):
    
28.         dp[i] = any(len(s)-i >= len(word) and word == s[i:i+len(word)] and dp[i+len(word)] for word in wordDict)
    
29.     return dp[0]

复制代码

[/i]

1. 
   
2. def wordBreak(self, s, wordDict):
   
3.     if not wordDict:
   
4.         return False
   
5.     d = [False] * len(s)
   
6.     for i in range(len(s)):
   
7.         for w in wordDict:
   
8.             if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) is -1):
   
9.                 d[i] = True
   
10.     return d[-1]

复制代码

做几道DE的真题，检验一下。SDE们也可以过来看看，试试。

# What Is Wrong With This Family?


Michael always knew that there was something wrong with his family. Many strangers were introduced to him as part of it.

Michael should figure this out. He's spent almost a month parsing the family archives. He has all father-son connections of his entire family collected in one place.

With all that data Michael can easily understand who the strangers are. Or maybe the only stranger in this family is Michael? Let's see.

You have a list of family ties between father and son. Each element on this list has two elements. The first is the father's name, the second is the son's name. All names in the family are unique. Check if the family tree is correct. There are no strangers in the family tree. All connections in the family are natural.

Input: list of lists. Each element has two strings. The list has at least one element

Output: bool. Is the family tree correct.

1. def is_family(tree):
   
2.    
   
3.     #　先大概清理一下数据，简单条件排除明显错误：排除多个祖先
   
4.     father = []
   
5.     son = []
   
6.     for c in tree:
   
7.         father.append(c[0])
   
8.         son.append(c[1])
   
9.     if len(set(father).difference(set(son))) != 1:
   
10.         return False
    
11.    
    
12.     # 排除互为父子现象
    
13.     for j in range(len(tree)):
    
14.         for k in range(1,len(tree)):
    
15.             if tree[j] == tree[k][::-1]:
    
16.                 return False
    
17.    
    
18.     # 为了构造有序的新树，先做一个小函数，返回当前的Father
    
19.     def top_helper(tree):
    
20.         father = []
    
21.         son = []
    
22.         for c in tree:
    
23.             father.append(c[0])
    
24.             son.append(c[1])
    
25.         if len(set(father).difference(set(son))) == 1:
    
26.             return ''.join(set(father).difference(set(son)))
    
27.    
    
28.     # 构建一个有序的新树，保证先祖永远在前，子孙永远在后
    
29.     dummy_tree = tree
    
30.     list1 = []
    
31.     list2 = []
    
32.     while len(dummy_tree) > 1:
    
33.         top = top_helper(dummy_tree)
    
34.         list2 = []
    
35.         for i in range(len(dummy_tree)):
    
36.             if top in dummy_tree[i]:               
    
37.                 list1.append(dummy_tree[i])
    
38.             else:
    
39.                 list2.append(dummy_tree[i])
    
40.         dummy_tree = list2
    
41.     new_tree = list1 + list2
    
42.    
    
43.     # 字典法，祖先为0，后世子孙从1开始递加，如果最后字典成立，则返回True
    
44.     if len(new_tree) < 2: return True
    
45.     dic = {}
    
46.     dic[new_tree[0][0]] = 0
    
47.     dic[new_tree[0][1]] = 1
    
48.     num = 1
    
49.     for i in range(1,len(new_tree)):   
    
50.         if new_tree[i][0] not in dic or new_tree[i][1] in dic:
    
51.             return False
    
52.         elif new_tree[i][1] not in dic:
    
53.             dic[new_tree[i][1]] = num + 1
    
54.             num += 1
    
55.     return True
    
56. 
    
57. if __name__ == "__main__":
    
58.     #These "asserts" using only for self-checking and not necessary for auto-testing
    
59.     assert is_family([
    
60.       ['Logan', 'Mike']
    
61.     ]) == True, 'One father, one son'
    
62.     assert is_family([
    
63.       ['Logan', 'Mike'],
    
64.       ['Logan', 'Jack']
    
65.     ]) == True, 'Two sons'
    
66.     assert is_family([
    
67.       ['Logan', 'Mike'],
    
68.       ['Logan', 'Jack'],
    
69.       ['Mike', 'Alexander']
    
70.     ]) == True, 'Grandfather'
    
71.     assert is_family([
    
72.       ['Logan', 'Mike'],
    
73.       ['Logan', 'Jack'],
    
74.       ['Mike', 'Logan']
    
75.     ]) == False, 'Can you be a father to your father?'
    
76.     assert is_family([
    
77.       ['Logan', 'Mike'],
    
78.       ['Logan', 'Jack'],
    
79.       ['Mike', 'Jack']
    
80.     ]) == False, 'Can you be a father to your brother?'
    
81.     assert is_family([
    
82.         ["Logan","Mike"],
    
83.         ["Alexander","Jack"],
    
84.         ["Jack","Alexander"]
    
85.     ]) == False
    
86.     assert is_family([
    
87.         ["Logan","Mike"],
    
88.         ["Alexander","Jack"],
    
89.         ["Jack","Logan"]
    
90.     ]) == True,'Family connections can be listed in any directions'
    
91.     assert is_family([
    
92.         ['Logan', 'Mike'],
    
93.         ['Logan', 'Jack'],
    
94.         ['Mike', 'Alexander']
    
95.     ]) == True
    
96.     assert is_family([
    
97.       ['Logan', 'William'],
    
98.       ['Logan', 'Jack'],
    
99.       ['Mike', 'Alexander']
    
100.     ]) == False, 'Looks like Mike is stranger in Logan\'s family'
     
101.     print("Looks like you know everything. It is time for 'Check'!")

复制代码

[/i][/i][/i][/i][/i][/i][/i]

上面这道题最大的难点在于：Family connections can be listed in any directions。一开始不知道谁是先祖，谁是子孙，逻辑判断的时候无从下手，无法保证IF条件可以覆盖所有场景。所以

1. 首先试图创建新的Tree，祖先在前，子孙在后；
2. 为了这个新Tree，还需要构建一个小函数，判断当前的祖先；
3. 为了创建新的Tree，还需要提前清理现有的数据，排除一些明显错误，比如：多个祖先，互为父子
4. 排除了，多个祖先F，互为父子等情况，也建立了有序的新Tree，这个时候就可以用字典，从头开始遍历，祖先为0，后面的依次加1，如果字典成立，则True，否则就是False。

DE的考题，非常实际，需要用Python在处理Data Pipeline ETL上做数据清理和逻辑判断。

后来看了某5级SDE的代码，心里又崩溃了，看了好久才理解：

SDE的高级字典法：from collections import defaultdict


当我使用普通的字典时，用法一般是dict={}，添加元素的只需要dict[element] =value即，调用的时候也是如此，dict[element] = xxx，但前提是element字典里，如果不在字典里就会报错。defaultdict的作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值。

1. dict1 = defaultdict(int)
   
2. dict2 = defaultdict(set)
   
3. dict3 = defaultdict(str)
   
4. dict4 = defaultdict(list)
   
5. dict1[2] ='two'
   
6. 
   
7. print(dict1[1])
   
8. print(dict2[1])
   
9. print(dict3[1])
   
10. print(dict4[1])
    
11. 
    
12. 
    
13. 
    
14. 0
    
15. set()
    
16. 
    
17. []
    

复制代码

1. from collections import defaultdict
   
2. 
   
3. def is_family(tree):
   
4.     anscestor = defaultdict(set)
   
5.     for father, son in tree:
   
6.         if father == son: return False
   
7.         if father in anscestor[son]: return False
   
8.         if son in anscestor[father]: return False
   
9.         if anscestor[father] & anscestor[son]: return False
   
10.         anscestor[son] |= {father} | anscestor[father]
    
11.     adam = [person for person in anscestor if not anscestor[person]]
    
12.     return len(adam) == 1

复制代码

可以的，加油