BusRoutes [source code]
public class BusRoutes {
static
/******************************************************************************/
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T)
return 0;
int N = routes.length;
Map<Integer, Set<Integer>> route_sets = new HashMap<> ();
Set<Integer> start_buses = new HashSet<> (), target_buses = new HashSet<> ();
for (int i = 0; i < N; i++) {
Set<Integer> set = new HashSet<> ();
for (int stop : routes[i])
set.add (stop);
if (set.contains (S))
start_buses.add (i);
if (set.contains (T))
target_buses.add (i);
route_sets.put (i, set);
}
boolean[][] intersects = new boolean[N][N];
for (int i = 0; i < N; i++) {
for_each_j: for (int j = 0; j < N; j++) {
// ignore symmetry optimization for now: don't Premature Optmization
if (j == i)
continue;
for (int station : routes[i]) {
if (route_sets.get (j).contains (station)) {
intersects[i][j] = true;
continue for_each_j;
}
}
}
}
int[] d = new int[N];
Arrays.fill (d, Integer.MAX_VALUE);
Queue<Integer> queue = new LinkedList<> (start_buses);
// Define d as the distance array: don't adapt it to the question.
// Rather, calculate the distance, then get your desired values from
// the distance, this is simpler and safer.
for (int start : start_buses)
d[start] = 0;
while (!queue.isEmpty ()) {
int cur = queue.poll ();
for (int i = 0; i < N; i++) {
if (intersects[i][cur] && d[i] > d[cur] + 1) {
d[i] = d[cur] + 1;
queue.offer (i);
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
if (target_buses.contains (i))
res = Math.min (res, d[i]);
}
return res == Integer.MAX_VALUE ? -1 : res + 1;
}
}
/******************************************************************************/
public static void main(String[] args) {
BusRoutes.Solution tester = new BusRoutes.Solution();
int[][][] inputs = {
{{3,16,33,45,59,79,103,135},
{3,35,39,54,56,78,96,101,120,132,146,148},
{13,72,98},
{37,70,107},
{0,12,31,37,41,68,78,94,100,101,113,123},
{11,32,52,85,135},
{43,50,128},
{0,13,49,51,53,55,60,65,66,80,82,87,92,99,112,118,120,125,128,131,137},
{15,19,34,37,45,52,56,97,108,123,142},
{7,9,20,28,29,33,34,38,43,46,47,48,53,59,65,72,74,80,88,92,110,111,113,119,135,140},
{15,41,64,83},
{7,13,26,31,57,85,101,108,110,115,119,124,149},
{47,61,67,70,74,75,77,84,92,101,124,132,133,142,147},
{0,2,5,6,12,18,34,37,47,58,77,98,99,109,112,131,135,149},
{6,7,8,9,14,17,21,25,33,40,45,50,56,57,58,60,68,92,93,100,108,114,130,149},
{7},
{5,16,22,48,77,82,108,114,124},
{34,71},
{8,16,32,48,104,108,116,134,145},
{3,10,16,19,35,45,64,74,89,101,116,149},
{1,5,7,10,11,18,40,45,50,51,52,54,55,69,71,81,82,83,85,89,96,100,114,115,124,134,138,148},
{0,2,3,5,6,9,15,52,64,103,108,114,146},
{5,33,39,40,44,45,66,67,68,69,84,102,106,115,120,128,133},
{17,26,49,50,55,58,60,65,88,90,102,121,126,130,137,139,144},
{6,12,13,37,41,42,48,50,51,55,64,65,68,70,73,102,106,108,120,123,126,127,129,135,136,149},
{6,7,12,33,37,41,47,53,54,80,107,121,126},
{15,75,91,103,107,110,125,139,142,149},
{18,24,30,52,61,64,75,79,85,95,100,103,105,111,128,129,142},
{3,14,18,32,45,52,57,63,68,78,85,91,100,104,111,114,142},
{4,7,11,20,21,31,32,33,48,61,62,65,66,73,80,92,93,97,99,108,112,116,136,139}},
{{85, 112, 2}}, //1
{{7,12},
{4,5,15},
{6},
{15,19},
{9,12,13}}, {{15, 12, -1}}, //2
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[][] routes = inputs[2 * i];
int S = inputs[2 * i + 1][0][0], T = inputs[2 * i + 1][0][1], ans = inputs[2 * i + 1][0][2], output = tester.numBusesToDestination (routes, S, T);
System.out.printf ("%sand %d, %d -> %s, expected: %d\n",
Matrix.printMatrix (routes), S, T, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
完全没有思路的题目;
最后自己感觉这个思路应该是对的:
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T)
return 0;
int cnt_bus = routes.length;
Map<Integer, Set<Integer>> route_sets = new HashMap<> ();
Set<Integer> start_buses = new HashSet<> (), target_buses = new HashSet<> ();
for (int i = 0; i < cnt_bus; i++) {
Set<Integer> set = new HashSet<> ();
for (int stop : routes[i])
set.add (stop);
if (set.contains (S))
start_buses.add (i);
if (set.contains (T))
target_buses.add (i);
route_sets.put (i, set);
}
Map<Integer, Set<Integer>> edges = new HashMap<> ();
boolean[][] processed = new boolean[cnt_bus][cnt_bus];
for (int i = 0; i < cnt_bus; i++) {
for (int j = 0; j < cnt_bus; j++) {
if (j == i)
continue;
if (processed[i][j] || processed[j][i])
continue;
processed[i][j] = processed[j][i] = true;
Set<Integer> tmp = new HashSet<> (route_sets.get (i));
tmp.retainAll (route_sets.get (j));
if (!tmp.isEmpty ()) {
edges.computeIfAbsent (i, num -> new HashSet<> ()).add (j);
edges.computeIfAbsent (j, num -> new HashSet<> ()).add (i);
}
}
}
int min = Integer.MAX_VALUE;
for (int start : start_buses) {
min = Math.min (min, dfs (start, start_buses, target_buses, edges, 1, new boolean[cnt_bus]));
if (min == 1)
break;
}
return min == Integer.MAX_VALUE ? -1 : min;
}
int dfs (int cur, Set<Integer> start_buses, Set<Integer> target_buses, Map<Integer, Set<Integer>> edges, int length, boolean[] visited) {
if (target_buses.contains (cur))
return length;
visited[cur] = true;
int min = Integer.MAX_VALUE;
for (int next_bus : edges.get (cur)) {
if (!visited[next_bus]) {
min = Math.min (min, dfs (next_bus, start_buses, target_buses, edges, length + 1, visited));
}
}
visited[cur] = false;
return min;
}
}
2018-05-02 01:03:23 看起来很复杂的一个代码, 其实很多部分都是在做preprocess, 还好啦; 这里这个情况, 最好还是把DFS的这些草丛里了抽屉哦你参数都扔到global算了; 你面试的时候也想要这样写这么长一个参数表吗? 小细节, 自己懂就行了, 还是要按照面试最好的方式来习惯自己;
但是被test1这个大的给TLE了; 又实在是不好debug; 后面再看了; 看了一下其他人的答案, 都很简短, 所以估计这个题目我是方向走错了;
最后照着uwi的解法改了半天好歹是AC了; 只能说看他的代码真的是学到很多东西;
主要的几个改动:
- 最后一个搜索用BF算法来搜索; 对应的, adjacency应该用matrix来表示而不是用list;
- 注意他这个BF搜索的过程, 只有relax成功之后, 这个i才会被enqueue; 这个是一个很重要的地方, 我自己写的时候好像是忘记了;
2018-05-02 01:06:16 还是要强调一下, BF算法我还是不熟悉其实, 自己看看核心代码: 按照一个固定的顺序, relax所有的edge, 如果relax成功, 更改dist, 然后被relax成功的那一个node扔到queue里面去;
这题因为最后edge其实都是长度1(换route都是1的代价), 所以最后用adjmatrix还挺好的;
其他的, 基本写法都差不多; 他用的List of Set好像最后比我的快, 但是实际上我们俩的算法都很慢, 都是大几百ms的;
另外, 一个小细节, 在计算intersects矩阵的时候, 要判断i和j两个route相交, 我一开始的做法是这样的:
Set<Integer> tmp = new HashSet<> (route_sets.get (i));
tmp.retainAll (route_sets.get (j));
if (!tmp.isEmpty ()) {
intersects[i][j] = true;
continue for_each_j;
}
特地实验了一下, 真的不行, 最后只有按照uwi这里干脆暴力搜索反而还快一点; 这个真的是没办法了; 不过实际面试的时候应该也不会出这种问题;
另外, 这个算法思路最后肯定不是最优秀的, 速度太慢了; 应该还有更好的思路; 比如下面cchao的思路, 那么简短, 肯定就是更优秀的; 这个后面整理到这题的时候再来看看; discuss好像也已经有很简短的解法了;
2018-05-02 00:57:46 还是那句话, 我现在因为刷LeetCode太多, 所以看到题目就有例子, 反而认为是理所当然的, 但是真正面试的时候, 自己看完题目, 一定一定要立刻开始想一个很typical的例子, 然后再开始想, 一定一定不要脑子里面一点数据都没有在空想. 这个真的是刷题太多导致有点习以为常, 但是最近面试的时候如果面试官不给例子, 自己很容易就直接姜住了, 还以为自己的思考很有进度的错觉;
editorial
Approach #1: Breadth First Search [Accepted]
Intuition
Instead of thinking of the stops as nodes (of a graph), think of the buses as nodes. We want to take the least number of buses, which is a shortest path problem, conducive to using a breadth-first search.
这里理解还是没有问题的; 另外, 他这个算法好快, 61ms, 我模仿uwi的那个是600+的速度;
Algorithm
We perform a breadth first search on bus numbers. When we start at S, originally we might be able to board many buses, and if we end at T we may have many targets for our goal state.
One difficulty is to efficiently decide whether two buses are connected by an edge. They are connected if they share at least one bus stop. Whether two lists share a common value can be done by set intersection (HashSet), or by sorting each list and using a two pointer approach.
To make our search easy, we will annotate the depth of each node: info[0] = node, info[1] = depth.
又是有点看不懂的样子, 感觉他又要开始炫技了;
import java.awt.Point;
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S==T) return 0;
int N = routes.length;
List<List<Integer>> graph = new ArrayList();
for (int i = 0; i < N; ++i) {
Arrays.sort(routes[i]);
graph.add(new ArrayList());
}
Set<Integer> seen = new HashSet();
Set<Integer> targets = new HashSet();
Queue<Point> queue = new ArrayDeque();
// Build the graph. Two buses are connected if
// they share at least one bus stop.
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (intersect(routes[i], routes[j])) {
graph.get(i).add(j);
graph.get(j).add(i);
}
// Initialize seen, queue, targets.
// seen represents whether a node has ever been enqueued to queue.
// queue handles our breadth first search.
// targets is the set of goal states we have.
for (int i = 0; i < N; ++i) {
if (Arrays.binarySearch(routes[i], S) >= 0) {
seen.add(i);
queue.offer(new Point(i, 0));
}
if (Arrays.binarySearch(routes[i], T) >= 0)
targets.add(i);
}
while (!queue.isEmpty()) {
Point info = queue.poll();
int node = info.x, depth = info.y;
if (targets.contains(node)) return depth+1;
for (Integer nei: graph.get(node)) {
if (!seen.contains(nei)) {
seen.add(nei);
queue.offer(new Point(nei, depth+1));
}
}
}
return -1;
}
public boolean intersect(int[] A, int[] B) {
int i = 0, j = 0;
while (i < A.length && j < B.length) {
if (A[i] == B[j]) return true;
if (A[i] < B[j]) i++; else j++;
}
return false;
}
}
首先他用的是adjlists, 所以估计是真的想要BFS; 然后用sort来做intersection这个思路其实不错哦; 不然呢, 你现在这个做法, 是N^2啊, sort怎么不行了;
array intersection by sorting
然后你要熟悉一下他这个intersect的实现方式, 还是挺不错的; 看这个代码样子, 应该是一个熟悉的方法;
仔细看了一下这个算法核心, 真的是一个无比简单的BFS啊; 为什么比BF快这么多啊; TODO;
另外这题虽然最后代码不难懂, 其实还是符合LeetCode大部分hard的套路的, 就是要先仔细的用simplifying observation来尽可能深入的转化题目, 这样最后才比较容易写出来代码;
UNFINISHED
uwi:
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if(S == T)return 0;
int n = routes.length;
List<Set<Integer>> sets = new ArrayList<>();
for(int i = 0;i < n;i++){
Set<Integer> set = new HashSet<>();
for(int v : routes[i]){
set.add(v);
}
sets.add(set);
}
boolean[][] g = new boolean[n][n];
for(int i = 0;i < n;i++){
inner:
for(int j = 0;j < n;j++){
if(i == j)continue;
for(int v : routes[i]){
if(sets.get(j).contains(v)){
g[i][j] = true;
continue inner;
}
}
}
}
int[] d = new int[n];
Queue<Integer> q = new ArrayDeque<>();
Arrays.fill(d, 99999999);
for(int i = 0;i < n;i++){
if(sets.get(i).contains(S)){
q.add(i);
d[i] = 0;
}
}
while(!q.isEmpty()){
int cur = q.poll();
for(int i = 0;i < n;i++){
if(g[cur][i] && d[i] > d[cur] + 1){
d[i] = d[cur] + 1;
q.add(i);
}
}
}
int ret = 99999999;
for(int i = 0;i < n;i++){
if(sets.get(i).contains(T)){
ret = Math.min(ret, d[i]);
}
}
if(ret > 99990000){
return -1;
}
return ret+1;
}
}
这个代码基本上就是不怎么想看了, 不过思路看起来好像跟我的有点类似;
仔细看了一下, 好像是真的跟我的代码类似的; 而且他最后的这个BFS实际上是用一个类似DJ算法的写法, 也就是有点通用的一个写法来写的;
但是我最后改成BFS, 而且还加了pruning, 为什么还是不行呢;
另外, 注意他这里多起点BFS的初始化是怎么做的: 是直接把所有的起点都一起丢到queue里面去, 而不是一个循环, 每一个iteration重新建立一个queue, 每次只有一个起点这样做; 之前好像学系统设计的时候也碰到过类似的做法;
他最后的BFS不仅没有pruning, 连visited都懒得做, 居然也是很好的就过了;
另外仔细看了一下他这个写法其实更像是BF算法, 而不是DJ或者BFS这种基于adjacency的写法? 因为他对于每一个cur, 都是遍历所有的node;
哎, 这题讲到底其实还是基本功不扎实, 现在别的不说, 起码知道DFS肯定是不对的: DFS什么时候可以用来找最短路径了? 任何时候用DFS找最短路径都不是最好的办法, 偏偏你还居然这么写了;
另外, 他这里的graph实际上是用g这个矩阵来完成的一个adjacency matrix的表达方式; 因为使用BF算法, 所以用这个方式正好合理; adjacency list反而是比较适合那种基于neighbor的算法;
discuss好像有人讨论说这题DFS不好写, 不过也有人说自己用DFS做出来的; 这题就算用BFS来做也好像要加上额外的pruning; 可能我的问题是在这里?
cchao:
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
if (S == T) return 0;
vector<bool> used(routes.size());
unordered_set<int> vis;
vis.insert(S);
int step = 0;
for(;;) {
step++;
vector<int> a;
for (int i = 0; i < routes.size(); ++i) {
if (!used[i]) {
for (int x : routes[i]) if (vis.count(x)) {
a.push_back(i);
used[i] = true;
break;
}
}
}
for (int i : a) {
for (int x : routes[i])
vis.insert(x);
}
if (a.empty() || vis.count(T)) break;
}
return vis.count(T) ? step : -1;
}
};
他这个就非常简短了;
感觉其实就是省略了很多预处理? 暂时还不是很理解这个算法: TODO;
突然发现这题九章算法居然有解法;
http://www.lintcode.com/en/problem/bus-station/#
题目给的限制不太一样:
1 <= N <= 100, 2 <= |route[i]| <= 100, 0 <= route[i][j] <= 2^31 - 1
A and B two stations must exist and they are different
public class Solution {
public int getMinTransferNumber(int N, int[][] route, int A, int B) {
// Write your code here
Map<Integer, Integer>idxTable = new HashMap<Integer, Integer>();
int [] status = new int[1001];
Queue<Integer>que = new LinkedList<Integer>();
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < route[i].length; j++) {
if (!idxTable.containsKey(route[i][j])) {
idxTable.put(route[i][j], cnt++);
}
if (route[i][j] == A) {
status[i] |= 1;
que.offer(i);
}
if (route[i][j] == B) {
status[i] |= 2;
}
}
}
List<List<Integer>>station = new ArrayList<List<Integer>>();
for(int i = 0; i < cnt; i++) {
station.add(new ArrayList<Integer>());
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < route[i].length; j++) {
int idx = idxTable.get(route[i][j]);
station.get(idx).add(i);
}
}
List<List<Integer>>transfer = new ArrayList<List<Integer>>();
for(int i = 0; i < N; i++) {
transfer.add(new ArrayList<Integer>());
for(int j = 0; j < N; j++) {
transfer.get(i).add(0);
}
}
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < station.get(i).size(); j++) {
for (int k = j + 1; k < station.get(i).size(); k++) {
int a = station.get(i).get(j);
int b = station.get(i).get(k);
transfer.get(a).set(b, 1);
transfer.get(b).set(a, 1);
}
}
}
int ans = 0;
while (!que.isEmpty()) {
ans++;
int size = que.size();
for (int i = 0; i < size; i++) {
int h = que.poll();
if ((status[h] & 2) != 0) {
return ans;
}
for (int j = 0; j < N; j++) {
if (transfer.get(h).get(j) != 1 || (status[j] & 1) != 0) {
continue;
}
status[j] |= 1;
que.offer(j);
}
}
}
return -1;
}
}
这个算法有点奇怪啊, 他status的长度只给了1000, 按照下面的实现, 这个是完成一个把每一个station(route[i]的每一个元素)像一个类似tokenization一样的对应处理; count最后对应的就是route[i][j]的值域的size;
然后station的长度就是这个count, 所以这个station(实际上是一个list of lists)实际上就是一个key是station的结构, 然后看后面处理, 是一个station = {all routes that contain this station}的一个结构; 这个也什么为什么他要对所有的station有一个tokenization的操作, 这样最后建这个list的时候(类似一个数组其实)才会比较方便; 当然如果图省事, 这个list换成一个Map, 那么tokenization就可以省了.
这个实际上是一个比较危险的操作, 因为linkcode这里给的限制是, 最多有100x100个distinct的station, 所以他这里很无所谓的建立了一个反向查询; 但是LeetCode里面给的是500x500的限制, 这个最后很有可能就会爆内存了;
Problem Description
We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.
We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.
Example:
Input:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation:
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.
Note:
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= 500.
- 0 <= routes[i][j] < 10 ^ 6.
Difficulty:Hard
Total Accepted:2.4K
Total Submissions:7.6K
Contributor:awice
Companies
google
Related Topics
breadth-first search