【递归，Java传智播客笔记

2021-08-08 21:24:24

java 后端程序员

对于将有n个数的数组arr进行全排列，所采用的思想是递归加回溯。

对n个元素进行全排列，将第一个元素依次和之后的元素互换，将第一个元素确定下来
对之后的n-1个元素进行全排列，**（可以看做是第一步的子问题）**采用递归实现
将互换后的元素重新换回来，以防止数组元素的顺序被打乱**（回溯思想）**

具体的实现可以看下面的函数，（可以直接使用）


/**
* 对数组中所有的元素进行全排列
* @param arr 待排列的数组
* @param k 确定第几个元素，是下标，从0开始
* */
private static void f(int[] arr, int k) {
//当k等于数组的长度时，说明排列完成
if (k == arr.length) {
//将排列好的数组输出
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
}
System.out.println();
}
for (int i = k; i < arr.length; i++) {
//将待确定的元素位置和后面的元素互换
int t = arr[k];
arr[k] = arr[i];
arr[i] = t;
//递归（确定第k+1个元素）
f(arr, k+1);
//回溯，将调换后的元素重新调换回来
t = arr[k];
arr[k] = arr[i];
arr[i] = t;
}
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.

测试用例：


public static void main(String[] args) {
int[] arr = {1,2,3,4}; //待处理的数组
int n = 3; //取出元素的个数
int[] newarr = new int[n]; //存放结果的数组
f(arr, 0);
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.

三、数组元素的排列组合

===============

有了上面对从n个元素的数组arr中取出m个数（不考虑顺序且不重复）和对n个数进行全排列的理解，那么对于从n个数中取出m个数实现排列的问题，可以看成是上面两个问题的结合体。

按照数学中的思路，我们可以先从n个元素的数组中选取出m个元素，之后对这m个元素进行全排列即可。

实现的方法如下：


/**
* 数组中对n个数进行全排列
* @param 待处理的数组
* @param newarr 排列后得到的数组
* @param k 从哪一个下标的元素开始处理
* @param n 处理元素的个数
* */
private static void pac(int[] arr,int[] newarr, int k,int n) {
//当n=0时，说明选取的数的个数为0，也就是组合完成
if (n==0) {
f(newarr, 0); //对组合到的新数组进行全排列
return;
}
for (int i = k; i <= arr.length-n; i++) {
newarr[newarr.length-n] = arr[i];
pac(arr, newarr,i+1, n-1);
}
}
/**
* 对数组中所有的元素进行全排列
* @param arr 待排列的数组
* @param k 确定第几个元素，是下标，从0开始
* */
private static void f(int[] arr, int k) {
//当k等于数组的长度时，说明排列完成
if (k == arr.length) {
//将排列好的数组输出
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
}
System.out.println();
}
for (int i = k; i < arr.length; i++) {
//将待确定的元素位置和后面的元素互换
int t = arr[k];
arr[k] = arr[i];
arr[i] = t;
//递归（确定第k+1个元素）
f(arr, k+1);
//回溯，将调换后的元素重新调换回来
t = arr[k];
arr[k] = arr[i];
arr[i] = t;
}
}


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.

测试用例：

最后

权威指南-第一本Docker书

引领完成Docker的安装、部署、管理和扩展，让其经历从测试到生产的整个开发生命周期，深入了解Docker适用于什么场景。并且这本Docker的学习权威指南介绍了其组件的基础知识，然后用Docker构建容器和服务来完成各种任务：利用Docker为新项目建立测试环境，演示如何使用持续集成的工作流集成Docker，如何构建应用程序服务和平台，如何使用Docker的API，如何扩展Docker。

总共包含了：简介、安装Docker、Docker入门、使用Docker镜像和仓库、在测试中使用Docker、使用Docker构建服务、使用Fig编配Docke、使用Docker API、获得帮助和对Docker进行改进等9个章节的知识。

关于阿里内部都在强烈推荐使用的“K8S+Docker学习指南”—《深入浅出Kubernetes：理论+实战》、《权威指南-第一本Docker书》，看完之后两个字形容，爱了爱了！

如果你也爱了，点击这里免费下载：“K8S+Docker”学习指南

版权声明

本文为[cxy喜喜呀]所创，转载请带上原文链接，感谢

https://blog.51cto.com/u_15308636/3314432

文章推荐