数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究查找最后一个能够从数组中移除字符串的玩家，该字符串尚未从其他数组中移除
在这个问题中，两位玩家玩一个游戏，通过从他们的数组中移除字符串来进行游戏，该字符串尚未从对方的数组中移除。我们需要决定游戏的赢家。
我们可以使用两种不同的方法来解决这个问题。在第一种方法中，我们可以使用集合数据结构来存储公共字符串。在第二种方法中，我们可以使用集合来存储两个数组中已经移除的字符串。
问题陈述 – 我们得到了两个名为 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 个索引处的字符串存在于 “公共字符串” 集合中，则将 flag 设置为 true，并退出循环。
如果 “flag” 为 false，则将当前字符串插入 uncommonA 中。
定义 unCommonB 集合，并将 brr[] 的所有非公共字符串存储到集合中，就像我们上面针对 arr[] 所做的那样。
如果共有奇数个公共字符串，则玩家 1 可以使用公共字符串进行最后一轮操作。因此，为了完成操作，玩家 2 需要使用一个非公共字符串。所以，将 uncommonB 的长度减少 1。
如果 uncommonA 的长度大于 lenBrr，则返回 “玩家 1”。否则返回 “玩家 2”。
示例
#include <bits/stdc++.h>
using namespace std;
// function to find the winner
string findWinningPlayer(vector<string> arr, vector<string> brr){
// set to store common strings
set<string> commonStrings;
// Finding common strings
for (int i = 0; i < arr.size(); i++){
for (int j = 0; j < brr.size(); j++){
if (arr[i] == brr[j]){
// insert common string to set
commonStrings.insert(arr[i]);
break;
}
}
}
// getting uncommon strings from A
set<string> uncommonA;
for (int i = 0; i < arr.size(); i++){
bool flag = false;
for (auto value : commonStrings){
if (value == arr[i]){
// If value == arr[i], it means string is common
flag = true;
break;
}
}
if (!flag)
uncommonA.insert(arr[i]);
}
// getting uncommon strings from B
set<string> uncommonB;
for (int i = 0; i < brr.size(); i++){
bool flag = false;
for (auto value : commonStrings){
if (value == brr[i]){
// If value == brr[i], it means string is common
flag = true;
break;
}
}
if (!flag)
uncommonB.insert(brr[i]);
}
int LenBrr = uncommonB.size();
// If the size of commonStrings is odd, then decrease 1 common string from a set of uncommon strings of B
if ((commonStrings.size()) % 2 == 1){
// Update LenBrr
LenBrr -= 1;
}
if (uncommonA.size() > LenBrr){
return "Player 1 won!";
}
else{
return "Player 2 won!";
}
}
int main(){
// Set of strings for player A
vector<string> arr{"tuts"};
// Set of strings for player B
vector<string> brr{"tuts", "tutorialspoint"};
cout << findWinningPlayer(arr, brr);
}
输出
Player 2 won!
时间复杂度 – O(N^2)，因为我们找到了公共字符串。
空间复杂度 – O(N + M)，因为我们将公共和非公共字符串存储到集合中。
方法 2
在这种方法中，我们将存储已使用的字符串以在集合中进行轮换。之后，在进行轮换时，如果玩家没有不在集合中的字符串，则该玩家输掉游戏。
算法
将 arr[] 的所有字符串插入 set1，将 brr[] 的所有字符串插入 set2。
将 “turn” 变量初始化为 1，因为玩家 1 先开始。
使用 while() 循环进行无限迭代。
在循环中，如果 turn == 1，并且 set1 为空，则返回 “玩家 2”。如果集合有值，则从 set1 中移除第一个值，如果包含，则从 set2 中移除相同的值。
在循环中，如果 turn == 21，并且 set2 为空，则返回 “玩家 1”。如果集合有值，则从 set2 中移除第一个值，如果包含，则从 set1 中移除相同的值。
依次更改 turn 的值 -3 以交替轮换。
示例
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// function to find the winner
string findWinningPlayer(vector<string> arr, vector<string> brr){
// set to store all strings
set<string> set1(arr.begin(), arr.end());
set<string> set2(brr.begin(), brr.end());
// player 1 starts the game
int turn = 1;
// loop until the game is over
while (true){
// if it is player 1's turn
if (turn == 1){
// if player 1 has no string to remove, player 2 wins
if (set1.empty())
return "Player 2 won!";
// get the first string from set 1
auto to_remove = set1.begin();
// remove the string from set 1
set1.erase(set1.begin());
// find the position of to_remove in set 2 and remove it
auto it = set2.find(*to_remove);
if (it != set2.end())
set2.erase(it);
}
else{
// if player 2 has no string to remove, player 1 wins
if (set2.empty())
return "Player 1 won!";
// get the first string from set 2
auto to_remove = set2.begin();
// remove the string from set 2
set2.erase(set2.begin());
// find the position of to_remove in set 1 and remove it
auto it = set1.find(*to_remove);
if (it != set1.end())
set1.erase(it);
}
turn = 3 - turn;
}
return ""; // should never reach this point
}
int main(){
// Set of strings for player A
vector<string> arr{"tuts", "point"};
// Set of strings for player B
vector<string> brr{"tuts", "tutorialspoint", "acd"};
cout << findWinningPlayer(arr, brr) << endl;
return 0;
}
输出
Player 2 won!
时间复杂度 – O(N + M)，因为我们通过交替轮换从集合中移除值。
空间复杂度 – O(N + M)，用于将数组值存储到集合中。
59 次查看
