首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > JAVA > J2EE开发 >

文思海辉第一届在线编程大赛标题解析

2014-01-15 
文思海辉第一届在线编程大赛题目解析。这比赛一出来就想做,不过因为这种那种事,一直没时间。这几天终于抽出

文思海辉第一届在线编程大赛题目解析。
这比赛一出来就想做,不过因为这种那种事,一直没时间。
这几天终于抽出空来研究了一下,花了三天,每天花费一到二个小时吧,今天个人感觉算是解决了,结果兴冲冲的去提交代码,给了我这个:
文思海辉第一届在线编程大赛标题解析
最后提示失败,挑战失败,够郁闷的,虽然知道javaScript模仿编译java的代码不容易,也也不能出这种错误让人无从下手解决啊。
另外这次奖励评分标准竟然包含个人简历完整度,这一点还是蛮让人觉得别扭的,好了,不多说了,上我的代码。
题目和我写的代码如下,效率算法上有什么更好的建议也欢迎指出。


本第一次在线编程大赛由文思海辉冠名,题目如下:

甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a < b < c <....<z),则这个人胜利。两个人都足够聪明(即如果有赢的方案,都不会选输的方案 ),甲先开始,问他能赢么?

输入: 一连串英文小写字母,长度不超过15,保证最开始的状态不是一个严格单增的序列。

输出:1表示甲可以赢,0表示甲不能赢。

例如: 输入 bad, 则甲可以删掉b或者a,剩余的是ad或者bd,他就赢了,输出1。

又如: 输入 aaa, 则甲只能删掉1个a,乙删掉一个a,剩余1个a,乙获胜,输出0。


函数头部:

C:int who (const char * word);

C++:int who (string word);

Java:public static int who(String in);

C# :public static  int who(string word);

我的代码:


/**
 * @author liu
 * 本类中a代表甲,b代表乙
 */
public class TestTest {  
static Map<String,Boolean> map=new HashMap<>();

public static void main(String[] args) {
String in="aabac";
System.out.println("甲会"+(who(in)==1?"赢":"输"));
}

//头函数
public static int who(String in){
char[] charArray = in.toCharArray();
return aGet(charArray)?1:0;
}

/**
 * 模拟甲拿的过程,遍历本次拿字母的所有可能性,甲只拿能保证自己赢的字母,如果拿任何一个字母都不能赢,则返回false,代表甲会输
 */
public static boolean aGet(char[] inch) {
for (int i = 0; i < inch.length; i++) {
char[] ach = getCharArray(inch, i);
if (ach.length == 1){
//甲赢
return true;
}
if (ifIncremental(ach)) {
//甲赢
return true;
} else {
String str=new String(ach);
Boolean b = map.get(str);
boolean flag;
if(b!=null){
flag=b;
}else{
flag=bGet(ach);
map.put(str, flag);
}
if(flag==false){
//乙选择这个组合会赢,跳过判断下一个选择
continue;
}else{
//甲拿选择这个组合会赢
return true;
}
}
}
//遍历结束未返回,代表甲在这一轮无论选择哪一个字符,都会输
return false;
}


/**
 * 模拟乙拿的过程,遍历本次拿字母的所有可能性,乙只拿能保证自己赢的字母,如果拿任何一个字母都不能赢,则返回true,代表乙会输
 */
public static boolean bGet(char[] inch) {
for (int i = 0; i < inch.length; i++) {
char[] bch = getCharArray(inch, i);
if (bch.length == 1){
//乙赢
return false;
}
if (ifIncremental(bch)) {
//乙赢
return false;
} else {
String str=new String(bch);
Boolean b = map.get(str);
boolean flag;
if(b!=null){
flag=b;
}else{
flag=aGet(bch);
map.put(str, flag);
}
if(flag==true){
//甲选择这个组合会赢,跳过判断下一个选择
continue;
}else{
//乙拿选择这个组合会赢
return false;
}
}
}
//遍历结束未返回,代表乙在这一轮无论选择哪一个字符,都会输
return true;
}

/**
 * 从一个char[]集合中拿出第k个,生成一个新的集合
 */
public static char[] getCharArray(char[] ch,int k){
char[] returnchar=new char[ch.length-1];
for(int i=0;i<ch.length;i++){
if(i==k)continue;
if(i<k){
returnchar[i]=ch[i];
}
if(i>k){
returnchar[i-1]=ch[i];
}
}
return returnchar;

}

/**
 * 判断是否是递增序列
 * @param str
 * @return
 */
public static boolean ifIncremental(char[] ch){
int lasti=0;
if(ch.length==1)return true;
for(int i:ch){
if(i<=lasti)return false;
lasti=i;
}
return true;
}

//输出函数
public static void foreach(boolean AorB,char[] ch){
System.out.print(AorB?"甲":"乙"+"的选择是:");
for(char c:ch){
System.out.print(c);
}
System.out.println();
}
}  



[解决办法]
呵呵,刚刚离开这家公司,很好奇他们会搞这样的大赛!!!!
------解决方案--------------------


前两天也看了这个题目,开始想的通过排序+重复字母个数的判断,来判定输赢。后来发现,无序状态+重复字母,导致总也找不到“规律”。

这个问题挺像那个“五个强盗分100个宝石”的问题,聪明人的思想不好代码体现啊。
[解决办法]
挺有意思的文思海辉第一届在线编程大赛标题解析
[解决办法]
文思海辉不是倒闭了吗?
[解决办法]
判断非递增的字符串个数偶数甲赢基数已赢
[解决办法]
大概明白你的算法思路了:
循环去掉字符串每个字符,看看自己能否赢。
如果能赢则取这个字符,不能赢则跳过这个字符。

取字符又是一个递归操作。

能得到答案。文思海辉第一届在线编程大赛标题解析

这种方法会将所有可能的组合遍历一遍,可能效率上会慢些。
期待更NB的解题方案~文思海辉第一届在线编程大赛标题解析
[解决办法]
看不懂你的map是什么?不懂java。
你测试下root和aab的过程和结果呢,等待你的测试
[解决办法]

引用:
Quote: 引用:

看不懂你的map是什么?不懂java。
你测试下root和aab的过程和结果呢,等待你的测试

map是一个缓存机制,个人感觉也是本次程序中的点睛之笔吧。
完成程序60分的话,这个map得多加30分。
由于我的程序是递归遍历性质的,所以一但遍历过aaab这样的组合之后,利用map来缓存下来结果,之后在遇到aaab这样的组合,就不会再次递归遍历,而是直接返回相应的结果。这样会极大的提高效率。
那两个结果都是甲赢。

有点像哈希表呀

热点排行