曾经在 Codewars 上作过一个名为 Directions Reduction 的题目,大意是:
一个人在荒野里需要从一个地方移动到另外一个地方,然后他会收到一个包含方向指示的数组,方向包括 “NORTH”, “SOUTH”, “WEST”, “EAST”。很明显呢,”NORTH” 和 “SOUTH” 这两个方向是相反的,”WEST” 和 “EAST” 同理。
因为气候非常恶劣并且饮用水也不多了,他必须要节省体力,因此要避免沿着一个方向前进然后再折返回来这样的无用功。
如果他收到的是像下面这样的一个方向指示:
{ "NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST" };
他首先就会发现先往 “NORTH” 走再往 “SOUTH” 走是不合理的,因为这样相当于没走。你的任务就是给这个人提供一个最简化的路线版本。例如,上面的方向指示简化后就变成了:
["WEST"];
因为首先 “NORTH” 和 “SOUTH” 抵消了、”EAST” 和 “WEST” 抵消了,然后是 “SOUTH” 和 “NORTH” 抵消了,最后只剩下一个 “WEST”。
而
["NORTH", "EAST", "WEST", "SOUTH", "WEST", "WEST"];
经过简化后变成了:
["WEST", "WEST"];
以上为题目描述和任务要求。
这种题应该怎么解呢?
通常情况下我们都会想到使用 JavaScript 中的 Array.prototype.reduce() 方法。
- 将原数组的成员从左往右依次压入一个新的数组中,
- 如果原数组的成员可以跟新数组栈顶的成员抵消,则把新数组栈顶的成员弹出;
- 如果无法抵消,则把原数组中的该成员压入新数组的栈顶,作为新数组的栈顶跟原数组的下一个成员再进行比较,最后的新数组就是我们想要的结果。
代码如下:
function dirReduc(plan) { var opposite = { NORTH: "SOUTH", EAST: "WEST", SOUTH: "NORTH", WEST: "EAST" }; return plan.reduce(function(dirs, dir) { if (dirs[dirs.length - 1] === opposite[dir]) dirs.pop(); else dirs.push(dir); return dirs; }, []); }
这基本上已经算是最佳实践了,
然而有个让我目瞪狗呆的实现是这样的:
function dirReduc(arr) { var str = arr.join(""), pattern = /NORTHSOUTH|EASTWEST|SOUTHNORTH|WESTEAST/; while (pattern.test(str)) str = str.replace(pattern, ""); return str.match(/(NORTH|SOUTH|EAST|WEST)/g) || []; }
实现原理是:
- 首先把原数组转成字符串,
- 然后把能抵消的路线使用正则匹配替换为空,
- 最后利用 String.prototype.match() 返回值为数组这个技巧把字符串重新还原为我们想要的数组。
虽然不如第一种方案符合最佳实践,但我觉得的确挺聪明的!
作者心里一定在(ˇˍˇ) 想~:
凡是字符串处理都可以使用正则表达式实现;如果不是字符串,那就先把它转成字符串。
我做前端两年,对算法这方面研究不深,如有不正确的,还请指教.
博主,你的算法似乎只完成80%的任务(两版均是).如果每次只比较最顶层的栈,那些非顶栈不会抵消,除非顶栈抵消后下一个成为顶栈,这样仍存在一定可能并未简化.这在数据量比较大时一定会发生.
举个例子:对于plan=[“NORTH”, “EAST”, “SOUTH”, “WEST”]时,得到的结果仍是原plan,一眼看去就知道这预期应该是[]