前言
数据结构与算法属于开发人员的内功,不管前端技术怎么变,框架怎么更新,版本怎么迭代,它终究是不变的内容。 始终记得在参加字节青训营的时候,月影老师说过的一句话,不要问前端学不学算法。计算机学科的每一位都有必要了解算法,有
写出高质量代码的潜意识
。
一、问题描述
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1] 输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1] 输出:[[1]]
二、思路讲解
拿到问题的时候,先不着急,分析一下,全排列问题。是不是有以下几个特点
- 每次走N步(N为数组的长度),走过的路径不能重复
- 每走一步,都可以撤销(如果还能走其它路的话)
- 计算所有不重复的路径 我在这篇文章中罗列了其它有关回溯算法的题目,感兴趣的话可以看一下: 春招前你一定可以学会的回溯算法ByteDance
var permute = function(nums) { const res = [] // 存储所有结果 const map = {} // 记录当前元素是否存在,其实就是记录当前走过的路 const dfs = (arr)=>{ if(arr.length==nums.length){ res.push(arr.slice()) // 对数组进行浅拷贝,避免后续操作数组会影响到res的值 return } for(const num of nums){ // 横向遍历 if(map[num]){ // 这个元素已经选过 continue } map[num] = true arr.push(num) // 选择元素 dfs(arr) // 递归 arr.pop() // 撤销选择 map[num] = false } } dfs([]) return res };
后续
- 地址: 全排列
好了,本篇 力扣-全排列
到这里就结束了,我是邵小白,一个在前端领域摸爬滚打的大三学生,欢迎👍评论。