javascript 之排列组合 |
您所在的位置：网站首页 › js字符串排列组合 › javascript 之排列组合 |
|
接上一篇 javascript 之二分查找 看完这篇后，相信你在解决排列组合问题的时候会象写 for 循环一样快速。 方法是一样的，记模板，提高效率，减少出错。 var permute = function (nums) { let ans = [] let used = [] let arr = [] function helper() { if (arr.length == nums.length) { ans.push(arr.slice(0)) return } for (let i = 0; i < nums.length; i++) { if (used[i]) continue used[i] = true arr.push(nums[i]) helper(arr) arr.pop() used[i] = false } } helper() return ans };输入 [1,2,3] 输出 [ [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] ]这正好是 全排列的解法。46. 全排列 可以不用 used 额外数组，直接交换 nums 元素的方式，但是额外数组记录的方式更具有通用性，更适合用做模板 为了方便记，简单解释一下。递归三板斧。 退出条件。//找到 一组排列直接退出 if (arr.length == nums.length) { ans.push(arr.slice(0)) return }这一层递归要做的事//如果这个位置 已经用过了，略过 if (used[i]) continue //标记已使用 used[i] = true //取用这个数 arr.push(nums[i]) //进到下一层 helper(arr)恢复现场arr.pop() used[i] = false用语言来表述一下：每次取一个没有用过的数，直到长度为 nums 长度。 递归过程早已有人画了图，还有视频 ，看这里 可能每个人开始的时候都习惯用大脑去模拟递归调用的整个过程，但是这样效率不高，也容易出错。比较高效的方法是记住模板的每句代码可以产生的效果，想要什么样的结果 写什么样的代码即可。写过多次后，大脑就可以很容易的模拟整个递归过程了。这就是只要足够熟练，其意自见。 全排列有两种，一种没有重复数字，一种有重复数字 没有重复数字 全排列有重复数字，全排列II全排列前面已经讲过，现在看下 全排列II 只要稍加改动即可 function permuteUnique(nums) { const ans = [] const arr = [] const used= [] function helper() { if (arr.length === nums.length) { ans.push(arr.slice(0)) return } let last = undefined //新增 for (let i = 0; i < nums.length; i++){ if (used[i]) continue if (last == nums[i]) continue //新增 last = nums[i] //新增 used[i] = true arr.push(nums[i]) helper() arr.pop(nums[i]) used[i]=false } } helper(); return ans }一共新增了三行代码。要想避免答案重复，首先得知道为什么会重复。在递归的每一层里都会枚举每一个没有用过的位置上的数，放在位置 index ( index>=0&&index |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |