狗家店面，感觉超难

rayluck4 发表于 2020-8-22 03:19
这是在一个一维的世界里吗？为什么我无法理解一维的世界里两条路怎么在一个点相交？

二维平面上的点，也可以用一个数字来表示（计数）吧。比如说，10*10的表格，可以用1到100来标记每一个格子。格子的标记顺序也可以改变。

yiliaobailiao 发表于 2020-8-22 04:47
二维平面上的点，也可以用一个数字来表示（计数）吧。比如说，10*10的表格，可以用1到100来标记每一个格 ...

但是这题明显没有说到这个意思啊

旧未来 发表于 2020-8-22 05:00
但是这题明显没有说到这个意思啊

就想成一个graph就好了啊。。每个节点都是一个值，只不过在同一条路上，节点的值是有顺序的。

yiliaobailiao 发表于 2020-08-21 13:47:27
二维平面上的点，也可以用一个数字来表示（计数）吧。比如说，10*10的表格，可以用1到100来标记每一个格子。格子的标记顺序也可以改变。

这和一维二维没有半毛钱关系吧，其实就是个不能再简单的图啊，可以想成航班路线，给一个始发，一个到达，和一个list的途中转机航站楼。

1.  union-find
2. dfs
3. dfs  on a sorted list of intersections with probability and time

这是算法题吗？leetcode有吗？

确实有点满 但不算难吧

1和2是一道题 找到start所在的road开始 dfs+一个counter 这里有个trick是你不能对intersections的road去重因为他们代表不同的route 所以最简单粗暴的人方法就是把map里每个key对应的values都过一遍

第三题看似概率 实际就是个bfs 时间速度算出距离 用这个距离去bfs 结果等于bfs结束前 到达的destination的routes的数量/bfs过的routes的总数

nina9128 发表于 2020-8-22 06:47
确实有点满 但不算难吧

1和2是一道题 找到start所在的road开始 dfs+一个counter 这里有个trick是你不能对i ...

"时间速度算出距离 " - 这个地方你怎么算？速度每个route上都不一样，没法算出来最后会走多远把

旧未来 发表于 2020-08-22 11:33:27
"时间速度算出距离 " - 这个地方你怎么算？速度每个route上都不一样，没法算出来最后会走多远把

哦 没看太仔细 那就还是dfs 然后用时间作为结束条件return

请问是校招么？网上找不到链接啊