2つのインプリメンテーション(java)—poj 2718

以前出会った全配列、清一色のdfsは遡って、自分が時間の複雑さが高いことを知っていて、最近poj 2718に出会って真剣に下全配列をまとめました.
全配列:いくつかの数を指定し、すべての配列方法を見つける必要があります.
法一:dfs遡及法:

構想:遡及法の核心構想はシミュレーション過程であり、実際には比較的簡単である.次のステップが何であるかを考える必要がないため、これらの数を操作する場合に注目するだけだ.数のルールを気にしないかもしれませんが、できます.

例を挙げます.1,2,3,4,5の5つの数が全配列を必要とする.遡及法を使うと、追加の配列やlist、boolean配列などでシミュレーションのデータを追加したり削除したりすることができます.

例えば、最初の賦値(1-5)をループして、各数を賦値するときに使用したデータをマークし、dfsを最後まで実行します.その後、dfsはデータを復元するために実行します.例えば、マークされたデータをキャンセルするなどです.

詳細コードは

import java.util.Scanner;

public class quanpailie1 {
	public static void main(String[] args) {
				Scanner sc=new Scanner(System.in);
				String s[]=sc.nextLine().split(" ");
				int a[]=new int[s.length];
				for(int i=0;iint b[]=new int[a.length];
				boolean b1[]=new boolean[a.length];//      
				long startTime = System.currentTimeMillis();
				dfs(b1,a,b,0);
				long endTime = System.currentTimeMillis();
				System.out.println("    :" + (endTime - startTime) + "ms");
			}

			private static void dfs(boolean[] b1, int[] a, int b[], int index) {
				// TODO Auto-generated method stub
				int len=a.length;
				if(index==a.length)//  
				{
					if(b[0]==0) {}
					else {
						for(int j:b)
						{
							System.out.print(j+"  ");
						}
						System.out.println();
					}				
				}
				else 
				for(int i=0;iif(!b1[i]) {
						b[index]=a[i];
						b1[i]=true;//      
						dfs(b1, a, b,index+1);
						b1[i]=false;//  
						
					}
				}
				
			}
}

出力印刷結果:
入力:1 2 3 3 4 1 2 3 3 4 1 2 4 3 3 3 3 3 3 3 4 2 4 4 1 4 2 4 3 3 3 2 1 3 4 4 3 3 3 1 4 4 4 4 4 4 1 3 4 4 3 3 3 3 3 3 3 3 3 3 1 3 3 3 3 1 3 4 4 2 3 1 4 3 2 1 4 3 4 4 1 3 4 4 4 4 4 4 2 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 2 1 4 3 3 3 4 4 2 3 3 3 3 3 3 3 3 1 4 3 3 3 3 1 4 3 3 4 4 4 3 2 1運転時間:2 ms
法二:再帰法
上記の方法は全配列を実現できるが,方法の複雑さは依然として高い.指数レベルの増加.無駄なことをたくさん経験しなければならないからです.そのため、データが大きいと高速に処理できません.だから考えを変えて処理します.[a,b,c,d]をabcdの全配列とすると,この全配列は[1,2,3,4](4つの数の全配列)=

1[2,3,4](1先頭[2,3,4]の全配列)=

1 2 2[3,4]=(1,2先頭の[3,4]全配列)==

1 2 3[4]=12 3 4(1 2 3の先頭の[4]全配列)

1 2 4 [3]=1 2 3 4

1 3 [2,4]

1 3 2 [4]=1 3 2 4

1 3 4 [2]=1 3 4 2

1 4 [3,2]

1 4 3 [2]=1 4 3 2

1 4 2 [3]=1 4 2 3

2 [1,3,4]=

2 1 [3,4]

2 1 3 [4]=2 1 3 4

2 1 4 [3]=2 1 4 3

2 3 [1,4]

2 3 1 [4]=2 3 1 4

2 3 4 [1]=2 3 4 1

2 4 [3,1]

2 4 3 [1]=2 4 3 1

2 4 1 [3]=2 4 1 3

3[2,1,4]=(略)

3 2 [1,4]

3 1 [2,4]

3 4 [3,2]

4[2,3,1]=(略)

4 2 [3,1]

4 3 [2,1]

4 1 [3,2]

全配列再帰のモードは、(dfsに似ている)

isstop?: 判断再帰終了

stop

do not stop:

before recursive()

recursive()

after recursive()

上のデータに基づいて法則を探しましょう.

上は再帰的で問題ありません.全配列は、サブ配列が最後の遍歴に再帰するすべての場合

である.

くれぐれも遡及的に全配列のデータの影響を得るために使用されないでください.ブロガーはこれまで遡及して得られたデータから再帰的な関係を見つけようと長い間カードを押していたが、書いているうちに書き崩れてしまった.

再帰データは規則的である.データのサイズ配列ではなく、位置のみに注目します.それぞれの配列の初期状態が何なのか悩む必要はありません.彼がそれらの数を持っていることに注目すればいいです.例を挙げると、1[2,3,4]と1[4,3,2]の効果と同じように、1という部分に注目する必要があります.1この部分を再帰的に処理すると,自然にサブノードの関係がうまく処理される.

は、1[],2[],3[],4[],例えば1,2,3,4のような同じ階層に対して、各層が次のようなステップであり、同層データの信頼性を保証することができ、下位層が以下のような考え方で正しい.

1,2,3,4—>swap(0,0)—>1[23 4](サブ再帰は気にしない)—>swap(0,0)—>1,2,3,4,

1,2,3,4—>swap(0,1)—>2[13 4](サブ再帰は気にしない)—>swap(0,1)—>1,2,3,4,

1,2,3,4—>swap(0,2)—>3[21 4](サブ再帰は気にしない)—>swap(0,1)—>1,2,3,4,

1,2,3,4—>swap(0,3)—>4[23 1](サブ再帰は気にしない)—>swap(0,1)—>1,2,3,4

ですので、全配列関数全体は概ね次のようになります.

停止

停止しない:-for(i from start to end)

swap(start,i)/iは、その層の後ろのすべての可能なすべてから、その層

に一度に配列する.

recursive(start+1)/この層は決定し、次の層に入るサブ再帰

swap(start,i)/同層間のデータに影響しないため、データが初期話であることを保証する具体的なコードは:

import java.util.Scanner;
public class quanpailie2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		String s[] = sc.nextLine().split(" ");
		int a[] = new int[s.length];
		for (int i = 0; i < s.length; i++) {
			a[i] = Integer.parseInt(s[i]);
		}
		long startTime = System.currentTimeMillis();
		arrange(a, 0, a.length - 1);
		long endTime = System.currentTimeMillis();
		System.out.println("    :" + (endTime - startTime) + "ms");
	}
	static void arrange(int a[], int start, int end) {

		if (start == end) {		
			for (int i : a) {
				System.out.print(i);
			}
			System.out.println();
			return;
		}
		for (int i = start; i <= end; i++) {
			swap(a, i, start);
			arrange(a, start + 1, end);
			swap(a, i, start);
		}
	}

	static void swap(int arr[], int i, int j) {
		int te = arr[i];
		arr[i] = arr[j];
		arr[j] = te;
	}
}

入出力結果:
1 2 3 4 1234 1243 1324 1342 1432 1423 2134 2143 2314 2341 2431 2413 3214 3241 3124 3142 3412 3421 4231 4321 4312 4132 4123運転時間:1 ms
両者のルールが異なり、出力されたデータが後で異なることがわかります.しかし、大きなデータがプログラムの実行に与える影響はまだ体験されていないかもしれません.出力した結果を注釈します.0 1 2 3 4 5 6 7 8 9でフルソート:
全配列については、再帰か再帰かを推奨します.再帰的に追加の配列オーバーヘッドがないためです.そして計算するたびに役に立ちます.遡及すると無駄な計算がたくさんあります数が大きいほど明らかになる.
poj2718
問題は、重複しない数字をいくつか与えて、その中のすべての配列方式で構成されている2つの数の差を最小にすることです.サイズが0の場合を除き、0は先頭になりません.
考え方:すべての状況を並べます.一番小さいのは、この全配列が真ん中から2半に分かれている配列差に違いない.注意したいのは、0の処理、3つの長さの0の先頭/その他の長さの0の先頭などです.貪欲な枝切りを採用する人もいる.個人的にはデータがそんなに規則的ではないと感じていますが、欲張りは必ずしもうまく処理できませんが、適切に枝を切って時間を減らすことができます.例えば、2つのデータのトップに基づいて、対応する枝を切ります.しかし、この問題は全部並べておけばいいです.
もう一つは、データの加減乗除変換で、intでStringを使わないで、stringが遅くなるとタイムアウトします.
acコードを添付します.コードはきれいではないかもしれませんが、前の紹介も漏れているかもしれません.ご指摘ください.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class poj2718 {

	static int min = Integer.MAX_VALUE;
	static int mid = 0;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(in.readLine());
		for (int q = 0; q < t; q++) {
			String s[] = in.readLine().split(" ");
			int a[] = new int[s.length];
			for (int i = 0; i < s.length; i++) {
				a[i] = Integer.parseInt(s[i]);
			}
			min = Integer.MAX_VALUE;
			mid = (a.length) / 2;
			arrange(a, 0, a.length - 1);
			out.println(min);
			out.flush();
		}
	}
	static void arrange(int a[], int start, int end) {

		if (start == end) {
//			for(int i:a)
//			{
//				System.out.print(i);
//			}
//			System.out.println();

			if ((a[0] == 0 && mid == 1) || (a[mid] == 0 && a.length - mid == 0) || (a[0] != 0 && a[mid] != 0)) {
				int va1 = 0;
				int va2 = 0;
				for (int i = 0; i < mid; i++) {
					va1 = va1 * 10 + a[i];
				}
				for (int i = mid; i < a.length; i++) {
					va2 = va2 * 10 + a[i];
				}
				min = min < Math.abs(va1 - va2) ? min : Math.abs(va1 - va2);
			}
			return;
		}
		for (int i = start; i <= end; i++) {
			swap(a, start, i);
			arrange(a, start + 1, end);
			swap(a, start, i);
		}
	}

	static void swap(int arr[], int i, int j) {
		int te = arr[i];
		arr[i] = arr[j];
		arr[j] = te;
	}
}

dfs遡及githubリンク
再帰法全配列githubリンク
poj 2718コードgithubリンク
もし間違いがあったら,大物に指摘してください.
転載先:https://juejin.im/post/5cdfb9fa5188251ce35d50ae