程序员面试的 Top10 算法概念汇总

[ksex]

程序员面试的 Top10 算法概念汇总

译文地址： http://codecloud.net/top-10-algorithms-for-coding-interview-447.html
原文地址： http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

[yangff]

class TreeNode{
int value;
TreeNode left;
TreeNode right;
}
……现在很少这样声明二叉树了。
class TreeNode{
int value;
TreeNode ch[2];
}
简单轻松。

[felix021]

“动态编程”…… 这翻译够烂的。

[misaka]

直接看原文吧。

[bengol]

@felix021 搞翻译的人这是在秀下限

[haohaolee]

@yangff 那也不是吧。left right更可读，用0 1访问是怎么回事

[yangff]

@haohaolee 比如说……
左孩子ch[0]右孩子ch[1]……
好扯淡啊
没关系换个说法。


如果balabala访问左孩子xxx，否则访问右孩子
ch[balabala^1]
哎……
继续，如果A访问左孩子的右孩子，否则访问右孩子的左孩子
ch[A^1]->ch[A]

如果我在父节点的左边，就把父节点放到我的右边，如果我在父节点的右边，就把父节点放到我的左边。（平衡树旋转中的一步）

int getDir(){
return this == p->ch[1];
}

ch[p->getDir()^1] = p;p->p = this;

进而完整的rotate只要8～9行就能写完QAQ，真是简单又实惠的技巧～还不用担心左旋右旋写错了～

找兄弟～

p->ch[getDir()^1]

但是总感觉没有left和right好不爽啊。

node* left(){
return ch[0];
}

node* right(){
return ch[1];
}

[felix021]

@yangff 友情提醒一下你最后两个函数是编译不了的。

[yangff]

@felix021 可以啊）

[felix021]

噢 我说反了。是你1L留的那个编译不过， TreeNode* ch[2] 才对。

[yangff]

@felix021 0 0,1L那个听说是Java不用写*？反正我不会 ）

[felix021]

@yangff 好吧 所以你是1L java 6L C了……跳跃了点

[yangff]

@felix021 暴露了完全不会用Java的本质 匿了）

[luikore]

原文也不怎么样, breadth 都能拼错成 breath ...