生成全排列格雷码邮票问题(回溯)

参考视频bilibil fjnuzs

1.题目分析

大概意思就是给你一堆数字&＃xff0c;把他们的全排列输出来。不要保存&＃xff0c;直接就是一棵多分枝的树&＃xff0c;每一层每一层走下去&＃xff0c;到了树叶的时候输出&＃xff0c;再返回到上一层去其他分支。也可理解为递归的时候&＃xff0c;上一层&＃xff08;数组前面部分&＃xff09;都固定了&＃xff0c;当前这层你把每个数都试了一遍。

2.伪代码

代码如下&＃xff08;示例&＃xff09;&＃xff1a;

设一共有n层&＃xff0c;目前在t层&＃xff0c;A数组去记录当前排列
fun(t)if(t&＃61;n)print(A)elsefor 每个数字都遍历一遍A[t] <-> A[i]fun(t&＃43;1)A[i]<->A[t]


举个例子&＃xff0c;输入1234567
假设在2这一层了&＃xff0c;那么2这个位置的和134567都换了一遍。假设某一次&＃xff0c;它被换成某一个数比如4时&＃xff0c;前面就确定了14&＃xff0c;3又开始和142567换……递归下去。

然后我们讨论一下为什么要换回来&＃xff0c;有点类似于回到树的上一层&＃xff0c;简单来说如果不换回来会出现相同的排列的数。当他到了第7层输出了之后&＃xff0c;假设输出7654321&＃xff0c;换回来是在1654327&＃xff0c;接下来时7和65432分别换了。不换的话继续循环&＃xff0c;是1可以和65432换&＃xff0c;是很不一样的。

对于给定的正整数n&＃xff0c;格雷码为满足如下条件的一个编码序列&＃xff1a;
(1) 序列由2n个编码组成&＃xff0c;每个编码都是长度为n的二进制位串。
(2) 序列中无相同的编码。
(3) 序列中位置相邻的两个编码恰有一位不同。
例如&＃xff1a;n&＃61;2时的格雷码为&＃xff1a;{00, 01, 11, 10}。
思路&＃xff1a;和全排列是一个道理。用树结构存储每一个01结点&＃xff0c;可以得到一棵完全二叉树&＃xff0c;这样就能用数组存储这棵树。为了使序列中位置相邻的两个编码恰有一位不同&＃xff0c;一棵树子节点01则旁边一个为10。采用先序遍历&＃xff0c;保留父节点&＃xff0c;每到一个子节点就能输出一个格雷码。

通过0110重复的规律还能对二叉树进行裁枝&＃xff0c;从下标为6开始&＃xff0c;将下标对4求余后能得到正确的元素。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input &＃61; new Scanner(System.in);int times &＃61; input.nextInt();for(int k&＃61;0; k<times; k&＃43;&＃43;) {int num &＃61; input.nextInt();ArrTree t &＃61; new ArrTree(num);t.order();}}
}class ArrTree{private int[] tree &＃61; {2,0,1, 0,1,1,0};private int[] arr;private int num;private int len;public ArrTree(int num) {this.num &＃61; num;this.len &＃61; (int) Math.pow(2,num&＃43;1)-2;this.arr &＃61; new int[num];}public void print(int[] arr) {for(int i&＃61;0; i<arr.length; i&＃43;&＃43;) {System.out.printf("%d ",arr[i]);}System.out.print("\n");}public void order() {//index &＃61; 1树的下标//i &＃61; 0存当前二进制数的数组下标order(0, 1);order(0, 2);}public void order(int i, int index) {if(index > 6) {arr[i] &＃61; tree[(index-7)%4&＃43;3];}else {arr[i] &＃61; tree[index];}if(i &＃61;&＃61; num-1) {print(arr);return;}//左递归if((index*2&＃43;1) < len) {order(i&＃43;1, index*2&＃43;1);}//右递归if((index*2&＃43;2) <&＃61; len) {order(i&＃43;1, index*2&＃43;2);}}
}

三、邮票问题

设有n种不同面值a1, a2,…, an的邮票&＃xff0c;规定每封信最多贴m张邮票。对于给定的m&＃xff0c;n&＃xff0c;求出最大的邮资连续区间。例如&＃xff0c;给定n&＃61;3&＃xff0c;m&＃61;3&＃xff0c;邮票面值分别为2, 3, 5&＃xff0c;则最大的邮资连续区间为[2&＃xff0c;13]。
输入&＃xff1a;输入的第一行是一个正整数n&＃xff0c;表示测试例个数。接下来几行是n个测试例的数据&＃xff0c;每个测试例的数据由两行组成&＃xff0c;其中第一行含两个正整数n和m (1<&＃61;n, m<&＃61;10)&＃xff0c;表示有n种邮票&＃xff0c;每封信最多贴m张邮票&＃xff1b;第二行含n个正整数&＃xff0c;表示n种邮票的面值。同一行整数之间用一个空格隔开。
思路&＃xff1a;采用深度优先遍历&＃xff0c;不贴邮票表示为0&＃xff0c;这样每一层可以循环四次&＃xff0c;每次循环到了最后一层就去记录这个数。记录方式是&＃xff0c;以全部贴最大面值时的值为一个数组最后一个元素下标&＃xff1b;当找到对应下标&＃xff0c;就把这个元素置为1。最后将这个数组遍历一次记录连续为1的长度和起始下标。

import java.util.Arrays;
import java.util.Scanner;public class Stamp {static int n;static int m;static int[] tree;//static int count &＃61; 0;public static void main(String[] args) {Scanner in &＃61; new Scanner(System.in);int times &＃61; in.nextInt(); //测试次数for(int t&＃61;0; t<times; t&＃43;&＃43;) {n &＃61; in.nextInt(); //n种邮票m &＃61; in.nextInt(); //最多贴m张tree &＃61; new int[n&＃43;1];tree[0] &＃61; 0; //不贴上去for(int i&＃61;1; i<n&＃43;1; i&＃43;&＃43;) {tree[i] &＃61; in.nextInt();}System.out.println(Arrays.toString(tree));int[] value &＃61; new int[tree[n]*m&＃43;1];dfs(1, 0, value);System.out.println(Arrays.toString(value));Search(value);}}public static void dfs(int t, int sum, int[] res) {for(int i&＃61;0; i<&＃61;n; i&＃43;&＃43;) {sum &＃43;&＃61; tree[i];if(t &＃61;&＃61; m) {res[sum] &＃61; 1;sum -&＃61; tree[i];}else {dfs(t&＃43;1, sum, res);sum -&＃61; tree[i];}}}public static void Search(int[] a) {int lastLen &＃61; 1;int lastIndex &＃61; 1;int thisLen &＃61; 0;int thisIndex &＃61; 1;boolean flag &＃61; true;for(int i&＃61;1; i<a.length; i&＃43;&＃43;) {//把0屏蔽掉if(a[i] &＃61;&＃61; 1) {//连续相加&＃43;&＃43;thisLen;if(flag) {thisIndex &＃61; i;flag &＃61; false;}}else {//断开记录if(lastLen < thisLen) {lastLen &＃61; thisLen;lastIndex &＃61; thisIndex;flag &＃61; true;thisLen &＃61; 0;}}}System.out.printf("%d %d", lastIndex, lastIndex&＃43;lastLen-1);}
}