首页 > 程序开发 > 软件开发 > Java >

单词博弈 --- java实现

2014-01-06

前段时间做了一道题,这里mark一下。 题目: 甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严& 26684;单调递增的(按字典序a < b < c = word

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

题目:

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

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

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

输出: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"));
	}

}


说明:参考了https://blog.csdn.net/miss_ruochen/article/details/17199887


热点推荐