Javascript函数来显示所遵循的城市的路线

Question

我正在 codewars.com 上练习编码。 我遇到了this question :

We are tracking down our rogue agent Matthew Knight A.K.A. Roy Miller and he travels from places to places to avoid being tracked. Each of his travels are based on a list of itineraries in an unusual or incorrect order. The task is to determine the routes he will take in his every journey. You are given an array of routes of his itineraries. List down only the places where he will go in correct order based on his itineraries.

Example: routes = [[USA, BRA], [JPN, PHL], [BRA, UAE], [UAE, JPN]]

result: "USA, BRA, UAE, JPN, PHL"

我试过下面的代码:

function findRoutes(routes) {

    let newArr = Array.prototype.concat.apply([], routes)
    let unique = newArr.filter((v, i, a) => a.indexOf(v) === i);

    return unique.join(', ');
  
}
console.log(findRoutes([["USA","BRA"],["JPN","PHL"],["BRA","UAE"],["UAE","JPN"]]))

它只适用于给定的案例，但是当我尝试另一个测试用例时:

[["Chicago", "Winnipeg"], ["Halifax", "Montreal"], ["Montreal", "Toronto"], ["Toronto", "Chicago"], ["Winnipeg", "Seattle"]]

如果失败了...所以我知道出了问题，因为运动应该是有序的。 我很乐意改进它或从不同的想法重写。

Answer 1

这是一种解决方案。我不会说这是最好的策略，但它确实有效。我是这样做的:

1. 使用双循环找到第一个城市(没有任何以其名称开头的项目的城市)
2. 从路由数组中移除包含第一个城市的元素
3. 遍历路由数组以找到下一个城市并删除该元素，直到列表为空
4. 添加您要查找的最后一个“下一个”城市(最后一个元素的第二个城市)

let routes = [["Chicago", "Winnipeg"], ["Halifax", "Montreal"], ["Montreal", "Toronto"], ["Toronto", "Chicago"], ["Winnipeg", "Seattle"]]
let solution = [];
let next = '';

for(i = 0; i < routes.length; i++) {
  let first = routes[i][0];
  next = routes[i][1];
  let j = 0;
  while (j < routes.length && routes[j][1] !== first) {
    j++;
  }
  if (j >= routes.length) {
    solution.push(first);
    routes.splice(i, 1);
    break;
  }
}

while (routes.length !== 0) {
  for(i = 0; i < routes.length; i++) {
    if (routes[i][0] === next) {
      solution.push(routes[i][0]);
      next = routes[i][1]
      routes.splice(i, 1);
      break;
    }
  }
}
solution.push(next);
console.log(solution);

我想明确指出，如果您的列表无法获得解决方案，则此算法将存在无限循环的严重问题。 例如，routes = [[A, B], [C, D]] 将失败并且永不停止。