本文共 1772 字，大约阅读时间需要 5 分钟。

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

题目：

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

两个人都足够聪明（即如果有赢的方案，都不会选输的方案 ），甲先开始，问他能赢么？

输入： 一连串英文小写字母，长度不超过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
   
     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
    
      hs = new HashMap
     
      ();		return WordGame(word, hs);	}	public static void main(String[] args) {		System.out.println(who("zzlsdjgzmcheued"));	}}
     
    
   

说明：参考了

转载地址：http://ojrsi.baihongyu.com/