公交车最优换成次数计算
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
提示：
1 <= routes.length <= 500.
1 <= routes[i].length <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bus-routes
代码思路：
关于BFS就不细说了，不了解的可以自行百度，这道题可以从换成车辆做切入点，然后通过BFS筛选出最优换成次数
代码示例：
class Solution
{
/**
* @param Integer[][] $routes
* @param Integer $S
* @param Integer $T
* @return Integer
*/
function numBusesToDestination($routes, $S, $T)
{
if ($S == $T) {
return 0;
}
//入栈车号
$queue = new SplQueue();
$used = [];
foreach ($routes as $key => $route) {
if (in_array($S, $route)) {
$used[$key] = 1;
$queue->enqueue($key);
}
}
$site = 1;
while (!$queue->isEmpty()) {
$size = count($queue);
for ($i = 0; $i < $size; $i++) {
$top = $queue->dequeue();
if (in_array($T, $routes[$top])) {
return $site;
}
foreach ($routes[$top] as $s) {
foreach ($routes as $key => $route) {
if (in_array($s, $route) && $used[$key] == 0) {
$used[$key] = 1;
$queue->enqueue($key);
}
}
}
}
$site++;
}
return -1;
}
}
$res = (new Solution)->numBusesToDestination([[1,2,7],[3,6,7]],1,6);
上面思路解题优化,遍历耗时比较严重，in_array函数滥用
class Solution
{
/**
* @param Integer[][] $routes
* @param Integer $S
* @param Integer $T
* @return Integer
*/
function numBusesToDestination($routes, $S, $T)
{
$len_r = count($routes);
if ($S == $T) {
return 0;
}
$newRoutes = [];
foreach ($routes as $key => $route) {
foreach ($route as $r) {
$newRoutes[$key][$r] = 1;
}
}
//var_dump($newRoutes);
//入栈车号
$used = [];
$queue = new SplQueue();
foreach ($newRoutes as $key => $route) {
if (isset($newRoutes[$key][$T]) && isset($newRoutes[$key][$S])) {
return 1;
} elseif (isset($newRoutes[$key][$S])) {
$queue->enqueue($key);
}
}
$site = 1;
while (!$queue->isEmpty()) {
$size = count($queue);
for ($i = 0; $i < $size; $i++) {
$top = $queue->dequeue();
if (isset($newRoutes[$top][$T])) {
return $site;
}
foreach ($routes[$top] as $s) {
foreach ($routes as $key => $route) {
if (isset($newRoutes[$key][$s]) && $used[$key] == 0) {
$used[$key] = 1;
$queue->enqueue($key);
}
}
}
}
$site++;
}
return -1;
}
}
$res = (new Solution)->numBusesToDestination([[1,2,7],[3,6,7]],1,6);
对应golang代码
package main
import (
queue "container/list"
"fmt"
)
func main() {
//[[],[],[],[],[],[],[],[],[4,5,8,9,24,44]]
grid := [][]int{
//{1,9,12,20,23,24,35,38,37},
//{10,21,24,31,32,34,37,38,43},
//{10,19,28,37},
//{8},
//{14,19},
//{11,17,23,31,41,43,44},
//{21,26,29,33},
//{5,11,33,41},
//{4,5,8,9,24,44},
//{1,2,7},
//{3,6,7},
{3,16,33,45,59,79,103,135},
{3,35,39,54,56,78,96,101,120,132,146,148},
{37,70,107},
{0,12,31,37,41,68,78,94,100,101,113,123},
{11,32,52,85,135},
{43,50,128},
{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},
{6,7,8,9,14,17,21,25,33,40,45,50,56,57,58,60,68,92,93,100,108,114,130,149},
{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},
{7},
{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},
{0,2,5,6,12,18,34,37,47,58,77,98,99,109,112,131,135,149},
{0,13,49,51,53,55,60,65,66,80,82,87,92,99,112,118,120,125,128,131,137},
}
//res := numBusesToDestination(grid,37,28)
//res := numBusesToDestination(grid,1,6)
res := numBusesToDestination(grid,85,112)
fmt.Println(res)
}
func numBusesToDestination(routes [][]int, source int, target int) int {
if source ==target {
return 0
}
carMap := make(map[int]map[int]int)
for car,sites:=range routes{
siteList := make(map[int]int)
for _,site :=range sites{
siteList[site] =1
}
carMap[car] = siteList
}
used := make(map[int]int)
carQueue := queue.New()
for car,route:= range carMap{
if _,ok:=route[source];ok {
used[car] = 1
carQueue.PushBack(car)
}
}
siteCount := 1
for carQueue.Len()!=0 {
count :=carQueue.Len()
for i:=0;i<count;i++ {
car :=carQueue.Front()
carQueue.Remove(car)
carInt := car.Value.(int)
if _,ok:=carMap[carInt][target];ok {
return siteCount
}
for _,site := range routes[carInt] {
for nextCar,siteList :=range carMap {
_,t := siteList[site]
if _, ok := used[nextCar];!ok && t {
used[carInt] = 1
carQueue.PushBack(nextCar)
}
}
}
}
siteCount++
}
return -1
}
python3
class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
# 每个车站可以乘坐的公交车
stations = defaultdict(set)
for i, stops in enumerate(routes):
for stop in stops:
stations[stop].add(i)
# 每个公交车线路可以到达的车站
routes = [set(x) for x in routes]
q = deque([(source, 0)])
# 已经乘坐了的公交车
buses = set()
# 已经到达了的车站
stops = {source}
while q:
pos, cost = q.popleft()
if pos == target:
return cost
# 当前车站中尚未乘坐的公交车
for bus in stations[pos] - buses:
# 该公交车尚未到达过的车站
for stop in routes[bus] - stops:
buses.add(bus)
stops.add(stop)
q.append((stop, cost + 1))
return -1
测试昵称 -