JavaScript趣题：迷路的牛仔

一位年轻的牛仔，根据指示，得从一个地方前往另一个地点。指示像这样"NORTH", "SOUTH", "WEST", "EAST"。

很明显，"NORTH"和"SOUTH"是相反的方向， "WEST"和"EAST"也是相反的。

走一个方向，然后又往回走，无疑在做无用功。

在这人迹罕至的西部荒野，糟糕的天气，匮乏的水源，节约点体力很重要，否则很可能死于非命！

怎样走最明智的路线，这很重要！

给牛仔的指示，像下面这样：

plan = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

你能一眼看出，"NORTH"和"SOUTH"，这样的路线显然是不合理的，最好呆在原地。
所以，你的任务是，怎样精简路线，以节约体力。

一个更好的方案应该像这样：

plan = ["WEST"]

另一个例子：

["NORTH", "SOUTH", "EAST", "WEST"]

在这里，"NORTH"和"SOUTH"做抵消，"EAST"和"WEST"做抵消，最后返回空数组。

再看个复杂点的例子：

["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"]

"EAST", "WEST"作抵消，得到 ["NORTH", "SOUTH", "WEST", "WEST"]

"NORTH", "SOUTH"作抵消，最终得到["WEST", "WEST"]。
但是，请注意，下面这种情况是没办法抵消的：

["NORTH", "WEST", "SOUTH", "EAST"]

因为"EAST", "WEST"或"NORTH", "SOUTH"并不相邻，而是隔开的。

咋们来看看怎么编写一个这样的减少路线函数吧。

它接受一个字符串数组作为参数，返回新的字符串数组。

像这样：

dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]) // ["WEST"]
dirReduc(["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH"]) // []

第一步，建立方向的映射关系，哪些是相反的方向：

var opposite = {
 "NORTH":"SOUTH",
 "SOUTH":"NORTH",
 "EAST":"WEST",
 "WEST":"EAST"
};

接着，从后向前遍历字符串数组plan，遇到相反的方向，就从数组中移除，抵消。

然后，开始第二轮遍历，移除，抵消，第三轮，第N轮，直到找不到相反的方向，跳出循环。

此时的数组就是经过精简后的最佳路线。

function dirReduc(arr){
 var flag = false;
 while(!flag){
 for(var i=arr.length-2,flag=true;i>=0;i--){
 if(opposite[arr[i]] === arr[i+1]){
 arr.splice(i+1,1);
 arr.splice(i,1);
 i--;
 flag = false;
 }
 }
 }
 return arr;
}

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com