巴士路线算法
Bus Routes Algorithm
我正在尝试解决以下问题：
https://leetcode.com/problems/bus-routes/
We have a list of bus routes. Each routes[i] is a bus route that the ith bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0th 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.
我的想法是把每一站都当作一个节点。每个节点都有一个颜色（公交车编号），并有一个值（停靠站编号）。
这个问题将被转换为 0-1 BFS 最短路径问题。
这是我的代码：
class Node {
int val;
int color;
boolean visited;
int distance;
public Node(int val, int color) {
this.val = val;
this.color = color;
this.visited = false;
this.distance = 0;
}
public String toString() {
return "{ val = " + this.val + ", color = " + this.color + " ,distance = " + this.distance + "}";
}
}
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if(S == T) return 0;
// create nodes
// map each values node(s)
// distance between nodes of the same bus, have 0 distance
// if you're switching buses, the distance is 1
Map<Integer, List<Node>> adjacency = new HashMap<Integer, List<Node>>();
int color = 0;
Set<Integer> colorsToStartWith = new HashSet<Integer>();
for(int[] route : routes) {
for(int i = 0; i < route.length - 1; i++) {
int source = route[i];
int dest = route[i + 1];
adjacency.putIfAbsent(source, new ArrayList<Node>());
adjacency.putIfAbsent(dest, new ArrayList<Node>());
if(source == S) colorsToStartWith.add(color);
adjacency.get(source).add(new Node(dest, color));
adjacency.get(source).add(new Node(source, color));
}
if(route[route.length - 1] == S) colorsToStartWith.add(color);
adjacency.putIfAbsent(route[route.length - 1], new ArrayList<Node>());
adjacency.get(route[route.length - 1]).add(new Node(route[0], color));
adjacency.get(route[route.length - 1]).add(new Node(route[route.length - 1], color));
color++;
}
// run bfs
int minDistance = Integer.MAX_VALUE;
Deque<Node> q = new LinkedList<Node>();
Node start = new Node(S, 0);
start.distance = 1;
q.add(start);
boolean first = true;
boolean found = false;
while(!q.isEmpty()) {
Node current = q.remove();
current.visited = true;
System.out.println(current);
for(Node neighbor : adjacency.get(current.val)) {
if(!neighbor.visited) {
neighbor.visited = true;
if(neighbor.color == current.color || current.val == neighbor.val || first) {
q.addFirst(neighbor);
neighbor.distance = current.distance;
} else {
q.addLast(neighbor);
neighbor.distance = current.distance + 1;
}
if(neighbor.val == T) {
minDistance = Math.min(minDistance, neighbor.distance);
}
}
}
first = false;
}
return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
}
}
我不确定为什么这是错误的。
以下测试用例失败：
Routes = [
[12,16,33,40,44,47,68,69,77,78,82,86,97],
[5,8,25,28,45,46,50,52,63,66,80,81,95,97],
[4,5,6,14,30,31,34,36,37,47,48,55,56,58,73,74,76,80,88,98],
[58,59],
[54,56,78,96,98],
[7,30,35,44,60,87,97],
[3,5,57,88],
[3,9,13,15,23,24,28,38,49,51,54,59,63,65,78,81,86,92,95],
[2,7,16,20,23,46,55,57,93],
[10,11,15,31,32,48,53,54,57,66,69,75,85,98],
[24,26,30,32,51,54,58,77,81],
[7,21,39,40,49,58,84,89],
[38,50,57],
[10,57],
[11,27,28,37,55,56,58,59,81,87,97],
[0,1,8,17,19,24,25,27,36,37,39,51,68,72,76,82,84,87,89],
[10,11,14,22,26,30,48,49,62,66,79,80,81,85,89,93,96,98],
[16,18,24,32,35,37,46,63,66,69,78,80,87,96],
[3,6,13,14,16,17,29,30,42,46,58,73,77,78,81],
[15,19,32,37,52,57,58,61,69,71,73,92,93]
]
S = 6
T = 30
我的代码中有什么错误导致此测试失败？
您给出的示例输入应该 return 1，因为 one-but-last 路线包含源和目标巴士站（6 和 30）：
[3,6,13,14,16,17,29,30,42,46,58,73,77,78,81]
我运行your code with that input，它returns 1，所以你的解决方案因为其他原因被拒绝了，那肯定是超时了。
我看到您的代码不是最佳的几个原因：
虽然理想情况下 BFS 应该在找到目标节点时停止，但您的版本必须继续访问 所有 个可访问的未访问节点，然后才能访问决定解决方案是什么。所以即使它在与源相同的路由上找到目标，它也会继续切换路由并因此做很多不必要的工作，因为没有希望找到 更短的 路径.
这不是应该的样子。您应该注意以优先考虑不增加距离的边缘的方式执行搜索，并且仅当没有更多边缘时，才选择距离增加 1 的边缘。如果你这样做，你可以在找到目标后立即停止搜索。
A Node 对象被重复创建为公交车站和“颜色”（即路线）的相同组合。因此，当您稍后将 visited 设置为 true 时，重复的 Node 对象的 visited 仍将等于 false，因此公交车站将是去过几次都没有收获。
您应该确保仅在不存在具有此类组合的现有对象时才创建新的 Node 对象。
同一条路线上两个连续的公交车站之间存在边，这意味着您可能需要遍历同一条路线上的多条边才能找到目标或正确的切换地点另一条路线。
考虑整个路线会更有效Node：当路线至少共享一个公共汽车站时，它们将被视为连接（有边） .将路线转换为 Set 个公交车站将使识别这些边缘变得快速和容易。
自反边缘，往返于同一个公交车站，但指定颜色（路线），也不会增加效率。您尝试通过此设置解决的主要问题是确保路线的首选是免费的（不被视为转换）。但如果您应用前面的要点，那么这种担忧就不再是问题。
实施
我选择 JavaScript 作为实现，但我想在 Java 中重写它并不难：
function numBusesToDestination (routes, S, T) {
if (S === T) return 0;
// Create nodes of the graph
const nodes = routes;
// Map bus stops to routes: a map keyed by stops, with each an empty Set as value
const nodesAtBusStop = new Map([].concat(...routes.map(route => route.map(stop => [stop, new Set]))));
// ... and populate those empty Sets:
for (let node of nodes) {
for (let stop of node) {
nodesAtBusStop.get(stop).add(node);
}
}
// Build adjacency list of the graph
const adjList = new Map(nodes.map(node => [node, new Set]));
for (let [stop, nodes] of nodesAtBusStop.entries()) {
for (let a of nodes) {
for (let b of nodes) {
if (a !== b) adjList.get(a).add(b);
}
}
}
const startNodes = nodesAtBusStop.get(S);
const targetNodes = nodesAtBusStop.get(T);
if (!startNodes || !targetNodes) return -1;
// BFS
let queue = [...startNodes];
let distance = 1;
let visited = new Set;
while (queue.length) {
// Create a new queue for each distance increment
let nextLevel = [];
for (let node of queue) {
if (visited.has(node)) continue;
visited.add(node);
if (targetNodes.has(node)) return distance;
nextLevel.push(...adjList.get(node));
}
queue = nextLevel;
distance++;
}
return -1;
};
// I/O handling
(document.oninput = function () {
let result = "invalid JSON";
try {
let routes = JSON.parse(document.querySelector("#inputRoutes").value);
let S = +document.querySelector("#inputStart").value;
let T = +document.querySelector("#inputTarget").value;
result = numBusesToDestination(routes, S, T);
}
catch (e) {}
document.querySelector("#output").textContent = result;
})();
#inputRoutes { width: 100% }
Routes in JSON format:
<textarea id="inputRoutes">[[1,2,7],[3,6,7]]</textarea><br>
Start: <input id="inputStart" value="1"><br>
Target: <input id="inputTarget" value="6"><br>
Distance: <span id="output"></span>
我正在尝试解决以下问题： https://leetcode.com/problems/bus-routes/
We have a list of bus routes. Each
routes[i]is a bus route that the ith bus repeats forever. For example ifroutes[0] = [1, 5, 7], this means that the first bus (0th 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 stopT. 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 = 6Output:
2Explanation:
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.
我的想法是把每一站都当作一个节点。每个节点都有一个颜色（公交车编号），并有一个值（停靠站编号）。
这个问题将被转换为 0-1 BFS 最短路径问题。
这是我的代码：
class Node {
int val;
int color;
boolean visited;
int distance;
public Node(int val, int color) {
this.val = val;
this.color = color;
this.visited = false;
this.distance = 0;
}
public String toString() {
return "{ val = " + this.val + ", color = " + this.color + " ,distance = " + this.distance + "}";
}
}
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if(S == T) return 0;
// create nodes
// map each values node(s)
// distance between nodes of the same bus, have 0 distance
// if you're switching buses, the distance is 1
Map<Integer, List<Node>> adjacency = new HashMap<Integer, List<Node>>();
int color = 0;
Set<Integer> colorsToStartWith = new HashSet<Integer>();
for(int[] route : routes) {
for(int i = 0; i < route.length - 1; i++) {
int source = route[i];
int dest = route[i + 1];
adjacency.putIfAbsent(source, new ArrayList<Node>());
adjacency.putIfAbsent(dest, new ArrayList<Node>());
if(source == S) colorsToStartWith.add(color);
adjacency.get(source).add(new Node(dest, color));
adjacency.get(source).add(new Node(source, color));
}
if(route[route.length - 1] == S) colorsToStartWith.add(color);
adjacency.putIfAbsent(route[route.length - 1], new ArrayList<Node>());
adjacency.get(route[route.length - 1]).add(new Node(route[0], color));
adjacency.get(route[route.length - 1]).add(new Node(route[route.length - 1], color));
color++;
}
// run bfs
int minDistance = Integer.MAX_VALUE;
Deque<Node> q = new LinkedList<Node>();
Node start = new Node(S, 0);
start.distance = 1;
q.add(start);
boolean first = true;
boolean found = false;
while(!q.isEmpty()) {
Node current = q.remove();
current.visited = true;
System.out.println(current);
for(Node neighbor : adjacency.get(current.val)) {
if(!neighbor.visited) {
neighbor.visited = true;
if(neighbor.color == current.color || current.val == neighbor.val || first) {
q.addFirst(neighbor);
neighbor.distance = current.distance;
} else {
q.addLast(neighbor);
neighbor.distance = current.distance + 1;
}
if(neighbor.val == T) {
minDistance = Math.min(minDistance, neighbor.distance);
}
}
}
first = false;
}
return minDistance == Integer.MAX_VALUE ? -1 : minDistance;
}
}
我不确定为什么这是错误的。
以下测试用例失败：
Routes = [
[12,16,33,40,44,47,68,69,77,78,82,86,97],
[5,8,25,28,45,46,50,52,63,66,80,81,95,97],
[4,5,6,14,30,31,34,36,37,47,48,55,56,58,73,74,76,80,88,98],
[58,59],
[54,56,78,96,98],
[7,30,35,44,60,87,97],
[3,5,57,88],
[3,9,13,15,23,24,28,38,49,51,54,59,63,65,78,81,86,92,95],
[2,7,16,20,23,46,55,57,93],
[10,11,15,31,32,48,53,54,57,66,69,75,85,98],
[24,26,30,32,51,54,58,77,81],
[7,21,39,40,49,58,84,89],
[38,50,57],
[10,57],
[11,27,28,37,55,56,58,59,81,87,97],
[0,1,8,17,19,24,25,27,36,37,39,51,68,72,76,82,84,87,89],
[10,11,14,22,26,30,48,49,62,66,79,80,81,85,89,93,96,98],
[16,18,24,32,35,37,46,63,66,69,78,80,87,96],
[3,6,13,14,16,17,29,30,42,46,58,73,77,78,81],
[15,19,32,37,52,57,58,61,69,71,73,92,93]
]
S = 6
T = 30
我的代码中有什么错误导致此测试失败？
您给出的示例输入应该 return 1，因为 one-but-last 路线包含源和目标巴士站（6 和 30）：
[3,6,13,14,16,17,29,30,42,46,58,73,77,78,81]
我运行your code with that input，它returns 1，所以你的解决方案因为其他原因被拒绝了，那肯定是超时了。
我看到您的代码不是最佳的几个原因：
虽然理想情况下 BFS 应该在找到目标节点时停止，但您的版本必须继续访问 所有 个可访问的未访问节点，然后才能访问决定解决方案是什么。所以即使它在与源相同的路由上找到目标，它也会继续切换路由并因此做很多不必要的工作，因为没有希望找到 更短的 路径.
这不是应该的样子。您应该注意以优先考虑不增加距离的边缘的方式执行搜索，并且仅当没有更多边缘时，才选择距离增加 1 的边缘。如果你这样做，你可以在找到目标后立即停止搜索。
A
Node对象被重复创建为公交车站和“颜色”（即路线）的相同组合。因此，当您稍后将visited设置为true时，重复的Node对象的visited仍将等于false，因此公交车站将是去过几次都没有收获。您应该确保仅在不存在具有此类组合的现有对象时才创建新的
Node对象。同一条路线上两个连续的公交车站之间存在边，这意味着您可能需要遍历同一条路线上的多条边才能找到目标或正确的切换地点另一条路线。
考虑整个路线会更有效
Node：当路线至少共享一个公共汽车站时，它们将被视为连接（有边） .将路线转换为Set个公交车站将使识别这些边缘变得快速和容易。自反边缘，往返于同一个公交车站，但指定颜色（路线），也不会增加效率。您尝试通过此设置解决的主要问题是确保路线的首选是免费的（不被视为转换）。但如果您应用前面的要点，那么这种担忧就不再是问题。
实施
我选择 JavaScript 作为实现，但我想在 Java 中重写它并不难：
function numBusesToDestination (routes, S, T) {
if (S === T) return 0;
// Create nodes of the graph
const nodes = routes;
// Map bus stops to routes: a map keyed by stops, with each an empty Set as value
const nodesAtBusStop = new Map([].concat(...routes.map(route => route.map(stop => [stop, new Set]))));
// ... and populate those empty Sets:
for (let node of nodes) {
for (let stop of node) {
nodesAtBusStop.get(stop).add(node);
}
}
// Build adjacency list of the graph
const adjList = new Map(nodes.map(node => [node, new Set]));
for (let [stop, nodes] of nodesAtBusStop.entries()) {
for (let a of nodes) {
for (let b of nodes) {
if (a !== b) adjList.get(a).add(b);
}
}
}
const startNodes = nodesAtBusStop.get(S);
const targetNodes = nodesAtBusStop.get(T);
if (!startNodes || !targetNodes) return -1;
// BFS
let queue = [...startNodes];
let distance = 1;
let visited = new Set;
while (queue.length) {
// Create a new queue for each distance increment
let nextLevel = [];
for (let node of queue) {
if (visited.has(node)) continue;
visited.add(node);
if (targetNodes.has(node)) return distance;
nextLevel.push(...adjList.get(node));
}
queue = nextLevel;
distance++;
}
return -1;
};
// I/O handling
(document.oninput = function () {
let result = "invalid JSON";
try {
let routes = JSON.parse(document.querySelector("#inputRoutes").value);
let S = +document.querySelector("#inputStart").value;
let T = +document.querySelector("#inputTarget").value;
result = numBusesToDestination(routes, S, T);
}
catch (e) {}
document.querySelector("#output").textContent = result;
})();
#inputRoutes { width: 100% }
Routes in JSON format:
<textarea id="inputRoutes">[[1,2,7],[3,6,7]]</textarea><br>
Start: <input id="inputStart" value="1"><br>
Target: <input id="inputTarget" value="6"><br>
Distance: <span id="output"></span>