刷题记录帖子

292. Nim Game 特别简单的题目，想清楚这个策略是怎么 work 的就可以，其实最关键的部分就是 每 4 个石头是一组。
答案一旦想清楚就特别简单。

701. Insert into a Binary Search Tree 树的基本操作，两种写法都应该掌握，
这道题目的 recursion 更加巧妙值得自习品味。如何借助 None 返回新的 节点而不需要显式生成 TreeNode
Iterative methods

1. 
   
2. # Definition for a binary tree node.
   
3. # class TreeNode:
   
4. #     def __init__(self, x):
   
5. #         self.val = x
   
6. #         self.left = None
   
7. #         self.right = None
   
8. 
   
9. class Solution:
   
10.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    
11.         if root is None:
    
12.             root.val = val
    
13.             return root
    
14.         node = root
    
15.         prev_node = root
    
16.         while node:
    
17.             if node.val < val:
    
18.                 prev_node = node
    
19.                 node = node.right
    
20.             else:
    
21.                 prev_node = node
    
22.                 node = node.left
    
23.         new_node = TreeNode(val)
    
24.         if prev_node.val < val:
    
25.             prev_node.right = new_node
    
26.         else:
    
27.             prev_node.left = new_node
    
28.         return root
    

复制代码

1. 
   
2. # Definition for a binary tree node.
   
3. # class TreeNode:
   
4. #     def __init__(self, x):
   
5. #         self.val = x
   
6. #         self.left = None
   
7. #         self.right = None
   
8. 
   
9. class Solution:
   
10.     def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    
11.         if root:
    
12.             if root.val > val:
    
13.                 root.left = self.insertIntoBST(root.left, val)
    
14.             if root.val < val:
    
15.                 root.right = self.insertIntoBST(root.right,val)
    
16.             return root
    
17.         else:
    
18.             return TreeNode(val)
    

复制代码

535. Encode and Decode TinyURL 这道题目其实很简单，并不是特别难.
但是确实入门 system design 的好题目，这里的很多观点和思路都非常好，适合转移到 system design 的思路里面。
比如我们如何设计 key，如何 id。当然在刷题阶段，这道题目过了就行，心里记住 system design 的很多原则和思路即可。
当然如何记住几个 Python 的惯用法也是很有用的，比如

letters = string.ascii_letters + string.digits
res += letters[random.randint(0,61)]

1. 
   
2. class Codec:
   
3.     def encode(self, longUrl: str) -> str:
   
4.         """Encodes a URL to a shortened URL.
   
5.         """
   
6.         import string
   
7.         import random
   
8.         self.URLtable = {}
   
9.         letters = string.ascii_letters + string.digits
   
10.         suffix = "http://tinyurl.com/"
    
11.         def rand6letters() -> str:
    
12.             res = ""
    
13.             for i in range(6):
    
14.                 res += letters[random.randint(0,61)]
    
15.             return res
    
16.         tmp = rand6letters()
    
17.         while True:
    
18.             if tmp not in self.URLtable:
    
19.                 self.URLtable[tmp] = longUrl
    
20.                 break
    
21.             else:
    
22.                 tmp = rand6letters()
    
23.         return suffix+tmp
    
24.             
    
25. 
    
26.     def decode(self, shortUrl: str) -> str:
    
27.         """Decodes a shortened URL to its original URL.
    
28.         """
    
29.         key = shortUrl.split('/')[-1]
    
30.         return self.URLtable[key]
    
31. 
    
32. # Your Codec object will be instantiated and called as such:
    
33. # codec = Codec()
    
34. # codec.decode(codec.encode(url))
    

复制代码

876. Middle of the Linked List  之前做过，还是 slow fast pointer 解决。当然需要注意指针不能越界。

155. Min Stack 这道题目还是挺好的，关键思路就是一个，需要记录下当前值，插入时候的 min value。 通过记录信息解决问题。

两种思路，一个是 two stack， 一个记录 x， 一个记录 current x‘s min； 另一个就是直接存 tuple。

543. Diameter of Binary Tree 很经典的题目。如何在递归中利用 tree 的特性解决 图的内部问题。
这里最重要的设计出题目要求的答案，总共三种可能的 case 存在 最大的 diameter。
（1） 在左子树中
（2） 在右子树中
（3） 在经过 root 连接了左右子树的路径中

所以题目借助一个 辅助函数然后，不断调用递归即可 dfs。

1. 
   
2. 
   
3. class Solution:
   
4.     def diameterOfBinaryTree(self, root: TreeNode) -> int:
   
5.         
   
6.         self.res = 0
   
7.         
   
8.         def helper(root: TreeNode) -> int:
   
9.             if not root:
   
10.                 return 0
    
11.             depth_left = helper(root.left)
    
12.             depth_right = helper(root.right)
    
13.             # if the path cross root
    
14.             self.res = max(self.res, depth_left + depth_right)
    
15.             return 1+max(depth_left, depth_right)
    
16.         helper(root)
    
17.         return self.res
    

复制代码

6. ZigZag Conversion 其实就是 一个 从 0 ～ num-1 在回到 0 的数字循环插入数字。

但是题目非常误导人，如果读不懂题意就栽了。所以还是多多提高理解能力。
同时一个知识点，如何实现 0 ～ N ～ 0 的方法，我是用 mod 来做，但是看答案看到这么一个更加高效的方法，记录下。
通过改变 step 来做，直接从 +1 到 -1 高明～！

1. 
   
2. class Solution:
   
3.     def convert(self, S: str, R: int) -> str:
   
4.         if R == 1 or R > len(S):  # corner case
   
5.             return S
   
6.         res, i, step = ['' for r in range(R)], 0, 0  # a string for each line
   
7.         for s in S:
   
8.             res[i] += s
   
9.             if i == 0:  # first row
   
10.                 step = 1  # down
    
11.             if i == R - 1:  # last row
    
12.                 step = -1  # up
    
13.             i += step
    
14.         return "".join(res)
    

复制代码

[/i]

1046. Last Stone Weight 还是很简单的题目，我是通过排序做的，不过参考了下别人的答案还可以用 heap ，还是数据结构解决问题的思路。

记录下 Python 如何使用 heap， import heapq

1. 
   
2. import heapq class Solution:
   
3.      def lastStoneWeight(self, stones: List[int]) -> int:
   
4.          stones = [-val for val in stones]
   
5.          heapq.heapify(stones)
   
6.          while len(stones) > 1:
   
7.              x1 = heapq.heappop(stones)
   
8.              x2 = heapq.heappop(stones)
   
9.              if x1 != x2:
   
10.                  heapq.heappush(stones,-abs(x1-x2))
    
11.          if len(stones) == 0:
    
12.              return 0
    
13.          return -stones[0]
    

复制代码

今天刷了一道新的 30 天测试题，还是很 简单的，其实就是先统计左移总次数再统计右移总次数，最后得到 net shifts，再根据 reminder of modulo 得到具体的移动距离，最后组合字符串，不过这里需要小心。首先 Python 取字符串并不会取 s[a:b] 其实是取 s[a] 到 s[b-1] 所以需要注意。

238. Product of Array Except Self 每日签到题目，还是比较容易的，非常经典，其实就是不用除法，然后通过两边遍历得到左边数字乘积和右边数字乘积。