旅行终点站（1436）

题目

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

示例

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] 输出："Sao Paulo"

解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

输入：paths = [["B","C"],["D","B"],["C","A"]] 输出："A"

解释：所有可能的线路是： "D" -> "B" -> "C" -> "A".  "B" -> "C" -> "A".  "C" -> "A".  "A".  显然，旅行终点站是 "A" 。

输入：paths = [["A","Z"]] 输出："Z"

提示

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• 所有字符串均由大小写英文字母和空格字符组成。

算法

数组

使用数组citys保存终点站，然后遍历所有起点，从citys中删除所有起点，留下的就是终点

export const destCity = (paths) => {
	const citys = [];
	for (let i = 0; i < paths.length; i++) {
		citys.push(paths[i][1]);
	}
	for (let i = 0; i < paths.length; i++) {
		if (citys.indexOf(paths[i][0]) >= 0) {
			citys.splice(citys.indexOf(paths[i][0]), 1);
		}
	}
	return citys[0];
};

Set

和上面方法类似，使用两个Set保存起点和终点，需要注意的是最后获取Set中值的写法

export const destCity = (paths) => {
	const start = new Set();
	const end = new Set();
	for (let i = 0; i < paths.length; i++) {
		start.add(paths[i][0]);
		end.add(paths[i][1]);
	}
	for (const startCity of start) {
		end.delete(startCity);
	}
	return end.values().next().value;
};

Map

将{起点: 终点}按键值对保存在Map中，然后循环查找，当某一个值没有对应的键时，这个值就是终点

export const destCity = (paths) => {
	const map = new Map();
	for (let i = 0; i < paths.length; i++) {
		map.set(paths[i][0], paths[i][1]);
	}
	let end = paths[0][1];
	while (map.get(end)) {
		end = map.get(end);
	}
	return end;
};