資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：檢查首位玩家能否贏得一個逐字組成字串的遊戲
假設我們有一系列單詞。現在考慮一個字謎遊戲，兩位玩家可以參與其中。玩家輪流向字串新增字母。生成的字串必須是列表中某個單詞的有效字首，拼寫出列表中任何單詞的玩家算輸。我們必須檢查如果兩位玩家都採取最佳策略，首位玩家能否獲勝。
因此，如果輸入類似於 words = ["manage", "manager", "min"]，則輸出為 True，因為他們可以這樣玩：
- m [玩家1]
- ma [玩家2]
- man [玩家1]
- mana [玩家2]
- manag [玩家1]
- manage [玩家2] 輸
所以玩家1獲勝。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個對映 mp
- 對於 words 中的每個單詞 it：
- ch := it[0]
- 將 it 插入到 mp[ch] 中
- mn := inf
- 對於 mp 中的每個鍵值對 it：
- str := it 的值
- size := str 的大小
- 如果 size mod 2 等於 0，則：
- 返回 1
- 返回 0
示例 (C++)
讓我們看看下面的實現以更好地理解：
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<string> &words) {
map<char, set<string>> mp;
for (auto &it : words) {
char ch = it[0];
mp[ch].insert(it);
}
int mn = INT_MAX;
for (auto &it : mp) {
string str = *(it.second.begin());
int size = str.size();
if (size % 2 == 0)
return 1;
}
return 0;
}
int main(){
vector<string> v = {"manage", "manager", "min"};
cout << solve(v);
}輸入
{"manage", "manager", "min"}輸出
1
更新於：2020年12月12日
143 次檢視
廣告