arts-2019-04-28

Algorithm 算法题

每周至少做一个leetcode 的算法题

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

94. 二叉树的中序遍历

先用递归方法做,先递归处理左边,然后是中间,然后是递归处理右边。

如果用迭代方法呢?

想了一下,需要借助一个访问节点的栈来实现:

  1. 初始化,压栈:当前节点,弹栈时可拓展左分支。
  2. 每次弹栈,可拓展左分支?
    1. 可以拓展,循环拓展,压栈,弹栈时不可继续拓展左分支。
    2. 不可以拓展(说明拓展过了),当前值存到结果集中,右节点压栈,可以拓展左分支。

可以运行,但是否可以优化呢?

发现利用当前节点,当前节点不为空,直接赋值为左节点;当前节点为空,弹栈设为当前节点,值加结果集,当前节点赋值为右节点。

省略是否拓展左分支的判断。

Review 外国文章

阅读并点评至少一篇英文技术文章

程序设计实践,看的英文版,就算做英文技术文章好了。。

这本书里讲到 quick-sort 的实现。

选择 pilot 值,如果每次都选择到极端值,每次只能拆分出0和n-1,分治效果会比较差。

import random
def qsort(alist, start=0, end=None):
  """
  @param: alist: 一个列表
  @start: 排序起始下标
  @end: 排序结束下标
  """
  if end is None:
    end = len(alist) - 1
   
  # 随机选取一个 pilot 值,所有小于它的值被替换到它的左边
  pilot_idx = random.randint(start, end)
  alist[0], alist[pilot_idx] = alias[pilot_idx], alist[0]
  last = 0
  for i in range(1, end + 1):
    if alist[i] < alist[0]:
      last += 1
      alist[i], aliast[last] = alist[last], alist[i]
  alist[0], alist[last] = alist[last], alist[0]
  
  qsort(alist, 0, last - 1)
  qsort(alist, last + 1, end)
  

Technique 技巧总结

学习至少一个技术技巧

可以在工作中思考一下,如何把遇到的事故或者问题,转化成一个个工具。从源头上消除 bug。

Share 思考分享

至少分享一篇有观点和思考的技术文章

最近看了一本掘金小册,老钱的 Redis 深度历险:核心原理与应用实践。

从源码解读操作,有深度,有高度,推荐阅读。

2019-04-28 23:03 17
Comments
Write a Comment