找到最后一个能够从数组中删除字符串的玩家，该字符串尚未从其他数组中删除
在此问题中，两个玩家通过从他们的数组中删除尚未从对手的数组中删除的字符串来玩游戏。我们需要决定游戏的赢家。
我们可以使用两种不同的方法解决问题。在第一种方法中，我们可以用集合数据结构存储公共字符串。在第二种方法中，我们可以使用集合来存储已从两个数组中删除的字符串。
问题陈述– 我们给出了两个数组，分别称为 arr 和 brr。数组的大小分别为 N 和 M。我们需要决定如果玩家遵循以下规则玩游戏，哪个玩家将赢得游戏。
玩家 1 先开始游戏。
如果当前回合是玩家 1，他将从 arr[] 数组中删除一个字符串(如果该字符串尚未从数组 brr[] 中删除)。
如果当前回合是玩家 2，他将从 brr[] 数组中删除一个字符串(如果该字符串尚未从数组 arr[] 中删除)。
如果任何玩家没有字符串可删除，他将输掉游戏。
示例
输入– arr = {"tuts"}, brr = {"tuts", "tutorialspoint">
输出– '玩家 2 赢了。'
解释– 玩家 1 删除了'tuts'，玩家 2 删除了'tutorialspoint'。
现在，玩家 1 没有字符串可删除，所以他输了游戏。
输入– arr = {"tuts", "point"}, brr = {"tuts", "tutorialspoint", "acd">
输出– '玩家 2 赢了。'
解释– 玩家 1 删除了'tuts'，玩家 2 删除了'tutorialspoint'。
接下来，玩家 1 删除了'point'，玩家 2 删除了'acd'。现在，玩家 1 没有字符串可以移除，所以他输掉了游戏。
输入– arr = {"a ", "b"}, brr = {"a ", "c">
输出– '玩家 1 赢了。'
解释– 玩家 1 将移除'a'，玩家 2 将移除'c'。
之后，玩家 1 将移除'b'，玩家 2 没有字符串可以移除。
方法 1
在这种方法中，我们将从两个数组中找到公共字符串。我们假设玩家首先使用公共字符串，然后玩家使用不常见的字符串。因此，谁的常见字符串多，谁就能赢得游戏。
算法
定义常见字符串集。
比较所有 arr[] 和 brr[] 字符串，并将所有常见字符串添加到集合中。
我们需要从 arr[] 数组中找出不常见的字符串。
定义 uncommonA 集合来存储不常见的字符串。
遍历 arr[] 数组。在循环中，定义"flag"变量并用"false"值初始化它。
如果索引处为 i 的字符串存在于"common Strings"集合中，则将标志设置为 true，并中断循环。
如果"flag"为 false，则将当前字符串插入 uncommonA。
定义 unCommonB 集合，并将 brr[] 的所有不常见字符串存储在集合中，就像我们在上述步骤中对 arr[] 所做的那样。
如果共有奇数个常见字符串，则玩家 1 可以使用常见字符串进行最后一轮游戏。因此，要完成这一轮，玩家 2 需要使用一个不常见字符串。因此，将 uncommonB 的长度减少 1。
如果 uncommonA 的长度大于 lenBrr，则返回"玩家 1"。否则返回"玩家 2"。
示例
#include <bits/stdc++.h>
using namespace std;
// 查找获胜者的函数
string findWinningPlayer(vector<string> arr, vector<string> brr){
// 设置为存储通用字符串
set<string> commonStrings;
// 查找通用字符串
for (int i = 0; i < arr.size(); i++){
for (int j = 0; j < brr.size(); j++){
if (arr[i] == brr[j]){
// 插入通用字符串以进行设置
commonStrings.insert(arr[i]);
break;
}
}
}
// 从 A 中获取不常见的字符串
set<string> uncommonA;
for (int i = 0; i < arr.size(); i++){
bool flag = false;
for (auto value : commonStrings){
if (value == arr[i]){
// 如果 value == arr[i], 则表示字符串是常见的
flag = true;
break;
}
}
if (!flag)
uncommonA.insert(arr[i]);
}
// 从 B 获取不常见的字符串
set<string> uncommonB;
for (int i = 0; i < brr.size(); i++){
bool flag = false;
for (auto value : commonStrings){
if (value == brr[i]){
// 如果 value == brr[i]，则表示字符串是普通的
flag = true;
break;
}
}
if (!flag)
uncommonB.insert(brr[i]);
}
int LenBrr = uncommonB.size();
// 如果 commonStrings 的大小为奇数，则从 B 的一组不常见字符串中减少 1 个常见字符串
if ((commonStrings.size()) % 2 == 1){
// 更新 LenBrr
LenBrr -= 1;
}
if (uncommonA.size() > LenBrr){
return "Player 1 won!";
}
else{
return "Player 2 won!";
}
}
int main(){
// 玩家 A 的字符串集合
vector<string> arr{"tuts"};
// 玩家 B 的字符串集合
vector<string> brr{"tuts", "tutorialspoint"};
cout << findWinningPlayer(arr, brr);
}
输出
Player 2 won!
时间复杂度 – O(N^2)，因为我们找到了常见的字符串。
空间复杂度 – O(N + M)，因为我们将常见和不常见的字符串存储到集合中。
方法 2
在这种方法中，我们将已经使用的字符串存储在集合中以进行轮流。之后，在轮到玩家时，如果玩家没有集合中不存在的字符串，则玩家输掉游戏。
算法
将 arr[] 的所有字符串插入到 set1，将 brr[] 的所有字符串插入到 set2。
当玩家 1 轮到第一轮时，用 1 初始化"turn"变量。
使用 while() 循环进行无限迭代。
在循环中，如果 turn == 1，并且 set1 为空，则返回"player 2"。如果集合有值，则从 set1 中删除第一个值，并从 set2 中删除相同的值(如果包含)。
在循环中，如果 turn ==21，并且 set2 为空，则返回"player 1"。如果集合有值，则从集合 2 中删除第一个值，如果集合 1 包含相同的值，则从集合 1 中删除相同的值。
通过 turn -3 更改 turn 的值以交替进行 turn。
示例
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// 函数用于查找获胜者
string findWinningPlayer(vector<string> arr, vector<string> brr){
// 设置用于存储所有字符串
set<string> set1(arr.begin(), arr.end());
set<string> set2(brr.begin(), brr.end());
// 玩家 1 开始游戏
int turn = 1;
// 循环直到游戏结束
while (true){
// 如果轮到玩家 1
if (turn == 1){
// 如果玩家 1 没有要删除的字符串，则玩家 2 获胜
if (set1.empty())
return "玩家 2 赢了!";
// 从集合 1 中获取第一个字符串
auto to_remove = set1.begin();
// 从集合 1 中删除字符串
set1.erase(set1.begin());
// 在集合 2 中找到 to_remove 的位置并将其移除
auto it = set2.find(*to_remove);
if (it != set2.end())
set2.erase(it);
}
else{
// 如果玩家 2 没有要移除的字符串，则玩家 1 获胜
if (set2.empty())
return "玩家 1 获胜!";
// 从集合 2 中获取第一个字符串
auto to_remove = set2.begin();
// 从集合 2 中移除字符串
set2.erase(set2.begin());
// 在集合 1 中找到 to_remove 的位置并将其移除
auto it = set1.find(*to_remove);
if (it != set1.end())
set1.erase(it);
}
turn = 3 - turn;
}
return ""; // 永远不应该到达这一点
}
int main(){
// 玩家 A 的字符串集合
vector<string> arr{"tuts", "point"};
// 玩家 B 的字符串集合
vector<string> brr{"tuts", "tutorialspoint", "acd"};
cout << findWinningPlayer(arr, brr) << endl;
return 0;
}
输出
Player 2 won!
时间复杂度 – O(N + M)，因为我们通过交替方式从集合中删除值。
空间复杂度 – O(N + M)，用于将数组值存储在集合中。
