给定一个整数序列,判断这个序列是否可以构成某颗搜索二叉树(BST)的前序遍历结果。朴素的做法是O(N^2),2014年面试的时候遇到过此题,当时只给出了O(NlogN)的解法,现在给出O(N)解法。

阅读全文 »

Min Stack:支持getMin()操作的栈,前不久刚写过O(1)时间,O(N)额外空间的解法,并扩展到了Min Queue。详见Queue With MAX

昨晚在GeeksforGeeks上面看到了一篇文章Design a stack that supports getMin() in O(1) time and O(1) extra space,可以仅用O(1)时间、O(1)额外空间解决此问题。这个解法非常的genius,在此介绍这个方法。

阅读全文 »

纳木错圣牛

2015年主要做了如下几件事

  1. 骑行川藏线、环台湾岛骑行、参加台北马拉松
  2. 在台湾国立成功大学交换一学期
  3. 在App Store上线了自己的第一款APP
  4. 随队参加ACM World Final,现场见证了Tourist AK壮举
  5. 第一次走出国门,泰国、迪拜、摩洛哥
阅读全文 »