王小波在<人性的逆转>中写道:
“追求聪明是一种人生态度”;
在<智慧与国学>中, 他又阐述道:
我觉得西方的智者有一股不管三七二十一，总要把自己往聪明里弄的劲头儿。
以上．．．．．．
断断续续从Leetcode中刷了1000多道题目,
题干与不同的解法(py)按照算法分类归入到一个org file里作为数据库.
比如前1000道题目中有三道素数题
Sacha Chua的三字立身哲学: learn–> share–> scale
https://sachachua.com/blog/2012/11/coming-up-with-a-three-word-life-philosophy/
So learn by sharing．
文档结构, 二分为算法和数据,
先从算法的Binary Search开始, 采用螺旋交叉的方法,
每种算法与每种数据结构, 列5~10道题, 少则5道,多则10道; 然后进入下一个算法或者数据结构;
循环一轮过后, 进入第二轮.
Algorithms.Binary.Search
解题不能用蛮力, 不然练一万道题目也无济于事.
从审题到测试,分为四步走,
Sort, Strategy, Solve and Check,
四步是科学解题以及任何问题的步骤.
Sort是将题干中所有的条件都列出来, 其余几步后文陆续分享.
(编辑区排版实在不顺手)
Solution
写成class的形式, 是leetcode模板要求.
class Solution:
def firstBadVersion(self, n):
"""
:type n: int
:rtype: int
"""
lo = 1
hi = n -1
while lo < hi:
mid = (lo+hi) // 2
if not isBadVersion(mid): # good
lo = mid + 1
else:
hi = mid
return lo
这种刷题的思路看起来不错
刷leetcode就是为了应付面试，跟聪明跟编程水平都没有太大关系
agreed, 就是投石问路, 瞧瞧哪个话题有人气儿.
本帖收尾.
厉害厉害，我总共刷了不到200道，刷1000道要很多时间跟耐心，楼主v5。
不懂什么叫编程水平，我只知道leetcode刷的好可以进北美大厂，算法很菜，门都没有。
鄙人就在所谓的北美大厂，你说的没错有好多人是刷题进来的。至于水平和刷题的关系么，我讲个真实的故事。前几个月有人贴上来个PR，用了500行写了个错误百出的前缀搜索树(trie)。我问他你的数据集有多大需要前缀搜索树，他说大约40条，以后可能还会更多一些。。。当然这个PR最后给毙掉了，但是有些人刷题刷多了脑子真的会坏掉。
我觉着, 咱们都点到为止, 高高兴兴做点儿其他事情.
文字毕竟不同于口头表达, 白纸黑字写出来就会留下很多把柄, 导致后面论战不明所以, 无休无止.
周末愉快.
感觉这不是刷题不刷题的问题，是他本身不够灵活，不能把这个锅甩给刷题吧
preorder(node)
if (node = null)
return
visit(node) # visit在先
preorder(node.left)
preorder(node.right)
postorder(node)
if (node = null)
return
postorder(node.left)
postorder(node.right)
visit(node) # visit在后
inorder(node)
if (node = null)
return
inorder(node.left)
visit(node)
inorder(node.right)
levelorder(root)
q ← empty queue
q.enqueue(root)
while not q.isEmpty() do
node ← q.dequeue()
visit(node)
if node.left ≠ null then
q.enqueue(node.left)
if node.right ≠ null then
q.enqueue(node.right)
三种遍历方式的python实现
# Preorder
class Solution1:
def preorderTraversal(self, root: TreeNode) -> "List[int]":
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root: # 检测的点位
res.append(root.val) #每一个node都是一个root
self.dfs(root.left, res) #left first
self.dfs(root.right, res)
# Inorder
class Solution2:
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
res = []
self.helper(root, res)
return res
def dfs(self, root, res):
if root:
self.dfs(root.left, res)
res.append(root.val) # 在中间添加进来.
self.dfs(root.right, res)
# postorder
class Solution3(object):
def postorderTraversal(self, root):
self.res = []
self.dfs(root)
return self.res
def dfs(self, root):
if not root:
return
self.dfs(root.left)
self.dfs(root.right)
self.res.append(root.val)
Given a binary tree, return the preorder traversal of its nodes' values.
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively? iterations的方法, 考虑的是如何走下一步.
# recursion solution
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
#recursilvely
class Solution1:
def preorderTraversal(self, root: TreeNode) -> "List[int]":
res = []
self.dfs(root, res)
return res
def dfs(self, root, res):
if root: # 检测的点位
res.append(root.val) #每一个node都是一个root
self.dfs(root.left, res) #left first
self.dfs(root.right, res)
# iterative solution
class Solution2:
def preorderTraversal(self, root: TreeNode) -> "List[int]":
stack, res = [root], [] # 简练极了.
while stack:
cur = stack.pop()
if cur:
res.append(cur.val)
#right child is pushed first so that left is processed first
stack.append(cur.right) #the sequence.
# 注意这里的顺序呦吼.
stack.append(cur.left)
return res
#Pseudocodes
iterativePreorder(node)
if (node = null)
return
s ← empty stack
s.push(node)
while (not s.isEmpty())
node ← s.pop()
visit(node)
//right child is pushed first so that left is processed first
if (node.right ≠ null)
s.push(node.right)
if (node.left ≠ null)
s.push(node.left)
class Solution(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
node, output = root, []
while node:
if not node.left:
output.append(node.val)
node = node.right
else:
predecessor = node.left
while predecessor.right and predecessor.right is not node:
predecessor = predecessor.right
if not predecessor.right:
output.append(node.val)
predecessor.right = node
node = node.left
else:
predecessor.right = None
node = node.right
return output
Given a binary tree, return the postorder traversal of its nodes' values.
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
class Solution1(object):
def postorderTraversal(self, root):
self.res = []
self.dfs(root)
return self.res
def dfs(self, root):
if not root:
return
self.dfs(root.left)
self.dfs(root.right)
self.res.append(root.val)
# iteration solution
class Solution2(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
if root.left is not None:
stack.append(root.left)
if root.right is not None:
stack.append(root.right)
return output[::-1]
Given a binary tree, return the inorder traversal of its nodes' values.
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
# psudocode
inorder(node)
if (node = null)
return
inorder(node.left)
visit(node)
inorder(node.right)
# recursive solution
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution1:
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
# iteratively psudocode
iterativeInorder(node)
s ← empty stack
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
node ← s.pop()
visit(node)
node ← node.right
class Solution2: #要将第一个点单独拿出来.
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
res, stack = [], []
cur = root
while cur != None or len(stack) > 0:
# while not ( cur == None and len(stack) ==0): #只要有一个就行.
if cur == None:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
if cur != None:
stack.append(cur)
cur = cur.left
return res
class Solution3:
def inorderTraversal(self, root: "TreeNode") -> "List[int]":
stack, res = [root], []
while stack:
cur = stack[-1]
if cur != None:
cur = cur.left
if cur != None:
stack.append(cur)
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
from collections import deque
if root == None: return []
queue = deque([root])
res = []
step = -1
while queue:
step += 1
size = len(queue)
if len(res) < step + 1:
res.append([])
for _ in range(size):
cur = queue.popleft()
res[step].append(cur.val)
#stretch
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
# 最终实用模板．
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
res, queue = [], [(root, 0)]
while queue:
curr, level = queue.pop(0)
if curr:
if len(res) < level+1:
res.append([])
if level % 2 == 0:
res[level].append(curr.val)
else:
res[level]
queue.append((curr.left, level+1))
queue.append((curr.right, level+1))
return res