刷题记录帖子

122. Best Time to Buy and Sell Stock II 之前刷过，其实很简单，最重要的就是知道这个股票可以买卖多次一天内，当然要先买再卖。但是这样就只要考虑前后的价格差了。
可以说每一次价格的上涨你都可以赚到。

807. Max Increase to Keep City Skyline 题目不难，就是理解下题意，然后直接简单 N方的方案就行 Greedy 解决，练习下 Python 如何在二维 list 找最小和最大值。

1. 
   
2. class Solution:
   
3.     def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
   
4.         # get the skyline of each row and column
   
5.         row_max = [ max(row) for row in grid]
   
6.         col_max = [ max(col) for col in zip(*grid)]
   
7.         
   
8.         maxSum = 0
   
9.         for i in range(len(grid)): # Row
   
10.             for j in range(len(grid[0])): # Col
    
11.                 #print(grid[i][j])
    
12.                 #print(( max(row_max[i], col_max[j]) - grid[i][j] ))
    
13.                 maxSum += ( min(row_max[i], col_max[j]) - grid[i][j] )
    
14.         return maxSum
    

复制代码

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

1389. Create Target Array in the Given Order 太简单了，其实就是基本的 textbook 问题，如何在 array 中实现插入，用 Python 的内置函数实现。
基本的操作，需要考虑，扩容，在中间插入，在尾部插入，在头部插入等情况比较复杂。
直接 Python list insert 解决，list.insert(index, element)

1. 
   
2. class Solution:
   
3.     def createTargetArray(self, nums: List[int], index: List[int]) -> List[int]:
   
4.         res = []
   
5.         # list.insert(index, element)
   
6.         for num,ind in zip(nums,index):
   
7.             res.insert(ind, num)
   
8.         return res
   

复制代码

49. Group Anagrams 简单题目，需要注意如何设置 dict 的key ，因为 list 不是hashable的所以不能作为 key。

# Python list is not hashable type so using tuple
# How to iterate dictory in Python

Iterating Through Keys Directly
Iterating Through .items()
Iterating Through .keys()
Iterating Through .values()

1. 
   
2. class Solution:
   
3.     def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
   
4.         res = dict()
   
5.         for item in strs:
   
6.             items = [ ch for ch in item]
   
7.             items_tuple = tuple(sorted(items))
   
8.             if items_tuple in res.keys():
   
9.                 res[items_tuple].append(item)
   
10.             else:
    
11.                 res[items_tuple] = [item]
    
12.         ress = list()
    
13.         #print(res)
    
14.         for key,val in res.items():
    
15.             ress.append(val)
    
16.         return ress
    

复制代码

1221. Split a String in Balanced Strings 这道题目其实就是括号匹配问题，只是改变了题目的叙述变得比较陌生。当然括号匹配，课堂上学的是用「栈」这是因为还有别的比如设计计算器的时候有数字等等，所以这道题目简化了。

核心是保持一个变量记录下当前是不是已经匹配了。

1. 
   
2. class Solution:
   
3.     def balancedStringSplit(self, s: str) -> int:
   
4.         balanced = 0
   
5.         res = 0
   
6.         for ch in s:
   
7.             if ch == 'R':
   
8.                 balanced += 1
   
9.             else:
   
10.                 balanced -= 1
    
11.             if balanced == 0:
    
12.                 res += 1
    
13.         return res
    

复制代码

938. Range Sum of BST 写了一个 MidTravese 并没有用到 BST 的特色，自习研究答案的解法，其实可以发现如果改进下搜索策略可以大大加速，BST 本身就是一个好的提示。

We traverse the tree using a depth first search. If node.val falls outside the range [L, R], (for example node.val < L), then we know that only the right branch could have nodes with value inside [L, R].

https://leetcode.com/articles/range-sum-of-bst/

1. 
   
2. class Solution(object):
   
3.     def rangeSumBST(self, root, L, R):
   
4.         def dfs(node):
   
5.             if node:
   
6.                 if L <= node.val <= R:
   
7.                     self.ans += node.val
   
8.                 if L < node.val:
   
9.                     dfs(node.left)
   
10.                 if node.val < R:
    
11.                     dfs(node.right)
    
12. 
    
13.         self.ans = 0
    
14.         dfs(root)
    
15.         return self.ans

复制代码

1. 
   
2. class Solution(object):
   
3.     def rangeSumBST(self, root, L, R):
   
4.         ans = 0
   
5.         stack = [root]
   
6.         while stack:
   
7.             node = stack.pop()
   
8.             if node:
   
9.                 if L <= node.val <= R:
   
10.                     ans += node.val
    
11.                 if L < node.val:
    
12.                     stack.append(node.left)
    
13.                 if node.val < R:
    
14.                     stack.append(node.right)
    
15.         return ans
    

复制代码

1290. Convert Binary Number in a Linked List to Integer 需要熟悉 Python 的二进制操作，因为我其实用的是最简单的基本公式做了二进制和十进制的转换。

1. 
   
2. class Solution(object):
   
3.     def getDecimalValue(self, head):
   
4.         """
   
5.         :type head: ListNode
   
6.         :rtype: int
   
7.         """
   
8.         res = 0
   
9.         node = head
   
10.         bString = ""
    
11.         while (node != None):
    
12.             bValue = node.val
    
13.             bString += str(bValue)
    
14.             node = node.next
    
15.         
    
16.         res = int(bString,2)
    
17.         
    
18.         return res
    

复制代码

1. 
   
2. # Definition for singly-linked list.
   
3. # class ListNode:
   
4. #     def __init__(self, x):
   
5. #         self.val = x
   
6. #         self.next = None
   
7. 
   
8. class Solution:
   
9.     def getDecimalValue(self, head: ListNode) -> int:
   
10.         num = []
    
11.         while head:
    
12.             num.append(head.val)
    
13.             head = head.next
    
14.         numLen = len(num)
    
15.         res = 0
    
16.         for i in range(numLen):
    
17.             res += num[i] * 2 **(numLen - i - 1)
    
18.         return res
    

复制代码

[/i]

1038. Binary Search Tree to Greater Sum Tree 相当精彩的一道题目，对于树的考察特别有意思。
首先是要先去右边找子树，然后进行优化，特别是如何在递归调用的时候巧妙的引入右子树的结果。

1. 
   
2. class Solution:
   
3.     def bstToGst(self, root: TreeNode) -> TreeNode:
   
4.         self.ans = 0
   
5.         def helper(node: TreeNode) -> None:
   
6.             if node is None:
   
7.                 return
   
8.             helper(node.right)
   
9.             self.ans += node.val
   
10.             node.val = self.ans
    
11.             helper(node.left)
    
12.         helper(root)
    
13.         return root
    

复制代码

第二种解法，迭代写法，

1. 
   
2. 
   
3. class Solution:
   
4.     def bstToGst(self, root: TreeNode) -> TreeNode:
   
5.         if root is None:
   
6.             return
   
7.         # If we use iterative methods
   
8.         ans = 0
   
9.         stack = [root]
   
10.         node = root.right
    
11.         while node or stack:
    
12.             while node:
    
13.                 stack.append(node)
    
14.                 node = node.right
    
15.             node = stack.pop()
    
16.             ans += node.val
    
17.             node.val = ans
    
18.             node = node.left
    
19.         return root
    

复制代码

1266. Minimum Time Visiting All Points 很简单的题目，只需要把题意理解即可，其实就是平面移动的题目，理解题意即可。

1. 
   
2. class Solution:
   
3.     def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
   
4.         if len(points) == 0 or len(points) == 1:
   
5.             return 0
   
6. 
   
7.         # line is the shortest
   
8.         res = 0
   
9.         i = 0
   
10.         while i < len(points) - 1:
    
11.             xMoves = abs(points[i][0] - points[i+1][0])
    
12.             yMoves = abs(points[i][1] - points[i+1][1])
    
13.             res += max(xMoves, yMoves)
    
14.             i += 1
    
15.         return res[/i][/i]
    
16. 
    
17. [i][i]

复制代码

[/i][/i]

应该是新出的题目，在 30 天竞赛中的 day 7。
这道题目需要理解下题意，说的不太明确其实是说，key 和 key+1 比较如果有重复，其实 是按照 key 的数目统计。
我在这儿理解了半天才明白啥意思。

1. 
   
2. 
   
3. class Solution:
   
4.     def countElements(self, arr: List[int]) -> int:
   
5.         freq_arr = dict()
   
6.         for num in arr:
   
7.             if num in freq_arr.keys():
   
8.                 freq_arr[num] += 1
   
9.             else:
   
10.                 freq_arr[num] = 1
    
11.         res = 0
    
12.         for key in freq_arr.keys():
    
13.             if (key+1) in freq_arr.keys():
    
14.                 res += freq_arr[key]
    
15.         return res
    

复制代码