江苏龙网

  1. 主页 > 生活百科 > >

一文看懂全排列算法( 三 )

全排列算法


此时递归层数为2 。上次在2层递归里遍历到i=0了 ， 从dfs返回后取出temp末尾的字符 ， 其实就是0 ， 于是将vis[0]又置为了false；继续遍历 ， vis[1]和vis[2]都为true ， 也就是1和2都在temp里 ， 都不满足条件 ， 遍历结束返回上一层递归 。此时
temp={1,2}
此时递归层数为1 。上次在1层递归里遍历到i=2了 ， 从dfs返回后取出temp末尾的字符2 ， 于是将vis[2]又置为了false；此时
temp={1}
继续遍历 ， i=3超出了下标范围 ， 遍历结束 ， 返回上一层递归 。此时
此时递归层数为0 。上次在0层递归里遍历到i=1了 ， 从dfs返回后取出temp末尾的字符1 ， 于是将vis[1]又置为了false；此时
temp={}
继续遍历 ， 此时i=2 ， vis[2]=false ， 将2填入temp ， 然后将vis[2]置为true ， 传入cnt+1=1表示temp中已有字符的个数为1 ， 进行下一层递归 ， 此时
temp={2}
此时递归层数为1 。从i=0开始遍历 。i=0时 ， vis[0]=false ， 将0填入temp ， 然后将vis[0]置为true ， 传入cnt+1=2表示temp中已有字符的个数为2 ， 进行下一层递归 ， 此时
temp={2,0}
此时递归层数为2 。从i=0开始遍历 。i=0时 ， vis[0]=true ， 0已经被填入temp了不满足条件；i=1时 ， vis[1]=false ， 将1填入temp ， 然后将vis[1]置为true ， 传入cnt+1=3表示temp中已有字符的个数为3 ， 进行下一层递归 ， 此时
temp={2,0,1}
此时递归层数为3 。经判断temp中已经填入了3个字符 ， 达到了“出厂要求” ， 将其输出后返回上一层递归 。
此时递归层数为2 。上次在2层递归里遍历到i=1了 ， 从dfs返回后取出temp末尾的字符1 ， 于是将vis[1]又置为了false；此时
temp={2,0}
继续遍历 ， 此时i=2 ， vis[2]=true ， 2已经被填入temp了不满足条件；继续遍历 ， i=3超出了下标范围 ， 遍历结束 ， 返回上一层递归 。
此时递归层数为1 。上次在1层递归里遍历到i=0了 ， 从dfs返回后取出temp末尾的字符0 ， 于是将vis[0]又置为了false；此时
temp={2}
继续遍历 ， 此时i=1 ， vis[1]=false ， 将1填入temp ， 然后将vis[1]置为true ， 传入cnt+1=2表示temp中已有字符的个数为2 ， 进行下一层递归 ， 此时
temp={2,1}
此时递归层数为2 。从i=0开始遍历 。i=0时 ， vis[0]=false ， 将0填入temp ， 然后将vis[0]置为true ， 传入cnt+1=3表示temp中已有字符的个数为3 ， 进行下一层递归 ， 此时
temp={2,1,0}
此时递归层数为3 。经判断temp中已经填入了3个字符 ， 达到了“出厂要求” ， 将其输出后返回上一层递归 。
此时递归层数为2 。上次在2层递归里遍历到i=0了 ， 从dfs返回后取出temp末尾的字符0 ， 于是将vis[0]又置为了false；此时
temp={2,1}
继续遍历 ， vis[1]和vis[2]都为true ， 意味着1和2都在temp里 ， 都不满足条件 ， 遍历结束 ， 返回上一层递归 。
此时递归层数为1 。上次在1层递归里遍历到i=1了 ， 从dfs返回后取出temp末尾的字符1 ， 于是将vis[1]又置为了false；此时
temp={2}
继续遍历 ， 此时i=2 ， vis[2]=true ， 2已经被填入temp了不满足条件；继续遍历 ， i=3超出了下标范围 ， 遍历结束 ， 返回上一层递归 。
此时递归层数为0 。上次在0层递归里遍历到i=2了 ， 从dfs返回后取出temp末尾的字符2 ， 于是将vis[2]又置为了false 。此时
temp={}
继续遍历 ， i=3超出了下标范围 ， 遍历结束 。
全排列到此结束 ， temp和vis都恢复了最初的状态 。
又到了金三银四面试季 ， 衷心祝愿大家都能拿到想要的Offer 。




推荐阅读


上一篇：CentOS系统如何禁止root用户登录

下一篇：怎么防止黑衣服粘白毛 白衣服粘毛干了会掉吗