文思海辉第一届在线编程大赛题目解析。
这比赛一出来就想做，不过因为这种那种事，一直没时间。这几天终于抽出空来研究了一下，花了三天，每天花费一到二个小时吧，今天个人感觉算是解决了，结果兴冲冲的去提交代码，给了我这个：
最后提示失败，挑战失败，够郁闷的，虽然知道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个宝石”的问题，聪明人的思想不好代码体现啊。 --------------------编程问答-------------------- 挺有意思的
--------------------编程问答--------------------
如果把你说的这个题用计算机来实现，其实也是可以的。。
六个人的时候
1 2 3 4 5 6
99 1 0
97 0 2 1
97 0 1 0 2
96 0 1 2 1 0
从人数4个人+往后，第二人都给0
然后找出金币最少的+1，金币多的则不给，最终人数超过一半即可。 --------------------编程问答-------------------- 文思海辉不是倒闭了吗？ --------------------编程问答-------------------- 判断非递增的字符串个数偶数甲赢基数已赢 --------------------编程问答--------------------
举一个最简单的例子，
6个a和5个a非递增的字符串个数都为0
但是一个是甲赢，一个是乙赢。。。 --------------------编程问答--------------------
对不起，意思我理解错了。。 --------------------编程问答--------------------
adcad甲赢
adcca甲输
非递增个数为0和2
--------------------编程问答-------------------- 大概明白你的算法思路了：
循环去掉字符串每个字符，看看自己能否赢。
如果能赢则取这个字符，不能赢则跳过这个字符。
取字符又是一个递归操作。
能得到答案。
这种方法会将所有可能的组合遍历一遍，可能效率上会慢些。
期待更NB的解题方案~
--------------------编程问答--------------------
看不懂你的map是什么？不懂java。你测试下root和aab的过程和结果呢，等待你的测试 --------------------编程问答--------------------
map是一个缓存机制，个人感觉也是本次程序中的点睛之笔吧。
完成程序60分的话，这个map得多加30分。
由于我的程序是递归遍历性质的，所以一但遍历过aaab这样的组合之后，利用map来缓存下来结果，之后在遇到aaab这样的组合，就不会再次递归遍历，而是直接返回相应的结果。这样会极大的提高效率。
那两个结果都是甲赢。
--------------------编程问答--------------------
有点像哈希表呀
补充：Java , Java EE
