k**********g
发帖数: 989 | 1
好像是正解.
A shortest path from n0 (starting point) to ny (any point) can be classified
as:
n0 ... ... ny (not touching any constrained point), OR
n0 ... n2 ... ny (touching only n2), OR
n0 ... n5 ... ny (touching only n5), OR
... (more combinations if there are additional constrains)
The best result from the first class is simply computed by removing all
constrained points from the graph.
For each of the remaining classes, the search can be broken down into:
(e.g. for the class that allows n2, r... 阅读全帖 |
|
S**I
发帖数: 15689 | 2 一个heuristic的算法是用distance做为weight计算K shortest paths，然后从中寻找符
合total time < T的路径，或着是反过来用time做为weight计算K shortest paths，然
后选取distance最小的那条。 |
|
m********r
发帖数: 811 | 3 【 以下文字转载自 Physics 讨论区 】
发信人: miniplayer (mplayer), 信区: Physics
标 题: What is the shortest non-zero lenght, L, of a magnetic quadrupole that is imaging in the horizonta
发信站: BBS 未名空间站 (Mon Aug 31 18:20:27 2009, 美东)
What is the shortest non-zero lenght, L, of a magnetic quadrupole that is
imaging in the horizontal plane, with omega=9 ? |
|
|
r******r
发帖数: 700 | 5 Who can try the shortest code that immediately consumes up all your CPU
power? |
|
r*******y
发帖数: 1081 | 6 . . . . e
. . x . .
. s . x .
. . . . .
Need to find a shortest path from starting s to ending e
and can not pass through the point marked with x
At each point we can go right, left, up or down.
Thanks. |
|
a*******y
发帖数: 1040 | 7 You have a matrix of size n*n with entries either 1 or 0. 1 means there is a
path, 0 means no path. Find shortest path and print it from (0,0) to (n-1,
n-1)
这个我觉得用backtrack，但是keep那个path有点麻烦，假如你在某一点发现路径走的
cell数目相同，你怎么update那个path？任选一个？ |
|
a*******y
发帖数: 1040 | 8 no, 你这个不对，
不是shortest的，你要比较下再push |
|
d******a
发帖数: 238 | 9 我感觉这代码是有些蛮力的，不太好。但result应该是shortest的，因为我是得到了所
有路径，只保存最短的路径。 |
|
c****x
发帖数: 15 | 10 If you want to keep all shortest path, you can modify the hash table in BFS
to allow duplication of cell in search node |
|
a*****8
发帖数: 10 | 11 碰到的一题online coding
Given a string s, return the shortest substring that is only occurring once.
Examples:
s="aabbabbaab" retunrs either "bab" or "baa"
s="aaaa" returns "aaaa"
大家看看有什么好的想法 |
|
h*********2
发帖数: 192 | 12 但是对整个树找shortest path怎么做呢？好像要用dp，大家给个思路吧~~
谢谢！ |
|
r*******n
发帖数: 3020 | 13 two nodes 路径不就一条吗，还有shortest 之说？
tree 是没有环的图 |
|
i***y
发帖数: 285 | 14 My Mom stay here for 183 days, Can she count for my dependent? What is the
shortest duration for her to be a dependent of mine?
I heard that if I add her as dependent, i can have $13,000 tax deduction. Is
that true? |
|
z****l
发帖数: 5282 | 15
What is the shortest duration?
yes if you can file as resident.
183. Kindly read the chapter 1 of publicaiton 519 on www.isr.gov
Is
ask whoever told you so. |
|
s******8
发帖数: 4192 | 16 Chile is the shortest team competing in the World cup, with an average
height of 1.76m |
|
n****y
发帖数: 106 | 17 你意思是先找k 条最短路径，然后在里面找出最短但是符合条件的
我们现在就是这么做的，但是manager想avoid k shortest paths algorithm...
我不明白为什么要avoid,但是我没有决定权
你还知道其他的算法么？
谢谢
找符 |
|
|
e*u
发帖数: 17 | 19 After a simple search, I find this paper:
I. Dumitrescu and N. Boland, "Improved Preprocessing, Labeling and Scaling
Algorithms for the Weight Constrained Shortest Path Problem", Networks, 42(3
), pg. 135-153, 2003.
The authors compared several algorithms. The conclusion is that the labeling
algorithm is the best, which, by the way, is close to my algorithm, hehe. |
|
p**********g
发帖数: 378 | 20 the shortest synthetic route |
|
m********r
发帖数: 811 | 21 What is the shortest non-zero lenght, L, of a magnetic quadrupole that is
imaging in the horizontal plane, with omega=9 ? |
|
D**u
发帖数: 204 | 22 Just heard such a problem:
(0,0,0), (1,0,0), (0,1,0), (0,0,2),... (1,1,2) are the vertices of a
chang2 fang1 ti3. An ant is at (0,0,0) and can move on the surfaces of
this chang2 fang1 ti3. If you pick up a point A on the surface, the
ant can always choose the shortest path to A (from (0,0,0) ).
In order to make the ant move the longest path, you
need to find a point on the surface.
Question:
(1) Do you think (1,1,2) is the point that you should choose?
(2) if you have the energy, please find ou |
|
c*****a
发帖数: 808 | 23 新鲜写的 longest common prefix，之前没做过
public class Solution {
public String longestCommonPrefix(String[] strs) {
// Start typing your Java solution below
// DO NOT write main() function
if(strs.length ==0) return "";
String shortest=strs[0];
for(String s: strs){
if(s.isEmpty()) return "";
if(s.length()
shortest = s;
}
int length = shortest.length();
while(true){
b... 阅读全帖 |
|
p**********1
发帖数: 1458 | 24 大家觉得哪个可以赌啊？最后一列（例如2.21 跟1.704）是赔率，下注一块。
NFL Propositions
New York Giants vs New England Patriots: Aaron Hernandez Props
SUN 2/5 WILL AARON HERNANDEZ SCORE A TD?
03:30 PM 701 Yes 2.210
702 No 1.704
SUN 2/5 TOTAL PASS RECEPTIONS FOR AARON HERNANDEZ?
03:30 PM 703 Over 5.5 Receptions 1.840
704 Under 5.5 Receptions 2.020
SUN 2/5 TOTAL RECEIVING YARDS FOR AARON HERNANDEZ?
03:30 PM 705 Over 68.5 Receiving Yards 2.050
706 Under 68.5 Re... 阅读全帖 |
|
h*****u
发帖数: 109 | 25 我感觉这个是one-to-all shortest path的变形。如果在坐标上有一个点s，距离的和
最小，等同于每个城市到s的shortest distance。
for s in all points
determine the sum of the shortest distances
output the minimum one
算shortest distances时，可以用all-pair shortest paths, such as Floyd-
Warshall |
|
o*q
发帖数: 630 | 26 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
w*******g
发帖数: 9932 | 27
You don't follow the same shortest path as before.
You only update the nodes that are neighbors of u where k(u) = i for each i.
The key here is that for a unknown graph, you don't know how long is the shortest
path from source to the destination. That is why Bellman-Ford's algorithm needs
|V| iterations.
For this problem, that distance of the shortest path between v and u
is bounded by the distance of the previous shortest path and
you can find out the new shortest path by a BSF-like traversal |
|
s*x
发帖数: 3328 | 28 中学数学题
sum distance <= 2 x measure / shortest edge
= shortest edge x height / shortest edge
= height on the shortest edge
<= any edge that is not the shortest
<= sum of any two edges |
|
d********w
发帖数: 363 | 29 amazon好像出过此题，简单的说，就是一个原始字符串，一个目标串，求最少的变换的
路径，要求每次变化后的词都在一个字典中。
有些人说bfs，还是dijkstra算法？
下面是原题
// http://www.cs.duke.edu/csed/newapt/allwordladder.html
A word ladder is a sequence of words in which each word can be transformed
into the next word by changing one letter. For example, the word ladder
below changes 'lot' to 'log'.
lot dot dog log
This is not the shortest word-ladder between 'lot' and 'log' since the
former can be immediately changed to the latter yielding a word ladder of
length two:... 阅读全帖 |
|
D**********R
发帖数: 25234 | 30 今天带娃参加学区的language group，是给语言表达上有欠缺的孩子提供的服务，不过
很多指导对普通孩子也可能有帮助，训练师给了一张单子，是
concepts in order of difficulty by age band
按半年的时段，给3－6岁的孩子提出了一些需要掌握的概念，让我贴在家里冰箱上，对
照娃的年龄那一条，经常在对话中用到这些概念，让娃也会掌握和使用这些概念。
敲完发现有许多词是重复的，顺序也不一样，不知道怎么回事，不过既然总体就这些概念，照着练练总没错的，大家做
参考吧
3－0 to 3－5 （三岁0个月到三岁5个月，以下类推）
least difficult to most difficult
top
another
under
missing
highest
finished
nearest
all
up
empty
tallest
both
outside
down
largest
different
full
same
longest
in front
many
across
most
smallest
around
next
===========... 阅读全帖 |
|
w*******g
发帖数: 9932 | 31 hmmm, it is not exactly BFS.
This is not the same problem as the one that I dealt with before :(
I think the solution should be that
assume each node u is given the total weight (d(u)) and
the # of edges (let's call it k(u)) of the shortest path from the source v.
Based on the new weights of all edges,
update the shortest path of all nodes have edges from u where k(u)=1
and then update the shortest path of all nodes with edges from u where k(u) = 2,
and then update the shortest path of all nodes |
|
i**********e
发帖数: 1145 | 32 【 以下文字转载自 JobHunting 讨论区 】
发信人: dongfeiwww (feifei), 信区: JobHunting
标 题: [算法] word ladder problem
发信站: BBS 未名空间站 (Mon Jan 24 23:59:22 2011, 美东)
amazon好像出过此题，简单的说，就是一个原始字符串，一个目标串，求最少的变换的
路径，要求每次变化后的词都在一个字典中。
有些人说bfs，还是dijkstra算法？
下面是原题
// http://www.cs.duke.edu/csed/newapt/allwordladder.html
A word ladder is a sequence of words in which each word can be transformed
into the next word by changing one letter. For example, the word ladder
below changes 'lot' to 'log'.
lot dot dog log
This is not... 阅读全帖 |
|
q**j
发帖数: 10612 | 33 再给你看几个例子。你要是说美国人民不喜欢Camry，Sonata和Mustang，整个美国人都
笑了。TrueCar要吸引人眼球，谁简单轻信这种分析才是真的要反省了。
http://www.prnewswire.com/news-releases/truecarcom-identifies-m
e-shortest-and-longest-stays-on-dealership-lots-103851803.html
2010 Shortest Vehicles in Inventory, by model
2010 Chevrolet Equinox
2010 GMC Terrain
2010 Toyota 4Runner
2010 Longest Vehicles in Inventory, by model
2010 Toyota Camry
2010 Hyundai Sonata
2010 Ford Mustang
2011 Shortest Vehicles in Inventory, by model
Honda Accord
Ford Esc... 阅读全帖 |
|
b******y
发帖数: 660 | 34 if it the "path" is the shortest path,
we can use adjacency matrix, each entry a[u][v] stores the length the
shortest path from u to v.
if u->v has no path, then set a[u][v] = -1
In this way, we can tell whether this is a path from u to v in O(1) by
checking if the entry is -1; we can also tell in O(1) whether there is a
shortest path of length k by checking whether the value of the entry is k.
if it the "path" is the simple path,
we can expand the adjacency matrix to be 3-D, i.e., a[u][v][i], t... 阅读全帖 |
|
w*******l
发帖数: 14 | 35 code assessment是我自己面的。
aptitude paper是从老印论坛扒的。
PROBLEM ONE: TRAINS
Problem: The local commuter railroad services a number of towns in Kiwiland
. Because of monetary concerns, all of the tracks are 'one-way.' That is,
a route from Kaitaia to Invercargill does not imply the existence of a route
from Invercargill to Kaitaia. In fact, even if both of these routes do
happen to exist, they are distinct and are not necessarily the same distance!
The purpose of this problem is to help the railroad p... 阅读全帖 |
|
p****n
发帖数: 69 | 36 Assume the shortest path is of length N.
Call the shortest path algorithm for each node that is directly connected to
the source and record the lengths. Among these lengths, there should be one
(or some) equal to N-1, corresponding to the shortest path. If the next
smallest length is M. Then the answer is M+1.
getShortestPath |
|
r****c
发帖数: 2585 | 37 Faint
The problem is not clear and well defined
It is said that "the shortest path is already computed" is it mean a certain
pair of
source and destination or all pairs
for the objective: find the new shortest path is mean the all pairs
if all pairs, it could not be O(E)
Btw, even the objective is for a fixed pair of end points,
do not understand your solution
"just go through the graph edge by edge and determine whether the current
edge is the shortest path between its end points. the algorithm |
|
c******m
发帖数: 98 | 38 Could you please explain how to exam each edge? Thanks.
Given the shortest path between any pair, how to compute
the shortest path after adding k?
Besides, maybe what is given is only the shortest path to
one specific source node. |
|
r****c
发帖数: 2585 | 39 Yeah you are right
actually, we can find the shortest path tree not only a pair of shortest path
the key observation is that every edge is considered at most once,
can you imagine how to find the all shortest path in O(E)?
once.
v.
k(u) = 2,
k(u) = 3,
previously
complexity |
|
c***g
发帖数: 472 | 40 given one article, and a set of keywords
find the shortest length part which contain all the keywords
how to do that?
After translated, it will be: given a sequence, how to
find a shortest substring that contains all the items required. Example: a s
equence "abaccdefgacel" and a set of key words "a" "c", "d" and "e". The sho
rtest substring contianing all of the key words is "accde". Find one of such
shortest substrings. |
|
|
|
E*V
发帖数: 17544 | 43 Amtrak 票价 NYC - DC $134- $162
today one way
Afternoon $134.00
Evening $134.00
Shortest Trip
2 hr, 47 min
$162.00
next month if you buy in advance
$49 3Hours and 15 min to 3 hours 57 mins
$139 for for 2 hr 47 min
Lowest Price
Morning $49.00
Afternoon $49.00
Evening $49.00
Shortest Trip
2 hr, 47 min
$139.00 |
|
E*V
发帖数: 17544 | 44 today one way
Afternoon $134.00
Evening $134.00
Shortest Trip
2 hr, 47 min
$162.00
next month if you buy in advance
$49 3Hours and 15 min to 3 hours 57 mins
$139 for for 2 hr 47 min
Lowest Price
Morning $49.00
Afternoon $49.00
Evening $49.00
Shortest Trip
2 hr, 47 min
$139.00 |
|
c*****g
发帖数: 21627 | 45 Michael Lewis: Did Goldman Sachs Overstep in Criminally Charging Its Ex-
Programmer?
A month after ace programmer Sergey Aleynikov left Goldman Sachs, he was
arrested. Exactly what he’d done neither the F.B.I., which interrogated him
, nor the jury, which convicted him a year later, seemed to understand. But
Goldman had accused him of stealing computer code, and the 41-year-old
father of three was sentenced to eight years in federal prison.
Investigating Aleynikov’s case, Michael Lewis holds a s... 阅读全帖 |
|
c*******o
发帖数: 8869 | 46 Flynn, the shortest lived NSA,
Spicer, the shortest lived press secretary... |
|
c********d
发帖数: 11593 | 47 我还是觉得tomtom好使，如果不是它的地图更新总不够快……天晓得设计garmin最短路
径算法的是什么角色，家里的garmin每次给我指的路都超级奇葩。如果要shortest
time，它至少能带我多兜三个迈，直接导致我比其他人晚几分钟到；如果要shortest
distance，它就带我尽走些窄得匪夷所思的羊肠小道，石子路都有。
终极解决方式是配了google map或者waze的手机。 |
|
z*********3
发帖数: 37 | 48 能不能展开说说? 用dp的话，不能保证两个子串的shortest substring合起来也是
shortest substring吧，中间还有很多字符 |
|
c*****e
发帖数: 74 | 49 Several things to consider in designing a graph data structure:
1. Is there a need to add/delete graph Nodes?
2. Is there a need to add/delete graph Edges?
3. How to check whether there is a edge between two Nodes?
4. How to iterate all the edges incoming/outgoing to one Node?
5. How to calculate the shortest path between two Nodes?
6. How to calculate the shortest path of each node pair?
7. How to serialize and deserialize a graph data structure?
Seems the problem here is on how to serialize/de... 阅读全帖 |
|
v****s
发帖数: 1112 | 50 how to compute all-pair shortest path in a give graph? complexity?
how to store them in a database to get efficient query performance? e.g.,
how
to return the shortest path for query vertices A and B? |
|
