我在排列井的算法上遇到了一些小麻烦,我在全栈溢出中找到了它
function permutator(inputArr) {
var results = [];
function permute(arr, memo) {
var cur, memo = memo || [];
for (var i = 0; i < arr.length; i++) {
cur = arr.splice(i, 1);
if (arr.length === 0) {
results.push(memo.concat(cur));
}
permute(arr.slice(), memo.concat(cur));
arr.splice(i, 0, cur[0]);(what's the purpose of this statement ????)
}
return results;
}
return permute(inputArr);
}
实际上,我不明白递归调用是如何工作的我不明白拼接方法在这个递归调用中是如何工作的。我的意思是,例如,让我们在每次迭代中使用[0,1,2,3,4,5,6,7]的数组,我们运行cur=arr.splice(I,1(通常我们得到cur=0,然后cur=2,然后4,然后6,依此类推。。。,所以当我在控制台中记录备忘录和arr变量时,我在这里得到了输入图像描述
解决这类问题是一种复杂的方法,要理解这一点,我们需要简化问题,
经过一些修改,这个代码可读性很强!
function permutator(inputArr) {
var results = [];
function permute(arr, memo = []) {
for (var i = 0; i < arr.length; i++) {
let temp = [...arr], mem = memo.concat(temp.splice(i, 1));
if (temp.length === 0) results.push(mem);
permute(temp, mem);
}
}
permute(inputArr);
return results
}
console.log(permutator([1, 2, 3]))
因此,基本上在原始代码中,他们修改arr
(仅在短时间内(,然后(在这行arr.splice(i, 0, cur[0]);
中(恢复到原始状态。
splice
方法接受3个参数(start, deleteCount?, ...items?
(,并返回一个包含已删除元素的数组。我建议你阅读更多关于Array.splice((,
示例:
let numbers = [1, 2, 3, 4, 5];
console.log({ numbers })
let deleted_elements = numbers.splice(0, 2);
console.log('Removing first 2 elements from `numbers`', { deleted_elements, numbers })
numbers.splice(0, 0, ...deleted_elements);
console.log("Push `deleted_elements` in there original place", { numbers })