g**********y 发帖数: 14569 | 1 2. 先merge sort file, 然后merge intersection.
3. 这是个Dijkstra算法的变形,从set = {2^0*3^0*5^0 = 1}出发,每次取最小的数,
然后把该数的2*a, 3*a, 5*a放进set里(需要一个visited[][][]来记录避免重复), 然
后再取最小的重复以上步骤,直到k步。
you
will |
|
r*******g 发帖数: 1335 | 2 第二题merge sort的话岂不是很耗费硬盘空间
第三题我很好奇的是如何每次取最小的数,你说的dijkstra不是最短路径算法么,貌似
你说的是一次explor很多数,然后选最小一个,这样平坦下来开销小?explor的数还可
以放到heap里面。 |
|
S**I 发帖数: 15689 | 3 In Dijkstra all the neighbors of a current node are known, but in this problem they are
unknown, so how do you find the smallest neighbor? |
|
d*******d 发帖数: 2050 | 4 这题书上不是给了答案么?书上答案挺好的啊.那用得上dijkstra啊.
到B
和B |
|
g**********y 发帖数: 14569 | 5 哪本书上的答案?能贴一下吗?不需要经典Dijkstra的code, 几行就行,但是思路是一
样的,本质就是贪心。 |
|
B*******1 发帖数: 2454 | 6 我的第一想法是
方法1:
根据矩阵建立一个adj matrix,
然后对每一个s,跑dijkstra,算到每一个a的最短距离,
对于每一个a,如果新的s算出来的最短距离更加小,就更新它的最短距离。
方法2:
建立adj matrix
跑flyoyd- warshal, 算每2点之间最短距离,
对每一个a,找到所有s的距离中最小的那一个。 |
|
s***h 发帖数: 662 | 7 来自主题: JobHunting版 - 一个算法题 我碰到一个这样的题目,
You have a map of n cities connected by routes. A route (u,v) has length
d(u,v). you are in city s now and want to go to city t in m days. additional
constraints are:
1. you have maximum travel distance f(d), d from 1 to m.
2. you have cost c(u) to stay overnight in city u.
now it asks you to come up with a plan that
1. starts from s, takes exactly m days to go to t.
2. spending exactly one night at each city you pass.
3. do not travel more than f(d) on day d.
4. minimize the total c... 阅读全帖 |
|
y*******g 发帖数: 6599 | 8 bfs和weight 没关系吧。
dijkstra之类的priority first search才和weight有关系 |
|
u****t 发帖数: 5 | 9 可以考虑用Dijkstra,把Matrix转化成一个图
比如Matrix中4个位置
a b
c d
值分别是
1 2
3 4
可以转化为图
a - b
| \/ |
c - d
边的权重是对应cell的值相加,例如
(a, b) = 3
(a, c) = 4
(a, d) = 5 |
|
|
|
s******n 发帖数: 226 | 12 1, 不好意思,在java 的class里,用static variable做全局变量,不需要传参
2, 你的意思是说destination不一定是右下角? 那就传进去就是了 因为不管怎么样
都要检测目标那个位置
BTW: 虽然dijkstra是对的,但是我觉得从DP角度好理解,好实现 |
|
d*******l 发帖数: 338 | 13 我觉得前面那个DP或者叫记忆化搜索的代码是对的。Dijkstra应该也行 |
|
u****t 发帖数: 5 | 14 可以考虑用Dijkstra,把Matrix转化成一个图
比如Matrix中4个位置
a b
c d
值分别是
1 2
3 4
可以转化为图
a - b
| \/ |
c - d
边的权重是对应cell的值相加,例如
(a, b) = 3
(a, c) = 4
(a, d) = 5 |
|
|
|
s******n 发帖数: 226 | 17 1, 不好意思,在java 的class里,用static variable做全局变量,不需要传参
2, 你的意思是说destination不一定是右下角? 那就传进去就是了 因为不管怎么样
都要检测目标那个位置
BTW: 虽然dijkstra是对的,但是我觉得从DP角度好理解,好实现 |
|
d*******l 发帖数: 338 | 18 我觉得前面那个DP或者叫记忆化搜索的代码是对的。Dijkstra应该也行 |
|
s****j 发帖数: 67 | 19 没错,我觉得这里有个理解上的偏差
所谓面试算法,究竟是说看你知不知道某个特定的算法,比如dijkstra,prim这种,还
是说你能否利用某些算法思想去解决未知的一些问题,比如你是否有dp的sense去解一
些最优化问题
在我看来面前者意义不大,真正的算法能力指的是后者
可惜大多数公司不会这么面。。。 |
|
|
a*****n 发帖数: 158 | 21 直接用BFS吧,用DIJKSTRA有点浪费。。。 |
|
q****x 发帖数: 7404 | 22 bfs是dijkstra特例,此时优先队列退化成普通队列。 |
|
n*******w 发帖数: 687 | 23 嗯,Dijkstra肯定得掌握。虽然每个edge权重是1,还是得用优先队列吧。
还有个Bellman-Ford也可以考虑。 |
|
|
p*****2 发帖数: 21240 | 25 Given an undirected graph G having N (1
weights. Find the shortest path from vertex 1 to vertex N, or state that
such path doesn't exist.
区别是这个是undirected。解法一样吗? |
|
|
s***y 发帖数: 3042 | 27 谢谢了,刚刚找到一个说法,说现在最快的是用Dijkstra's shortest path algorithm
和fibonacci heap。为了缩短query的时间,有些会做preprocessing。不过是个
storage和computation的tradeoff。 |
|
H***e 发帖数: 476 | 28 这题跟dp啥关系啊?
也用不着dijkstra,就是简单的pre-order traversal就可以勒。
inside a class:
private List minPath = new ArrayList();
private int minSum = Integer.MAX_VALUE;
private void minSumPathFromRootToLeave(BSTNode node,
ArrayList path, int currentSum) {
//path is the path from root to node's parent,
//currentSum is sum from root till node's parent
// add base cases here:
if(node == null){
return;
}
... 阅读全帖 |
|
w*******q 发帖数: 1764 | 29 火车跑得快全凭车头带,没好车头什么都不是。你所谓talent是指作为一个螺丝钉的
talent, 和出好产品or出break-through半点关系也没有。何况目前的模式连测试螺丝
钉的talent豆大大可疑。何况真有talent的人多少都有点脾气,而能在这种大公司生存
的最根本的素质就是要求和别人合得来,Jobs那种性格就是有dijkstra的算法功夫去面
试也过不了behavior. |
|
|
S******t 发帖数: 151 | 31 这个就是所谓的
Dutch National Flag Problem
Dijkstra对这个问题进行过非常深入的研究
事实上现在是没有任何stable algorithm可以做到in place, linear time的
这个问题如果要求stable,事实上是无解的。
变。 |
|
|
h**6 发帖数: 4160 | 33 构造一个n顶点的有向图,把能到达的顶点连起来,然后用dijkstra求最短路径。 |
|
p*****2 发帖数: 21240 | 34
我就学了Floyd-Warshall和Dijkstra。 还没碰到需要那个的题。有时间得看看。 |
|
|
|
l*********8 发帖数: 4642 | 37 这道题目是求图上两点间最近距离的特例,可以用Dijkstra算法的简化版. |
|
S****h 发帖数: 115 | 38 Given an array of non-negative integers, you are initially positioned at the
first index of the array.
Each element in the array represents your maximum jump length at that
position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from
index 0 to 1, then 3 steps to the last index.)
我就按照最短路径的解法来做,初始化所有mj[A.length](minimum jump)为Integer.
MAX_VALUE, 然后mj[0] = 0; 后面利用P... 阅读全帖 |
|
l*********8 发帖数: 4642 | 39 以前gloomyturkey贴过一个O(n)的程序。 |
|
|
|
l*********8 发帖数: 4642 | 42 写了个递归的玩,呵呵
int jump(int A[], int n, int reach=1)
{
if (n<=reach) return 0;
int nextReach=reach;
for (int i=0; i
nextReach=max(nextReach, A[i]+i+1);
return 1+jump(A+reach, n-reach, nextReach-reach);
} |
|
q***y 发帖数: 236 | 43 我的dp方法。过了online judge。请大家帮忙看看复杂度多少?
int jump(int A[], int n) {
vector steps(n);
steps[n-1] = 0;
for (int i=n-2; i>=0; --i) {
if (A[i]==0) steps[i] = -1; // unable to reach
else if (A[i]>=n-i-1) steps[i] = 1;
else {
int msp = n-i-1;
for (int j=A[i]; j>0; --j) {
if (steps[i+j]>-1 && steps[i+j]
if (msp==1) break;
}
steps[i] = msp+1;
}
}
retu... 阅读全帖 |
|
|
S****h 发帖数: 115 | 45 嗯,看来greedy确实是最优解法O(n),贴个code:
public int jump(int[] A) {
int jumpCount = 0;
int index = 0;
int limit = 0;
while (limit < A.length - 1) {
jumpCount++;
int temp = limit;
for (int i = index; i <= limit; i++) {
if (A[i] + i > temp)
temp = A[i] + i;
}
// can not progress
if (limit == temp)
return -1;
// progress
index = limit + 1;
limit = temp;
... 阅读全帖 |
|
b******v 发帖数: 1493 | 46 火鸡好牛
★ 发自iPhone App: ChineseWeb - 中文网站浏览器 |
|
p*****o 发帖数: 1285 | 47 今天写了一个O(N^2)的,一个O(kn)的,k是从各点开始最短路径里的最大值。kn的轻松
过关,n^2的本来过不了,加了个dirty hack就过了。分别如下:
// O(n^2)
class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector cost(n, 0x7fffffff);
cost[n-1] = 0;
for (int i=n-2; i>=0; --i){
int mj = 0x7fffffff;
for (int j = min(n-1, i + A[i]); j > i; --j){
if (cost[j] < mj) mj = cost[j];
if ... 阅读全帖 |
|
|
w****x 发帖数: 2483 | 49 dijkstra只是找一条路径打印,就算是现场实现这个打印一条最短路径算法的代码也是
不简单的,A家啥时候这么难了 |
|
o****n 发帖数: 349 | 50 You can get a much better algorithm than O(n^3) if you modify
Dijkstra's algorithm. Most likely your O(n^3) algorithm would
fail miserably.
ps: this question is pure BS for a phone interview.
10
也是 |
|