leetcode刷题

王小波在<人性的逆转>中写道:

“追求聪明是一种人生态度”;

在<智慧与国学>中, 他又阐述道:

我觉得西方的智者有一股不管三七二十一,总要把自己往聪明里弄的劲头儿。

以上......

断断续续从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.

7赞

文档结构, 二分为算法和数据,
先从算法的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
1赞

因为要分享个人"压箱底"的一点东西, 盼望大家精彩的思路, 不致唱独角戏.

39道能用二分查找解的题目:

1赞

这种刷题的思路看起来不错

刷leetcode就是为了应付面试,跟聪明跟编程水平都没有太大关系

3赞

agreed, 就是投石问路, 瞧瞧哪个话题有人气儿.

本帖收尾.

厉害厉害,我总共刷了不到200道,刷1000道要很多时间跟耐心,楼主v5。

不懂什么叫编程水平,我只知道leetcode刷的好可以进北美大厂,算法很菜,门都没有。

鄙人就在所谓的北美大厂,你说的没错有好多人是刷题进来的。至于水平和刷题的关系么,我讲个真实的故事。前几个月有人贴上来个PR,用了500行写了个错误百出的前缀搜索树(trie)。我问他你的数据集有多大需要前缀搜索树,他说大约40条,以后可能还会更多一些。。。当然这个PR最后给毙掉了,但是有些人刷题刷多了脑子真的会坏掉。

2赞

我觉着, 咱们都点到为止, 高高兴兴做点儿其他事情.

文字毕竟不同于口头表达, 白纸黑字写出来就会留下很多把柄, 导致后面论战不明所以, 无休无止.

周末愉快.

1赞

感觉这不是刷题不刷题的问题,是他本身不够灵活,不能把这个锅甩给刷题吧

Tree Traverse

pre-order(NLR) 前序遍历

org_20190705_112237

preorder(node)
  if (node = null)
    return
  visit(node) # visit在先
  preorder(node.left)
  preorder(node.right)

post-order(LRN) 后序遍历

org_20190705_120714

postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node) # visit在后

in-order(LNR)中序或者顺序遍历

org_20190705_120758

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

Level-order Traversal(层级遍历)

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)

^Summary^,

三种遍历方式的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)

144.Binary Search Preorder Traversal(前序遍历)

Problem

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的方法, 考虑的是如何走下一步.

Solution

# 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)

Morris Traversal solution

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

145.Binary Tree Postorder Traversal (后续遍历)

Problem

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?

Solution

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]

94.Binary Tree Inorder Traversal of Binary Tree(中序遍历)

Problem

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?

Solution

# 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

102. Binary Tree Level Order Traversal(层序遍历)

Problem

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] ]

Solution

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
# 最终实用模板.

103. Binary Tree Zigzag Level Order Traversal(层序遍历)

Problem

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]
]

Solution

# 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

你的帖子已经被社区标记并被临时隐藏。