C++ 找到最后一个玩家能够从数组中删除一个未从其他数组中删除的字符串

在这个问题中，两名玩家通过从他们的数组中删除字符串来进行游戏，这些字符串在对手的数组中尚未删除。我们需要决定游戏的获胜者。

我们可以使用两种不同的方法来解决这个问题。在第一种方法中，我们可以使用集合数据结构存储公共字符串。在第二种方法中，我们可以使用一个集合来存储已从两个数组中删除的字符串。

问题陈述 –给定两个称为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集合，并像上面对arr[]一样存储brr[]的所有非常见字符串。
如果有奇数个共同的字符串，玩家1可以带着共同的字符串进行最后一次操作。所以，为了完成这一回合，玩家2需要使用一个非常见的字符串。所以，将uncommonB的长度减1。
如果uncommonA的长度大于lenBrr，则返回‘player 1’。否则返回‘player 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为空，则返回’player 2’。如果集合中有值，则从set1中删除第一个值，并且如果set2包含该值，则从set2中删除相同的值。
在循环中，如果turn 21，并且set2为空，则返回’player 1’。如果集合中有值，则从set2中删除第一个值，并且如果set1包含该值，则从set1中删除相同的值。
通过turn – 3来改变turn的值以交替回合。

示例

#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;
}