给定一个数字列表，返回其所有可能的排列
输入：[1,2,3]
输出：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
假定各个数字不相同
给出核心代码
private void dfs(int[] nums,
boolean[] visited,
list<integer> permutation,
list<list<integer>> results) {
if (nums.length == permutation.size()) {
results.add(new arraylist<integer>(permutation));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
permutation.add(nums[i]);
visited[i] = true;
dfs(nums, visited, permutation, results);
visited[i] = false;
permutation.remove(permutation.size() - 1);
}
}
考虑int[] nums={1,2,3,4}情况
——————————————————————————————————————————————
可以看下面各个量的变化情况，当看不懂算法的时候，可以用这种方法，自己一步一步模拟程序做了什么，就能明白代码的含义了
在这个小例子中，visted【】数组存放的是，1234是否在permutation中的状态，
对于1234这四个数，visited【0】=false，就代表1没在permutation中
1234会不断添加到permutation中，并且当4个数字都进入p中时，会得到一个结果；
——————————————————————————————————————————————
在模拟的过程中，我们明白各个变量发生了什么，所代表的意义
然后对于比较有代表性的几个位置，看看程序发生了什么
——————————————————————————————————————————————
1 观察程序回到dfs（tttf，1230）时
v2 变成f
p 变成1200
循环进入f3
而此时4不在p中
4进入p中
然后重新调用
dfs（ttft，1240）
可以预见，下一个进入result的就是1243
————————————————————————————————
2 继续观察程序运行到dfs（tttt，1432）
首先会将1432add进入result
然后回到dfs的位置
dfs（tttf，1430）的f1循环中，
继续运行
v1变成f p变成143 此时v是 tftt然后
f2 t
f3 t
此时 dfs（tttf，1430）运行结束 a8位置
给出a8之前的三行
f2 f
p143
v2 t tftt
然后我们继续模拟程序
v2 f tfft
p14
f3 t
说明某个dfs已经完成了全部循环，这个dfs的位置应该是最近的一个没有被标号的dfs
因为有标号的，说明都被执行完了
goto a9
我们回到了 dfs(tfft,1400)a9
f3 f
p14
v3 t tfft
继续模拟程序
v3 f
p1
此时 dfs(tfft,1400)所在的循环也结束了
goto a10
说明dfs(tfff,1000) a10也执行结束了
观察dfs(tfff,1000) a10上面的三行代码
f0 f
p1
v0 f
继续进行
v0 f ffff
p0000
f1 f
p2
v1 t
dfs（ftff，2000）
——————————————————————————————————————————————————————————————
通过这两处 我们完全可以明白这些代码的意义了
对于任何一位上的某个数字a，在它进入p之后，对于这一位来讲，没进入p而比a更靠后的数字，会添加进p
而对于当添加一个元素进入后，它的下一位会从重新又从头去寻找v[i] t，也就是没有进入p的数字
而对于填入某个位置数字后的dfs执行完成了，如果后一位的数字都比前一位的数字在原数组更靠前，那么就会出现
每退掉一位，回到前一个dfs，而将要退掉这个位置的数字，而之前的数字，在原数组的位置都比这个数字靠前，所以之后的循环不会再有数字进入
如果是1432，那么会变成2000
如果是4321，那么会变成dfs（fttt，4000）结束，整个程序结束
——————————————————————————————————————————————————————————————
而学习其他代码的过程也类似
看懂了代码以后，尝试用自然程序做了什么说出来，如果能说明白发生了什么事，也就说明看懂了
然后再把自己想要完成的事梳理一下，拆解成一步一步要做的事，再用代码使其重新实现
学习代码的过程：
模拟程序代码逐条运行 ——》尽量提炼出代码块的作用 ——》用自然语言 说明算法做了什么
而编写代码的过程：
分析问题——》提出完成算法的各个步骤 ——》逐条编写代码完成各个步骤 ——》调试，带入测试数据
下面给出模拟程序运行时，各个变量的变化情况
dfs(ffff,0000) //dfs(nums,ffff,,)为了方便 只写最频繁变化的两个参数
f0 f //f(0) 为了方便写成 f0 v[0]是f
p1 //permutation={1} 为了方便写成 p1
v0 t tfff //v[0]改成0 visited变成 tfff
dfs(tfff,1000) a10
f0 t
f1 f
p12
v1 t
dfs(ttff,1200) a3
f0 t
f1 t
f2 f
p123
v2 t
dfs(tttf,1230) a1
f0 t
f1 t
f2 t
f3 f
p1234
v3 t
dfs(tttt,1234)
result 1234 //这里的dfs直接结束了 能找到
v3 f tttf
p123
goto a1 这里其实是方法a的 for循环结束了 返回a所在位置，继续下一行
v2 f ttff
p12
f3 f
p124
v3 t
dfs(ttft,1240) a2
f0 t
f1 t
f2 f
p1243
v2 t
dfs(tttt,1243)
result 1243
v2 f ttft
p124
f3 t
goto a2
v3 f ttff
p12
goto a3
v1 f tfff
p1
f2 f
p13
v2 t tftf
dfs(tftf,1300) a6
f0 t
f1 f
p132
v1 t
dfs(tttf,1320) a4
f0 t
f1 t
f2 t
f3 f
p1324
v3 t tttt
dfs(tttt,1324)
result 1324
v3 f tttf
p132
goto a4
v1 f tftf
p13
f2 t
f3 f
p134
v3 t tftt
dfs(tftt,1340) a5
f0 t
f1 f
p1342
v1 t tttt
dfs(tttt,1342)
result 1342
v1 f tftt
p134
f2 t
f3 t
goto a5
v3 f tftf
p13
goto a6
v2 f tfff
p1
f3 f
p14
v3 t tfft
dfs(tfft,1400)a9
f0 t
f1 f
p142
v1 t ttft
dfs(ttft,1420) a7
f0 t
f1 t
f2 f
p1423
v2 t tttt
dfs(tttt,1423)
result 1423
v2 f ttft
p142
f3 t
goto a7
v1 f tfft
p14
f2 f
p143
v2 t tftt
dfs(tftt,1430) a8
f0 t
f1 f
p1432
v1 t
dfs(tttt,1432)
return 1432
v1 f tftt
p143
f2 t
f3 t
goto a8
v2 f tfft
p14
f3 t
goto a9
v3 f tfff
p1
goto a10
v0 f ffff
p000
f1 f
p2
v1 ftff
dfs(ftff,2000)
我们可以预见 下一个就是2134
我们已经完全可以预见程序将要完成什么了
也就是此时此刻，我们看懂了这段代码的含义
如对本文有疑问， 点击进行留言回复！！
Flink程序JDK8 运行一段时间后NullException解决
解决： java.lang.NoClassDefFoundError: org/apache/http/client/HttpClient
SpringBoot中定制异常页面（404页面配置提高用户体验）
DataGrip和IDEA无法连接上Mysql问题解决方法详解
Java基础语法（多态、类、接口、Date类、基本类型、系统类）
我要评论
网友评论