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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 3779 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

Top10

程序员

汇总

13 条回复 • 1970-01-01 08:00:00 +08:00

yangff

2013-12-15 13:20:45 +08:00

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

felix021

2013-12-15 14:07:47 +08:00

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

misaka

2013-12-15 14:14:53 +08:00 via Android

直接看原文吧。

bengol

2013-12-15 15:07:58 +08:00

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

haohaolee

2013-12-15 16:00:32 +08:00 via Android

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

yangff

2013-12-15 16:14:58 +08:00

@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

2013-12-15 19:40:49 +08:00

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

yangff

2013-12-15 20:10:48 +08:00

@felix021 可以啊）

felix021

2013-12-15 20:18:01 +08:00

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

yangff

2013-12-15 20:29:38 +08:00

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

felix021

2013-12-15 20:44:42 +08:00

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

yangff

2013-12-15 20:49:21 +08:00

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

luikore

2013-12-16 03:44:46 +08:00

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