題目

騰訊算法題-題干如下：

有甲乙兩家伙用一個(gè)英語(yǔ)單詞玩游戲（無(wú)聊的人還是很多的！！！）。兩個(gè)人輪流進(jìn)行，每個(gè)人每次從中刪掉任意一個(gè)字母，如果剩余的字母序列是嚴(yán)格單調(diào)遞增的（按字典序a < b < c <….),那就誰(shuí)贏。

輸入： 一連串英文小寫(xiě)字母，長(zhǎng)度任意（當(dāng)然要在計(jì)算機(jī)能承受的范圍內(nèi)）,保證最開(kāi)始的狀態(tài)不是一個(gè)嚴(yán)格單增的序列。

**輸出：**1表示甲可以贏，0表示甲不能贏。

例如: 輸入 bad， 則甲可以刪掉b或者a,剩余的是ad或者bd，他就贏了，輸出1。

又如: 輸入 aaa， 則甲只能刪掉1個(gè)a，乙刪掉一個(gè)a,剩余1個(gè)a，乙獲勝，輸出0。

---

解法

下面給出我用Java實(shí)現(xiàn)的算法，如果大家有其他的實(shí)現(xiàn)方法，歡迎跟帖和探討。語(yǔ)言不限。

1）算法邏輯

我的基本實(shí)現(xiàn)思路將給定的單詞分成若干個(gè)單調(diào)遞增的序列，然后按每個(gè)序列中包含單詞個(gè)數(shù)多少進(jìn)行遞減排序，也就是說(shuō)，排在前面的單調(diào)遞增序列中包含的字母?jìng)€(gè)數(shù)最少。然后由甲開(kāi)始從排在前面的遞增序列中選擇一個(gè)字母。直到該遞增序列中的字母全部被選中。然后繼續(xù)從下一個(gè)遞增序列選擇字母。按著這樣的方法做，直到剩下最后一個(gè)單調(diào)遞增序列，隨最后選擇了倒數(shù)第二個(gè)單調(diào)遞增序列中的最后一個(gè)字母，誰(shuí)就贏了。

例如，單詞hela，可以分為三個(gè)單調(diào)遞增序列：h、el、a。從甲開(kāi)始選擇。

甲：h

乙：a

由于a是倒數(shù)第二個(gè)單調(diào)遞增序列的最后一個(gè)字母，所以乙贏了。

注意：存儲(chǔ)單調(diào)遞增序列的集合中的單調(diào)遞增序列必須是按單詞順序放入數(shù)組的。例如上面的例子hela，若拆分為：h，a，el，的順序放入到集合當(dāng)中，然后我們刪除時(shí)，從h（即集合中第一個(gè)單調(diào)遞增序列開(kāi)始），則會(huì)出現(xiàn)問(wèn)題，若乙刪除“l(fā)”的話，按這個(gè)順序，甲贏，但是此時(shí)的單詞是ea，甲并沒(méi)有贏。

對(duì)于單詞money可以分成三個(gè)單調(diào)遞增序列：mo、n、ey。排序后：n、mo、ey。

甲：n

乙：m

甲：o

所以甲贏。

代碼如下：

public class Test {// 實(shí)現(xiàn)算法的方法，in為一個(gè)給定的單詞public static int who(String in){// 基本思路就是找到該單詞中所有遞增的子序列，然后從字符最少的子序列甲乙輪回刪除字母，直到還剩下最后一個(gè)子序列為止// 誰(shuí)刪除了最后一個(gè)字母，誰(shuí)就贏了！// in不能為nullif(in == null)return 0;// 單詞至少需要有一個(gè)字母if(in.length() == 0)return 0;in = in.toLowerCase(); // 都變成小寫(xiě)字母// 所有遞增數(shù)列集合java.util.List ascendingList = new java.util.ArrayList();char lastChar = in.charAt(0);StringBuilder sb = new StringBuilder(); // 存儲(chǔ)當(dāng)前遞增的字符列表sb.append(lastChar);for(int i = 1; i < in.length(); i++){// 當(dāng)前字符屬于當(dāng)前的遞增序列if(in.charAt(i) > lastChar){sb.append(in.charAt(i));}// 當(dāng)前字符屬于下一個(gè)遞增序列，所以需要存儲(chǔ)上一個(gè)遞增序列else{ascendingList.add(sb);sb = new StringBuilder(); sb.append(in.charAt(i));}lastChar = in.charAt(i);}if(sb.length() > 0){ascendingList.add(sb);}// 下面就開(kāi)始游戲了// 從甲開(kāi)始刪字母，從字符最少的遞增序列開(kāi)始刪除第一個(gè)字母，直到之后只剩下一個(gè)遞增序列為止，誰(shuí)刪除的最后一個(gè)之母，誰(shuí)就贏了// 這里本應(yīng)該判斷如果單詞本身就是遞增序列，那么甲就win了，不過(guò)既然題目說(shuō)沒(méi)有這種情況，所以就注釋掉了/*if(ascendingList.size() == 1){return 1;}*/java.util.Collections.sort(ascendingList, new java.util.Comparator(){@Overridepublic int compare(StringBuilder sb1, StringBuilder sb2){if(sb1.length() > sb2.length()){return 1;}else if(sb1.length() == sb2.length()){return 0;}else {return -1;}}});int win = 0; // 1代表甲贏，0代表乙贏while(ascendingList.size() > 1){if(win == 0)win = 1; // 甲開(kāi)始elsewin = 0; // 乙開(kāi)始// 刪除第一個(gè)遞增序列的第一個(gè)字母，如果該遞增序列ascendingList.get(0).delete(0, 1);if(ascendingList.get(0).length() == 0){ascendingList.remove(0);}}return win;}public static void main(String[] args){System.out.println(who("money"));} }

請(qǐng)尊重原創(chuàng)，原文地址：https://geekori.com/blogDetails.php?blog_id=14

總結(jié)

以上是生活随笔為你收集整理的算法--腾讯面试：单词游戏，谁会赢？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。