@
caiych 首先多谢你,我对这个题本身要求的需求再思考了一下。"min-max the tree, ascending to descending" 意思是这是一颗从小到大的树,然后去升序到降序。我的疑问是 min-max 和 ascending to descending 不是有点同一个意思吗。好吧,我对树结构的各种理论并不了解,英文水平也是半吊子,所以就不说这个了。
比起这个,我觉得还有个更有意思的问题,凭我的经验来推测(仅仅是我的推测),递归版本实现了,但是非递归(用 Stack 实现)没实现。我想说的是,我也是刚想明白整个流程,昨天看了微博上 左耳朵耗子 的 C++ 实现,只明白用了个栈来做临时存储和协调者,而节点在里面的进出并没有看懂。刚才重新看了一下,才算是真的明白了。你是不是同样会觉得有点吃惊呢?!
我也说一下自己除了上面提到的 detdup 之外的完全由我自己独立设计和实现的算法相关的开源作品:
1.
https://github.com/mvj3/fill_broken_words 填破碎单词,Python实现。
2.
https://github.com/mvj3/phrase_recognizer 英文短语识别,Python实现。
3.
https://github.com/mvj3/region_unit_recognizer 识别 带有省市区等地址的 企事业单位,Python 实现。
4.
https://github.com/mvj3/hangman 猜单词游戏,Ruby实现,两年前的一个做了两天的面试题。
这四个都是非常有意思的问题,就我实际做的经验(很完整的工程实现)来看,1 和 2 较难,大概是两周,3 和 4 相对容易,应该都是两天。前面三个都是由树结构实现的,最后一个是字典实现的(其实有人做了更好的基于树实现的)。
所以这里有个有意思的问题就是,我不能马上看懂二叉树的栈实现,但是我却可以做出以上,不证明了白板面试是非常随机和带偏见的一个测试吗。
@
Heartwork 最好是你可以提供一个基于某算法实现的开源项目(这样大家都可以看到,否则纯算法显示不出工程能力),并具有良好的工程结构,不然懂算法有什么用呢,你说是吧。
@
binux 1、Github 排行榜只能说明流行程度 --- 不过上了一定代码量,并很高 star + fork 的,那基本都是货真价实的了。或者你可以举个反例看看?
2、Homebrew 并不是复杂的软件系统 --- 复杂不复杂都是相对的。不过我愿意承认我大概翻过 Homebrew 代码(当然没有像实际工作项目那么认真,花了很多时间),除了 Formula 的格式,其他基本都没懂。
3、如果你连用栈模拟递归都需要「顿悟」的话,说明你根本不理解递归,甚至不理解函数是怎么执行的。
可能是我文章里说的不够清楚吧,我说的"顿悟"指的是 while 里面的部分,不过这个回复的上面已经解释了我理解这个算法的整个事实过程了。理解用到 stack 确实是即可的,因为我平时工作就经常用到这个技巧。但是 while 里面的逻辑整个放到脑子里,在我的思维里真的是顿悟的,我想这个是人们通常的被别人指点一下的那种体验。当然很可能是我的思维比你的慢,即是 CPU 慢点;当然你也听说过人类最近用成千上万台机器才勉强识别出了猫,所以CPU再快也没用。
我不清楚你对递归和函数的了解水平,但是我还是愿意给出我的理解,虽然可能有错。
什么是递归呢,在我看来,它是人脑思维的一种,和时间空间等一样神秘。人类发现了数据的递归模式(我递归论证了)模式,利用一些可用于稳定执行逻辑的物质(比如CPU器件)来做操作。
函数如何执行呢,摘录一段我在 [The Design Draft Of Human Programming Language](
http://human-lang.org/ ) 的思考笔记 "计算机在本质上就是 过程 + 数据,用 CPU (central processing unit) 来操作 IO (input output) , 也即是用布尔逻辑操作二进制数据。布尔逻辑包括基本的 与,或,非,再进而构建出 与非,或飞,异或 等复合操作(建议通过看 Wikipedia 上的 逻辑函数表示法 得知其相互关系),再进而构建出 集合交集,访问数组某索引的值,等常用数据结构的操作,最后进而构 建出万能的 函数 操作。数据在计算机体系里都表示为离散的 0 1 数字串,进而构建出 Boolean, Integer,Float,Char 等基本数据结构,再进而构建出 String,List,Set,Dict 等高级数据结构,最 后构建出类继承系统,JSON,XML 等复杂业务数据结构。",不知道这样可否让你明白我的理解。