文思海辉第一届在线编程大赛题目解析。
这比赛一出来就想做，不过因为这种那种事，一直没时间。
这几天终于抽出空来研究了一下，花了三天，每天花费一到二个小时吧，今天个人感觉算是解决了，结果兴冲冲的去提交代码，给了我这个：
最后提示失败，挑战失败，够郁闷的，虽然知道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();
}
}
