刷题记录帖子

1313. Decompress Run-Length Encoded List ， Easy 题目，主要是理解下题意，然后熟练使用 Python 的语法

1281. Subtract the Product and Sum of Digits of an Integer

# How to extract each digit in a num

1.         while ( num > 0 ):
   
2.             tmp = num //10
   
3.             digits = num - tmp * 10
   
4.             num = tmp
   

复制代码

136. Single Number 这道题目并不在于解答而在于如何高效的求解答案，一题多解, https://www.geeksforgeeks.org/find-element-appears-array-every-element-appears-twice/。

(1) 用 hash 统计出现频率，time  O(n), space, O(n)
(2) XOR, time  O(n), space, O(1)
(3) Set, time  O(n)， Iterating over a list is O(n) and adding each element to the hash set is O(1), so the total operation is O(n)，最后返回结果其实是简单的两步计算不过也都是 O（n）.  space, O(n)

202. Happy Number  其实还是很简单的，就是简单的操作，当然多知道一些数学也可以知道更多的解法。
在 HashSet 中查找看是否存在，若不存在则加入表中，若存在则跳出循环，并且判断此数是否为1，若为1返回true，不为1返回false

1. class Solution:
   
2.     def isHappy(self, n: int) -> bool:
   
3.         histroy = set()
   
4.         while n != 1:
   
5.             n = sum([int(x)**2 for x in str(n)])
   
6.             if n not in histroy:
   
7.                 histroy.add(n)
   
8.             else:
   
9.                 return False
   
10.         return True

复制代码

53. Maximum Subarray

这道题目真是很经典，推荐几个视频还是做的很不错的。https://blog.ihuxu.com/xiaoxu-ex ... 3-maximum-subarray/

https://www.youtube.com/watch?v=7J5rs56JBs8

https://www.youtube.com/watch?v=2MmGzdiKR9Y

（1）暴力 n 平方的方法搜索
（2）一维 dp，记住 dp 的含义，这里是 到第 i 位元素的时候最大的 sum， 如果 sum 不足够大那么还不如，不 包括之前的元素，直接自己成为答案
（3）divide and conquer， 分成三部分，左半部分，右半部分，和 如果包含中间元素的解法。

1282. Group the People Given the Group Size They Belong To 很简单的题目，就是 HashMap 的运用。

1302. Deepest Leaves Sum 一句话概括怎么解决， Level Traversal 那么怎么知道到了最深的一层？ 很简单，记录下 前一层的 node， 如果现在这一层没有任何 node 了，就说明到了最深的一层了。

1. class Solution:
   
2.     def deepestLeavesSum(self, root: TreeNode) -> int:
   
3.         node_queue = [root] # current_layer
   
4.         
   
5.         while node_queue:
   
6.             previous_layer = node_queue # record previous layer
   
7.             # generate next level of nodes
   
8.             node_queue = []
   
9.             for node in previous_layer:
   
10.                 if node.left:
    
11.                     node_queue.append(node.left)
    
12.                 if node.right:
    
13.                     node_queue.append(node.right)
    
14.         res = 0
    
15.         for node in previous_layer:
    
16.             res += node.val
    
17.         return res

复制代码

1315. Sum of Nodes with Even-Valued Grandparent 还是 level transverse。 当然这次需要记住 祖父layer 和 父亲 layer

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, x):
   
4. #         self.val = x
   
5. #         self.left = None
   
6. #         self.right = None
   
7. 
   
8. class Solution:
   
9.     def sumEvenGrandparent(self, root: TreeNode) -> int:
   
10.         # still level traverse
    
11.         if not root:
    
12.             return 0
    
13.         current_layer = [root]
    
14.         parent_layer = []
    
15.         grandparent_layer = []
    
16.         res = 0
    
17.         # populate parent layer
    
18.         parent_layer = current_layer
    
19.         current_layer = []
    
20.         for node in parent_layer:
    
21.             if node.left:
    
22.                 current_layer.append(node.left)
    
23.             if node.right:
    
24.                 current_layer.append(node.right)
    
25.         # populate grandparent layer
    
26.         if not parent_layer:
    
27.             return 0
    
28.         grandparent_layer = parent_layer
    
29.         parent_layer = current_layer
    
30.         current_layer = []
    
31.         for node in parent_layer:
    
32.             if node.left:
    
33.                 current_layer.append(node.left)
    
34.             if node.right:
    
35.                 current_layer.append(node.right)
    
36.         if not grandparent_layer:
    
37.             return 0
    
38.         while current_layer:
    
39.             for node in grandparent_layer:
    
40.                 if node.val % 2 == 0:
    
41.                     tmp = []
    
42.                     if node.left:
    
43.                         tmp.append(node.left)
    
44.                     if node.right:
    
45.                         tmp.append(node.right)
    
46.                     for node in tmp:
    
47.                         if node.left:
    
48.                             res += node.left.val
    
49.                         if node.right:
    
50.                             res += node.right.val
    
51.             grandparent_layer = parent_layer
    
52.             parent_layer = current_layer
    
53.             current_layer = []
    
54.             for node in parent_layer:
    
55.                 if node.left:
    
56.                     current_layer.append(node.left)
    
57.                 if node.right:
    
58.                     current_layer.append(node.right)  
    
59.         for node in grandparent_layer:
    
60.             if node.val % 2 == 0:
    
61.                 tmp = []
    
62.                 if node.left:
    
63.                     tmp.append(node.left)
    
64.                 if node.right:
    
65.                     tmp.append(node.right)
    
66.                 for node in tmp:
    
67.                     if node.left:
    
68.                         res += node.left.val
    
69.                     if node.right:
    
70.                         res += node.right.val
    
71.         return res
    

复制代码

507. Perfect Number 注意下题目的条件，其实很简单就是注意下 i * i == num 的时候需要单独处理，其实不需要，可以直接判断下，是不是 i == num / i。
同时注意下 edge case 的处理，比如负数就要排除。
记一下结论也很有帮助，其实在 可能的范围内，只有 4 个数字是 Perfect Number  

6, 28, 496, 8128, 33550336

1. class Solution:
   
2.     def checkPerfectNumber(self, num: int) -> bool:
   
3.         import math
   
4.         if num == 1:
   
5.             return False
   
6.         if num <= 0:
   
7.             return False
   
8.         sumdivs = 1
   
9.         for i in range(2, int(math.sqrt(num))+1):
   
10.             if (num % i == 0):
    
11.                 if i != num / i:
    
12.                     sumdivs += i
    
13.                     sumdivs += num / i
    
14.                 else:
    
15.                     sumdivs += i
    
16.         return sumdivs == num
    

复制代码

283. Move Zeroes 其实还是 double pointers ， 一个指着数组，一个指着下一个 non-zeros 的位置，当然需要小心 edge case 全是0，全是 1， 只有一个， 只有两个数字，然后需要边界条件判断。

1. 
   
2. class Solution:
   
3.     def moveZeroes(self, nums: List[int]) -> None:
   
4.         """
   
5.         Do not return anything, modify nums in-place instead.
   
6.         """
   
7.         if len(nums) == 1:
   
8.             return
   
9.         # moving next non zero ones to replace zeros
   
10.         right_nonzeros = 0
    
11.         for i in range(len(nums)):
    
12.             if nums[i] == 0:
    
13.                 right_nonzeros = i
    
14.                 while nums[right_nonzeros] == 0 and right_nonzeros < len(nums) - 1:
    
15.                     right_nonzeros += 1
    
16.                 # swap
    
17.                 nums[i], nums[right_nonzeros] = nums[right_nonzeros], nums[i]
    
18.             if right_nonzeros == len(nums) - 1:
    
19.                 return
    
20.         return[/i][/i][/i][i][i][i]
    

复制代码

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