d**********x
发帖数: 4083 | 1 任意两点的距离可以用Floyd-Marshall得到，O(n^3)
或者用Dijkstra求单源最短路径，O(n^2)。
离之 |
|
|
|
|
|
|
|
t*********7
发帖数: 255 | 8 只有你的出发点这个时候才是0,其他全部是INFINITY |
|
i******e
发帖数: 273 | 9 如果节点A到节点B的最短路径经过节点C,那么这条最短路径上从A至C之间的子路径一定
是从节点A到节点C的最短路径。也就是说，从A到B的最短路径是建立在从A到C的最短路
径基础上的，这是为什么每次总是从unfinished节点集合中找当前距离源点最近的节点
的原因。
节点集合应该放到一个按节点和源点距离排序的min priority_queue中。但是由于每个
节点对源点距离是动态变化的，STL和Java的Priority_queue似乎不能处理这种情况，
那位大牛说说应该怎么解决？ |
|
n******n
发帖数: 567 | 10 ls的各位，貌似这题应该是dijkstra吧。。。。。 |
|
|
g*******s
发帖数: 2963 | 12 这问题让我首先想到的是A*, 其次是Dijkstra（类似BFS）
不过当场让我任意一个我估计都得挂。。。。。 |
|
w****x
发帖数: 2483 | 13 挑了一些比较主要的章节, 分先后顺序, 不知道合不合理
Chapter 5: Probability analyze and Randomized Algorithms (Along with
Appendix C1, C2, C3)
Chapter 6: Heap sort
Chapter 7: Quick sort
Chapter 11: Hash Tables
Chapter 12: Binary search trees
Chapter 14.3: Interval tree
Chapter 32: String matching
Chapter 22: Elementary Graph Algorithm
Chapter 24.3: Dijkstra algorithm
Chapter 4: Recurrences
Chapter 9: Medians and order stastics
Chapter 15: Dynamic Programming
Chapter 16: Greedy Algorithm
Chapter 17: Amortized analysis
Ch... 阅读全帖 |
|
w****x
发帖数: 2483 | 14
我根据我个人需求整理了一下比较重要的几章:
Chapter 5: Probability analyze and Randomized Algorithms (Along with
Appendix C1, C2, C3)
Chapter 6: Heap sort
Chapter 7: Quick sort
Chapter 11: Hash Tables
Chapter 12: Binary search trees
Chapter 14.3: Interval tree
Chapter 32: String matching
Chapter 22: Elementary Graph Algorithm
Chapter 24.3: Dijkstra algorithm
Chapter 4: Recurrences
Chapter 9: Medians and order stastics
Chapter 15: Dynamic Programming
Chapter 16: Greedy Algorithm
Chapter 17: Amortized analysis
Chapter... 阅读全帖 |
|
|
|
w****x
发帖数: 2483 | 17
哎呀，我基础太差了，dijkstra是在权重不一样的情况下用的，BFS就可以了，丢死人
了 |
|
|
|
f*******t
发帖数: 7549 | 20 dijkstra变形一下，每次update shortest和second shortest |
|
p*****2
发帖数: 21240 | 21
因为Leetcode就是准备面试用的，不是玩竞赛的。对于面试来说，这题不是原题，原题
在CC150里。面试中遇到的也是CC150的原题。从算法和竞赛来讲，最短路径一般都是找
一条的，参见Dijkstra， 或者找所有pair的，参见Floyd-Warshall，但是所有pair也
是找最小cost而不是所有路径。另外每个pair只需要一个最短就可以了。因此word
ldadder II这题出的很诡异。既不是面试题，又不是竞赛题，我不知道有什么特别的意
义。
通常竞赛来说，输入的规模，时间，空间的要求都说的很详细。一般不需要写code就可
以把算法想的八九不离十，但是这题感觉就是要去死磕，我不太清楚，花那么多时间的
收获是什么。当然你要是觉得值得去做也没什么问题。我肯定不会花这个时间了。 |
|
p*****2
发帖数: 21240 | 22
因为Leetcode就是准备面试用的，不是玩竞赛的。对于面试来说，这题不是原题，原题
在CC150里。面试中遇到的也是CC150的原题。从算法和竞赛来讲，最短路径一般都是找
一条的，参见Dijkstra， 或者找所有pair的，参见Floyd-Warshall，但是所有pair也
是找最小cost而不是所有路径。另外每个pair只需要一个最短就可以了。因此word
ldadder II这题出的很诡异。既不是面试题，又不是竞赛题，我不知道有什么特别的意
义。
通常竞赛来说，输入的规模，时间，空间的要求都说的很详细。一般不需要写code就可
以把算法想的八九不离十，但是这题感觉就是要去死磕，我不太清楚，花那么多时间的
收获是什么。当然你要是觉得值得去做也没什么问题。我肯定不会花这个时间了。 |
|
g****y
发帖数: 2810 | 23 A家的面试默剧了，发一个全程，顺便求靠谱ICC？
A家历时2个月，一月初投出简历后就有人联系。然后就开始了约电面了，到3月onsite
一面电话：
一个中国人，显示介绍亚麻，然后自己的组，再是不一定要你进我们组，问题：
1. 先问了C++和Java的区别
2. 数据结构，问到了队列
3. 写一个队列用一定长度的数组循环，空间不够了就返回满了
二面电话：
老美吧，但是听着说话像老中
1. 数据结构， 问到哈希表
2. 二数求和问题，讲讲思路（就是给一串数和一个值，返回能否用这个数列里的2个
数的和得到这个值）
3. 用哈希表写一个上述问题的代码，当然要O(n)了
onsite 4轮：
那天那个hr总要我去西雅图转转，让我多玩玩，后来问我待几天，我说你们订得明天8
点的机票，我玩个屁啊，她就不说话了
一面
老美，估计是打算招我的那个组的+烙印，估计也是那个组的
1. 行为问题
2. 斐波那契数（输入一个数，输出刚好比这个小的斐数）
3. 我先是O(n)，他不满意，要优化。我推了一遍斐波那契的通项公式（将求和写出一
个矩阵变换，第n项就是矩阵的n次方，通过求矩阵的本征值可以得到矩... 阅读全帖 |
|
l*****a
发帖数: 14598 | 24 转载一个牛人的经验.
发信人: wwwyhx (wwwyhx), 信区: JobHunting
标 题: Re: 看来还是要看算法导论啊
发信站: BBS 未名空间站 (Sun Nov 18 23:33:22 2012, 美东)
我根据我个人需求整理了一下比较重要的几章:
Chapter 5: Probability analyze and Randomized Algorithms (Along with
Appendix C1, C2, C3)
Chapter 6: Heap sort
Chapter 7: Quick sort
Chapter 11: Hash Tables
Chapter 12: Binary search trees
Chapter 14.3: Interval tree
Chapter 32: String matching
Chapter 22: Elementary Graph Algorithm
Chapter 24.3: Dijkstra algorithm
Chapter 4: Recurrences
Chapter 9: Medians and... 阅读全帖 |
|
n*******w
发帖数: 687 | 25 recrusion试过，5个字母的单词都算不出来。假设字典50w单词，长度为5的单词只有几
千个。
这题我这么算的
1 先从字典里边选出长度为要找的单词的所有单词
2 建立dict，key是单词本身，value是从start到这个单词的路径长度，初始值为
integer的最大值，假设是MAX。
3 dict[start] = 0； dict[end] = MAX
4 对于dict里边每一个单词cur_word，
如果dict[cur_word] != MAX， 改变cur_word的任一个字符得到next_word，看next_
word是不是在dict里边，如果存在则更新dict[next_word] =
min( dict[next_word], 1+ dict[cur_word] )
5 如果step 4没有任何改变，退出。输出dict[end]
实际上DP，也可以看做是，建图并且Dijkstra一起做。
python写的话，不超过20行。运行时间在半分钟之内。 |
|
n*******w
发帖数: 687 | 26 这个好。。。可以当做标准答案。
没必要严格的Dijkstra。 |
|
a*******n
发帖数: 64 | 27 Given the Dijkstra's algorithm (finding the shortest path) and a acylic
graph, how can we modify the graph to find the longest path?
Didn't think of any good answer to this one? Anyone has an idea? |
|
S**I
发帖数: 15689 | 28 Didn't notice "acyclic"；both longest path and shortest path on a directed
acyclic graph can be solved in linear time by using topological ordering.
Dijkstra's algorithm is not necessary. |
|
n***t
发帖数: 76 | 29 转一个帖 聊以慰藉
劳资六年前开始搞ACM啊！！！！！！！！！！
从此踏上了尼玛不归路啊！！！！！！！！！！！！
谁特么跟劳资讲算法是程序设计的核心啊！！！！！！
尼玛除了面试题就没见过用算法的地方啊！！！！！！
谁再跟劳资讲算法之美算法的力量，劳资一本算法导论拍死你啊！！！！！！！！
那是搞ACM的入门书啊！！！！特么的入门书就一千多页啊！！！！！！！
还没有习题答案啊，学完了你特么都不知道自己到底会不会啊有木有！！！！！！
然后你就得看lrj的黑书啊！！！！！！还是特么的没有习题答案啊！！！！
那书难的一B啊！！！！人家一个“显然”得出的结论够你想一礼拜啊有木有！！！！
一个课后题够你想几个月啊有木有！！！！
然后还有一堆堆的书啊！！！！每一类算法都足够写一本书啊！！！！
每本都是砖头一样啊！！！！还都特么是英文的啊！！！！
也有中文翻译版啊！！！！！！翻译得跟屎一样啊！！！！
你看的时候得把它再变回英文才能懂啊！！！！！！有木有！！！！！！
ACM的题目类型是没有范围的啊！！！！！！
动态规划有木有！！！！数据结构有木有！！！！
图论有木有！！！！！！计算几何有木有！！！！！！
... 阅读全帖 |
|
h**6
发帖数: 4160 | 30 Louzhu can try to write Dijkstra algorithm |
|
r*******e
发帖数: 7583 | 31 我用的dijkstra+backtracking可以过large，不过也1000ms了 |
|
J****3
发帖数: 427 | 32 觉得就是dijkstra 把新节点加入集合时候对权值进行判断的时候加上条件？ |
|
p*****3
发帖数: 488 | 33
dijikastra这里不成立啊，最优子结构被破坏了
1 1 1 extra_cost(b,d) == 100000000
a ---> b --->c--->d
| ^
| |100
-------------e
100
dijkstra 不work啊 |
|
I******c
发帖数: 163 | 34 如果我没有记错的话，这种点对点求最短路径问题就时间效率而言等同于single-
source最短路径。后者可以用Dijkstra或者bellmen-ford来求解。不过我感觉直接修改
这两个算法来解题不容易。
我觉得可以不考虑extra weight的情况下先求最短路径。如果得到的最短路径没有
extra weight，那么这就是答案。不然的话，可以把原图里能够引起extra weight的点
去掉，来求最短路径(要分不同情况分别求。如点A，点B同时出现的话会造成extra
weight，那么就把点A去掉求一次，把点B去掉再求一次）.并和最开始求的带有extra
weight的最短路径比较来决定最后的最短路径。
如果造成extra weight的条件很复杂，可能需要别的算法。 |
|
n******n
发帖数: 567 | 35 dijkstra, 需要内存比较大，precalculate存在db里 |
|
r**h
发帖数: 1288 | 36 五分钟写个dijkstra？这个绝对是大牛。。。 |
|
x***y
发帖数: 633 | 37 Convert this to a graph problem by using a node for a set of cards, and a
directed edge between 2 nodes if the first set of cards can be transformed
to 2nd set by playing the card once.
Then, this is a Dijkstra problem. |
|
s********u
发帖数: 1109 | 38 还只是胡思乱想，也不太严谨。欢迎指正。（只讨论目前算法面试题一般涵盖的范围）
前言：
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp，只是效率不提高，还增加了space cost而已。（
所以这个原则应该是“适合用dp”，而不是“可以用dp”
另外且不说最优子结构，overlap有时候也较难判断，比如boggle game这个，路径一定
是有重复的，但是
subproblem却未必，因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外，就算是有overlap，从实用的角度来说，dp（bottom-up）未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7），bool cover( root, p )本身是
单纯的DFS访问，subproblem不存在overlap；但对整个问题而言，cover不停的调用，
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS，递归函数中调用了递归... 阅读全帖 |
|
s********u
发帖数: 1109 | 39 嗯，在理论上我是这么总结的：
**Divide and conquer :** 将问题分成几个部分，每一部分问题互相不重叠，假定每
个部分都可以得到解决进行递归调用，合并每一部分的结果。例如Merge Sort,Quick
Sort。
**Dynamic Programming**：对于具备最优子结构以及子问题重叠特性的问题，尽可能
不重复计算每个subproblem，将计算结果存储下来，以确定后驱问题的结果。与贪心算
法的区别是，在计算后驱问题时，可能会reconsider前驱问题的解，从而改变全局path
。
**Greedy Algorithm** : 当前问题的最优解只取决于前驱问题的最优解，即局部最
优解推广至全局最优解。如Dijkstra算法。
**Backtracking**： 一种暴力（穷举）的深度优先搜索法，直至检索到节点空间的尽
头。Tree或Graph的DFS，是backtracking的special case。
但实际上很多问题就算满足dp的条件，用dp却非常繁琐，比如8皇后问题，或path sum
问题。是可以用dp做，但实际上没必要。用b... 阅读全帖 |
|
s***e
发帖数: 403 | 40 就是一个图论的dijkstra问题。
始态必须经过过渡态才能到达终态而已。 |
|
I*****D
发帖数: 133 | 41 phone interview，这大概是我面过的最奇葩的面试了，
问的是
Q. 你懂哪些data structure?
A. 愣了一下:tree, graph, map, ..
然后被打断 good good 问下一个
Q. 你懂哪些distribution?
A. Gaussian, Uniform, ...
然后good 继续下一个问题
Q. 你懂哪些算法
A. BFS, DFS,etc.
Q. 你懂哪些图算法
A. Dijkstra, Bellman-ford
Q. Tree有哪些
A. Binary Tree, Binary Search Tree, Black-Red, etc.
Q. 你对ML有什么了解
A. Regression, Classification, SVM,
。。。
等等都是非常概念性的问题，并不深究里边的东西，点到即止，没有一道程序题，感觉
只要拿着算
法书的目录照念就可以了
然后收到拒信 |
|
|
|
c*****w
发帖数: 50 | 44 DP seems not work because history dependent path, use variation of Dijkstra
(similar to bottleneck shortest path) |
|
e********3
发帖数: 18578 | 45 记下来以后，你再重新读一遍给他听，这样等于他给你double check了。
Interviewer: My email is d******[email protected]
Interviewee: Great, I have your email address as d as Dog, i as Inch, j as
Jeep, k as Kite, s as Six, t as Test, r as Reason, a as Apple, at gmail dot
com, is that right?
Interviewer: Exactly.
Interviewee: Thank you so much for your patience! Enjoy the rest of your day
! Bye bye. |
|
e********3
发帖数: 18578 | 46 这么简单的问题都有不少人写不出来？靠，信心立刻超级爆棚呀。最近把经典算法写了
一轮，quicksort, mergesort, 8 queen, Dijkstra, string permutation什么的，感
觉稍微复习了一下基本上自己摸索40分钟之内都没有bug全部最优化实现了，当年读博
士的时候算法全班，前三的底子还是有点用的，哈哈。 |
|
s******u
发帖数: 550 | 47 正解 用Dijkstra's algorithm
用maximun flow. |
|
q****m
发帖数: 177 | 48 感觉可以用Dijkstra, 但是不知道对不对
,3 |
|
n******n
发帖数: 567 | 49 我投find median ,不带用递归的
Word ladder有点没意思，可以改一下题换成dijkstra更好 |
|
|
