深度优先

这个家伙好懒，除了文章什么都没留下

0%

发表于 分类于
本文字数： 990 阅读时长 ≈ 1 分钟

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。

例如，输入：
ABCBA
则程序应该输出：
0

再例如，输入：
ABDCDCBABC
则程序应该输出：
3

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

这个题用递归和记忆化搜索以下就解决了。

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
public class 密码脱落 {

	static String str;
	static int[][] data;
	public static void main(String[] args) {
		
		str="C";
		data=new int[str.length()+2][str.length()+2];
		int k=f(0,str.length()-1);
		System.out.println(k);
	}
	private static int f(int i, int j) {
		
		if(i>j||i==str.length()||j==-1)
			return 0;

		if(data[i][j]!=0){
			return data[i][j];
		}
		
		if (str.charAt(i)==str.charAt(j)) {
			return f(i+1,j-1);
		}else{
			data[i][j]=Math.min(f(i+1,j)+1, f(i,j-1)+1);
			return data[i][j];
		}
	}
}

用动态规划还没做出来，先占坑位。

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

1007.5位数字黑洞

Description

任意一个5位数，比如：34256，把它的各位数字打乱，重新排列，可以得到一个最大的数：65432，一个最小的数23456。求这两个数字的差，得：41976，把这个数字再次重复上述过程（如果不足5位，则前边补0）。如此往复，数字会落入某个循环圈（称为数字黑洞）。

比如，刚才的数字会落入：[82962, 75933, 63954, 61974] 这个循环圈。

请编写程序，找到5位数所有可能的循环圈，并输出，每个循环圈占1行。其中5位数全都相同则循环圈为 [0]，这个可以不考虑。循环圈的输出格式仿照：

[82962, 75933, 63954, 61974]

其中数字的先后顺序可以不考虑。

Input

Output

[74943, 62964, 71973, 83952]

[63954, 61974, 82962, 75933]

[53955, 59994]

[0]

模拟上述过程即可，注意优化

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
import java.util.Arrays;
public class T71 {
	static int[] data=new int[10000*10+1];
	public static void main(String[] args) {
		for (int i = 10000; i <= 100000; i++) {
			if (convert(i) == 0) { //对于 XXXXX这样的数（例如33333），不用处理。
				data[i] = 1;    //标记出现过num
				continue;
			}
			if (data[i] == 1){  //已出现过的数不再处理。
				continue;
			}
			getQuan(i);
		}
	}

	private static void getQuan(int k) {
		int[] arr=new int[1000];
		arr[0]=k;
		
		//主要的不同点：将每次做差得到的数依次放进数组中，然后输出圈的时候比较方便
		//老师的将得到的数做数组下标，放进圈中，然后打印圈什么的有点复杂
		while(data[k]!=1){
			data[k]=1;
			int m=convert(k);
			k=m;
			for (int i = 1; i < arr.length; i++) {
				if(arr[i]==0){//圈中没有的数，放进圈中
					arr[i]=m;
					break;
				}else{
					if(arr[i]==m){//找到了圈，打印
						System.out.print("[");
						for (int j = i; j < arr.length; j++) {
							if(arr[j]==0){
								System.out.println("]");
								return;
							}
							System.out.print(arr[j]);
							if(arr[j+1]!=0)
								System.out.print(",");
						}
					}
				}
			}
		}
	}

	private static int convert(int n) {

		int[] arr = new int[5];
		for (int i = 0; i < 5; i++) {
			arr[i] = n % 10;
			n /= 10;
		}
		Arrays.sort(arr);
		int max = 0;
		int min = 0;
		int tenN = 1;
		for (int i = 0; i < 5; i++) {
			min = 10 * min + arr[i];
			max += tenN * arr[i];
			tenN *= 10;
		}		
		return max - min;
	}
}

老师写的方法：

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
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class T7 {
static int[] visited = new int[100000]; // 放所有出现过的数
static int[] now = new int[100000];  	//存放当前数变换出的所有结果

//双击查看原图到并打印第一次出现的圈
private static void printCircle(int num) {
	int k = num;	
	while (visited[k] != 1  && now[k] != 1 )  //如果没有遇到圈(原来没有出现，且本轮也没有出现)，则继续变换
	{now[k] = num;	 //（1）标记本轮(num起点)出现过n
	visited[k] = 1; 	 //（2）标记出现过n
	k = convert(k);	 //（3）继续变换
	}  

	if(now[k]==num){	//本轮新出现的圈	
	Queue<Integer>  queue = new LinkedList<Integer>(); //放环中的元素
	queue.add(k);	 //k入队
	k = convert(k);
	while (k != queue.peek()) {
	queue.add(k);  
	k = convert(k); 
}

System.out.print( "[");
while( queue.size()>1) {
System.out.print( queue.poll() + ",");
}
System.out.println(queue.poll()+"]");
}
}

/** 
 * @param n
 * @return 返回n变换后的值。
 * 即各位数字打乱，重新排列，得到的最大数-最小数
 */
private static int convert(int n) {
int[] arr = new int[5];
for (int i = 0; i < 5; i++) {
arr[i] = n % 10;
n /= 10;
}

Arrays.sort(arr);
int max = 0;
int min = 0;
int tenN = 1;
for (int i = 0; i < 5; i++) {
min = 10 * min + arr[i];
max += tenN * arr[i];
tenN *= 10;
}	
return max - min;
}

public static void main(String[] args) {

for (int num = 10000; num < 100000; num++) {	//穷举五位数	

if (convert(num) == 0) { //对于 XXXXX这样的数（例如33333），不用处理。
visited[num] = 1;    //标记出现过num
continue;
}

if (visited[num] == 1)  //已出现过的数不再处理。
continue;

printCircle(num);	 //输出圈（只输出第一次出现的情况）
}
}
}

发表于 分类于
本文字数： 922 阅读时长 ≈ 1 分钟

1006.最长连续字母序列的长度

Description

给定一个 query 和一个 text,均由小写字母组成。要求在 text 中找出以同样的顺序连续出现在 query 中的最长连续字母序列的长度。例如, query 为“acbac”,text 为 “acaccbabb”,那么 text 中的“cba”为最长的连续出现在 query 中的字母序列,因此, 返回结果应该为其长度 3。请注意程序效率。

注意：变量在程序中直接赋值

String query = “acbac”;

String text = “acaccbabb”;

二维数组，打表做

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
import java.util.Scanner;

public class T6 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		String s1=sc.nextLine();
		String s2=sc.nextLine();
		sc.close();
		int n=getStrMax(s1,s2);
		System.out.println(n);
	}

	private static int getStrMax(String s1, String s2) {
		int n=s1.length();
		int m=s2.length();

		int[][] data=new int[n+1][m+1];
		int max=0;
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < m+1; j++) {
				if(s1.charAt(i-1)==s2.charAt(j-1)){
					data[i][j]=data[i-1][j-1]+1;
				}else{
					data[i][j]=0;
				}
				
				if(data[i][j]>max){
					max=data[i][j];
				}
			}
		}
		return max;
	}
}