大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 单词博弈---java实现

单词博弈---java实现

关键词:单词博弈Java单词博弈---java实现  阅读(673) 赞(14)

[摘要]本文主要是对单词博弈---java实现的讲解,希望对大家学习单词博弈---java实现有所帮助。

  前段时间做了一道题,这里mark一下。

  题目:

  甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a < b < c <…

  两个人都足够聪明(即如果有赢的方案,都不会选输的方案 ),甲先开始,问他能赢么?

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

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

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

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

  import java.util.HashMap;

  public class WordGame {

  /**

  * 判断是否严格单增

  *

  * @param str

  * @return

  */

  public static boolean judje(String str) {

  for (int i = 0; i < str.length() - 1; i++) {

  if (str.charAt(i) >= str.charAt(i + 1)) {

  return false;

  }

  }

  return true;

  }

  /**

  *  递归函数

  * @param word

  * @param has

  * @return

  */

  private static int WordGame(String word, HashMap<STRING, Integer> has) {

  //长度为2,可直接判断甲赢

  if (word.length() <= 2)

  return 1;

  //递归时,已经将做过的测试放入has中了

  if (has.containsKey(word)) {

  if (has.get(word) == 0) {

  return 0;

  } else {

  return 1;

  }

  }

  //长度为3

  if (word.length() == 3) {

  if (word.charAt(0) >= word.charAt(1) && word.charAt(1) >= word.charAt(2)) {//递增序列

  has.put(word, 0);

  return 0;

  } else {

  has.put(word, 1);

  return 1;

  }

  }

 

  //一个一个删除,看看剩下的是不是单增

  for (int i = 0; i < word.length(); i++) {

  String snew = new String(word.substring(0, i)+ word.substring(i + 1));

  if (judje(snew)) {

  has.put(word, 1);

  return 1;

  }

  }

  //如果还没判断出来,就要看是不是对方输了

  for (int i = 0; i < word.length(); i++) {

  String snew = new String(word.substring(0, i)+ word.substring(i + 1));

  if (WordGame(snew, has) == 0) {

  has.put(word, 1);

  return 1;

  }

  }

  //还没判断出来,那就是你输了

  has.put(word, 0);

  return 0;

  }

  public static int who(String word) {

  HashMap<STRING, Integer> hs = new HashMap<STRING, Integer>();

  return WordGame(word, hs);

  }

  public static void main(String[] args) {

  System.out.println(who("zzlsdjgzmcheued"));

  }

  }



相关评论