題目大意：
- 這是一個Leetcode平臺新型的交互式問題
我們會給定一個不重復(fù)的詞表蔚鸥，里面都是只有6個小寫字母的單詞。然后止喷，系統(tǒng)會隨機(jī)選定一個單詞作為 "secret"
你可以調(diào)用系統(tǒng)提供的API master.guess(word) 來查詢word 是否就是 "secret"。
這個API返回的參數(shù)是個整型乾巧，表示查詢的匹配程度预愤。
對于每個測試用例，你有10次查詢機(jī)會旷太。如果你能在10次以內(nèi)的查詢中找出 "secret" 則判定你通過用例销睁。
樣例輸入：
Input: secret = "acckzz", wordlist = ["acckzz","ccbazz","eiowzz","abcczz"]
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
- 詞表長度為 100
解題思路：
題目乍一看，特別像小時候 非常6+1節(jié)目睡毒，主持人讓觀眾查價格冗栗，也有反饋機(jī)制，會告訴距離目標(biāo)價格高了 還是 低了偶房。
給出的wordlist詞表長度军浆，一定會大于10。不然遍歷枚舉查詢就可以了(┑(￣Д ￣)┍)
基于貪心策略掰盘，我們應(yīng)該要利用好系統(tǒng)的反饋機(jī)制赞季，避免我們浪費(fèi)查詢機(jī)會。我們的目標(biāo)應(yīng)該是提高每次的 matches 值申钩，即每次都要淘汰詞表里不等于matches的單詞，縮小我們枚舉范圍邮偎。
每次查詢之后，如果matches不等于6豁跑，我們雖然還不知道"secret"泻云。但我們知道哪些一定不是"secret"，進(jìn)而縮小范圍卸夕，逼近答案征椒。
/**
6 / 6 test cases passed.
Status: Accepted
Runtime: 2 ms
*/
class Master {
public:
int guess(string word);
};
class Solution {
public:
int match(const string a, const string b){
int ans = 0;
for(int i = 0;i<a.length(); i++){
if(a[i] == b[i]) ++ans;
}
return ans;
}
void shrinkWordList(vector<string>& wordlits, const string guessWord, const int matches){
vector<string> tmp;
for(string word : wordlits){
int m = match(word, guessWord);
if(m == matches){
tmp.push_back(word);
}
}
wordlits = tmp;
}
void findSecretWord(vector<string>& wordlist, Master& master) {
string target = wordlist[random() % wordlist.size()];
int Count = 10;
while(Count--){
int matches = master.guess(target);
shrinkWordList(wordlist, target, matches);
target = wordlist[random() % wordlist.size()];
}
}
};
后記
注意到
Note: Any solutions that attempt to circumvent the judge will result in disqualification.
任何繞過判定的做法都會被視為 非法勃救。
比如治力，我們把Count 初始值設(shè)置為 10000，提交一下：
Output:
Either you took too many guesses, or you did not find the secret word.
：）猜測每次TC晕讲，系統(tǒng)會限制master.guess調(diào)用次數(shù)马澈。內(nèi)部控制了10次，超過10次查詢沒有得到matches=6痊班，就判定不通過用例。
這里還有一個問題馒胆，為什么100個不重復(fù)且長度都為6的單詞凝果，可以通過10次查詢一定會猜中 "secret"。
