当前位置:Gxlcms > JavaScript > JavaScript趣题:迷路的牛仔

JavaScript趣题:迷路的牛仔

时间:2021-07-01 10:21:17 帮助过:4人阅读

很久以前,有一条通往西部无法地带的路......

一位年轻的牛仔,根据指示,得从一个地方前往另一个地点。指示像这样"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;
}


以上就是JavaScript趣题:迷路的牛仔的内容,更多相关内容请关注PHP中文网(www.gxlcms.com)!

人气教程排行