首页 > 试题广场 >

困兽之斗

[编程题]困兽之斗
  • 热度指数:2142 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
经过深思熟虑之后,小贱君打算去M国闯一闯,那是一个古老的东方国度,传说有很多高阶魔法师,他想成为一名伟大的魔法师,将来征服星辰大海。
经过千辛万苦,小贱君终于来到了M国,不幸的是刚进城门小贱君就被M国的守城士兵困在了一种叫做“困兽之斗”的阵法之中。
士兵对小贱君说:“看到漂浮在你身边的宝石了吗?彩虹连接的两颗宝石可以任意交换位置,你需要通过一系列交换后使得宝石组成的字符串的字典序最小。若不能破阵,那还是请回吧!”
小贱君观察了一下周围的宝石,只见每颗宝石上标有一个小写字母,而且有一些宝石上通过彩虹与其他宝石相连。
琢磨了半天,他终于搞懂了这个阵法的意思:
若宝石系列为:dcba
其中有两道彩虹,分别是(0,1),(1,2),代表第一个位置上的宝石可以和第二个位置上的宝石互换,第二个位置上的宝石可以和第三个位置上的宝石互换,最终可以得到字典序最小的宝石系列:bcda。
作为小贱君的死党,你有什么方法帮助他破阵吗?

输入描述:

输入包含多组测试数据。
对于每组测试数据:
字符串s --- 代表宝石序列
n --- 代表有n条彩虹
接下来n行,每行两个数ai,bi --- 表示ai和bi由一条彩虹相连。
保证:
1<=s的长度<=10000
1<=n<=10000
且输入数据均合法。



输出描述:

对于每组数据,输出一个字符串

示例1

输入

dcba
2
0 1
1 2
hellonowcoder
4
0 1
1 4
2 5
2 3

输出

bcda
ehllonowcoder
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public String deal(ArrayList<String> list, String str) {
		StringBuffer fsb = new StringBuffer(str);
		for (int i = 0; i < list.size(); i++) {
			String s = list.get(i);
			byte[] temps = s.getBytes();
			Arrays.sort(temps);
			s = new String(temps);
			StringBuffer sb = new StringBuffer();
			for (int j = 0; j < s.length(); j++) {
				// 将这些位置上的字符拿出来排序
				int loc = Integer.valueOf(String.valueOf(s.charAt(j)));
				sb.append(str.charAt(loc));
			}
			byte[] b = sb.toString().getBytes();
			Arrays.sort(b);
			String finalstr = new String(b);
			// 按照这些顺序装上去
			for (int j = 0; j < s.length(); j++) {
				// 将这些位置上的字符拿出来排序
				int loc = Integer.valueOf(String.valueOf(s.charAt(j)));
				// loc的位置需要替换成 finalstr.charAt(j)
				fsb.delete(loc, loc + 1);
				fsb.replace(loc, loc, String.valueOf(finalstr.charAt(j)));
			}
		}
		return fsb.toString();
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		int number = Integer.valueOf(sc.nextLine());
		ArrayList<String> list = new ArrayList<String>();
		for (int i = 0; i < number; i++) {
			String l = sc.nextLine();
			String[] s = l.split(" ");
			for (int t = 0; t < list.size(); t++) {
				String string = (String) list.get(t);
				if (list.get(t).contains(s[0])) {
					string = string + s[1];
					list.set(t, string);
					break;
				} else if (list.get(t).contains(s[1])) {
					string = string + s[0];
					list.set(t, string);
					break;
				}
				if (t == list.size() - 1) {
					list.add(s[0] + s[1]);
					break;
				}
			}
			if (list.size() == 0) {
				list.add(s[0] + s[1]);
			}
		}
		Main m = new Main();
		System.out.println(m.deal(list, str));
	}

}
求大神帮我看看,通过不了。。。


发表于 2017-05-01 19:55:27 回复(0)
//自己测试一直正确,在这里就通不过。。。我也就郁闷了,求大神看一下怎么回事
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main{

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in =new Scanner(System.in);
while(in.hasNext()){
String str=in.next();
int N = in.nextInt();
int[] a = new int[N];
int[] b = new int[N];
int[] c = new int[str.length()];
int color=1;
for(int i=0;i<N;i++){
a[i]=in.nextInt();
b[i]=in.nextInt();
if(c[a[i]]==0&&c[b[i]]==0){
c[a[i]]=color;
c[b[i]]=color;
color++;
}
else if(c[a[i]]!=0&&c[b[i]]==0){
c[b[i]]=c[a[i]];
}
else if(c[a[i]]==0&&c[b[i]]!=0){
c[a[i]]=c[b[i]];
}
//else if(c[a[i]]!=0&&c[b[i]]!=0&&c[a[i]]!=c[b[i]]){
//for(int j=0;j<str.length();j++){
//if(c[j]==c[b[i]]){
//c[j]=c[a[i]];
//}
//}
//}
}
char[] tempstr=str.toCharArray();
for(int i=1;i<=color;i++){
List<Character> chr=new ArrayList<Character>();
List<Integer> index=new ArrayList<Integer>();
for(int j=0;j<tempstr.length;j++){
if(c[j]==i){
chr.add(tempstr[j]);
index.add(j);
}
}
Collections.sort(chr);
for(int j=0;j<index.size();j++){
tempstr[index.get(j)]=chr.get(j);
}
}
System.out.println(new String(tempstr));
}
in.close();
}

}

编辑于 2016-06-23 20:08:08 回复(0)