a***y
发帖数: 547 | 1 第一题，可以一步或者两步的上楼梯，一共有多少种上法
如何在stack里面实现min（）
怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢 |
g***s
发帖数: 3811 | 2
DP
return root (assume it is a min-heap)
DP
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
i**9
发帖数: 351 | 3
怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
在bfs同时可以加 greedy的思路来optimization,就是算下一步所有reachable单词里跟
destination 单词的 distance,哪个最近就先走哪个
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
a***y
发帖数: 547 | 4
是单
But it is BFS, the access order are just in one level, right? I am not sure
whether this would bring much speed up. Anyway, thanks.
【在 i**9 的大作中提到】
:
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
: 在bfs同时可以加 greedy的思路来optimization,就是算下一步所有reachable单词里跟
: destination 单词的 distance,哪个最近就先走哪个
|
f*****w
发帖数: 2602 | 5
Fibonacci ?
没很明白 难道用两个stack 全倒出来一遍？
heuristic, 就number of different chars 好了
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
D*********y
发帖数: 876 | 6 第一个是DP
S[n]=S[n-1]+S[n-2]，就是Fibbonaci
第二个是单独弄一个stack,里面放上有史以来的min(需要extra storage)
或者改变stack里面每一个node的结构，让这个node除了放原来的data以外，还存一个min value (不需要额外内存)
第三题是做一个BFS
第二题和第三题的solution, careercup书上都有
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
a******e
发帖数: 95 | 7
A* should work, and then there are tons of optimizations on A* (e.g., IDA*)
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
c******w
发帖数: 102 | 8 第一题就是Fibonacci数列。 比如你当前要求走到第n级楼梯的走法F(n), 那么你需要
完成知道走到n-1和n-2级的走法 F（n-1）和F（n-2）。 也就是F（n） = F（n-1） +
F（n-2）。
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
i**********e
发帖数: 1145 | 9 第二题是 wordladder 游戏的实现问题，本版有讨论过。
最基本的实现方法是用 BFS，但是level越深就越多节点。
利用一些剪枝 可以进行优化
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
g*********s
发帖数: 1782 | 10
classical. Fibonacci.
classical
bfs + greedy as someone mentioned earlier. this is actually a*.
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
C***y
发帖数: 2546 | 11 建一个图（或者想象有这么一个图）
起点是原来的单词
终点是目标单词
其他顶点是联通的条件是距离为一
可以用经典的greedy算法找最短路径
也可以用DP做
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
k*p
发帖数: 1526 | 12 电面就这么难，太变态了，好可怕啊
【在 a***y 的大作中提到】
: 第一题，可以一步或者两步的上楼梯，一共有多少种上法
: 如何在stack里面实现min（）
: 怎么把一个单词一步一步的变成另一个单词，每次只能变一个字母，中间结果也要是单
: 词。我说用bfs，他一直在问有没有什么optimization在里面。我也没说个所以然。他
: 还让我把实现的code发给他，可是我啥idea都没有啊，大家有什么建议么？多谢
|
l*****a
发帖数: 14598 | 13 这是一个很经典的问题
但是有人在面试中见到过吗？问这个也太没意思了吧
【在 C***y 的大作中提到】
: 建一个图（或者想象有这么一个图）
: 起点是原来的单词
: 终点是目标单词
: 其他顶点是联通的条件是距离为一
: 可以用经典的greedy算法找最短路径
: 也可以用DP做
|
s***n
发帖数: 459 | 14 精辟
个min value (不需要额外内存)
【在 D*********y 的大作中提到】
: 第一个是DP
: S[n]=S[n-1]+S[n-2]，就是Fibbonaci
: 第二个是单独弄一个stack,里面放上有史以来的min(需要extra storage)
: 或者改变stack里面每一个node的结构，让这个node除了放原来的data以外，还存一个min value (不需要额外内存)
: 第三题是做一个BFS
: 第二题和第三题的solution, careercup书上都有
|
