逛論壇的時(shí)候刷到的。覺得有點(diǎn)興趣就自己寫了一下。
給你一個(gè)數(shù)組 routes，表示一系列公交線路，其中每個(gè) routes[i] 表示一條公交線路，第 i 輛公交車將會(huì)在上面循環(huán)行駛。

例如，路線 routes[0] = [1, 5, 7] 表示第 0 輛公交車會(huì)一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 這樣的車站路線行駛。 現(xiàn)在從 source 車站出發(fā)（初始時(shí)不在公交車上），要前往 target 車站。 期間僅可乘坐公交車。

求出 最少乘坐的公交車數(shù)量 。如果不可能到達(dá)終點(diǎn)車站，返回 -1 。

示例 1：
輸入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
輸出：2
解釋：最優(yōu)策略是先乘坐第一輛公交車到達(dá)車站 7 , 然后換乘第二輛公交車到車站 6 。

示例 2：
輸入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
輸出：-1

  // var routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]];
var routes =  [[1,2,7],[3,6,7]];
// var source = 15, target = 12;
var source = 1, target = 6;
var counts = []; 
var exclude = [];
var countsIndex = () => { return counts.length-1;}
routes.forEach(item=>{
    if(item.includes(source)){
        exclude=[];
        counts.push([source]); 
        exclude.push(item);
        if(!item.includes(target)){
            var bool = false
            item.forEach(num=>{ 
                var b = fun(num,target);
                if(b)
                    bool = true
            })
            if(!bool)//如果該線路無(wú)法到達(dá)終點(diǎn)則刪除
                counts.splice(countsIndex(),1); 
        } 
    }
})
function  fun(from = source, to = target) {
    var list = routes.filter(item=> !exclude.includes(item))
    for (const item of list) {
        if(item.includes(from) && item.includes(to) ){  
            exclude.push(item); 
            if(item.includes(to)){
                counts[countsIndex()].push(to) 
                return true;
            }else{ 
                item.forEach(num=>{
                    if(fun(num,to)){
                        counts[countsIndex()].push(from) 
                        return true;
                    }
                        
                }) 
            }
        }
    }
    return false;
}

console.log(counts);

輸出結(jié)果

image.png

image.png

第二種寫法

function fun2() {
    var routes = [
        [7, 12],
        [4, 5, 15],
        [6],
        [15, 19],
        [9, 12, 13]
    ];
    var source = 15,
        target = 12;
    /* var routes =  [[1,2,7],[3,6,7]];
    var source = 1, target = 6; */
    var 線路s = [];
    var exclude = [];
    for (let index = 0; index < routes.length; index++) {
        const elements = routes[index];
        var 線路 = new Set();
        if (!exclude.includes(elements)) { //如果沒有被排除則添加到新線路中
            elements.forEach(item => 線路.add(item));
            //排除
            exclude.push(elements);
        }
        for (const item of routes) {
            if (!exclude.includes(item)) { //判斷當(dāng)前車站是否已經(jīng)被排除  
                var b = false
                for (const iterator of item) {
                    if (線路.has(iterator)) ////判斷當(dāng)前車站是否存在于線路中
                    {
                        b = true;
                        break;
                    }
                }
                if (b) { //如果存在于線路中則合并
                    item.forEach(e => 線路.add(e))
                    exclude.push(item);
                }
            }
        }
        if (線路.size > 0)
            線路s.push(Array.from(線路));
    } 
    console.log(線路s);
}
fun2();

結(jié)果

image.png

具體的返回就懶得寫了。過程大概就這樣