查詢最後一個能夠從陣列中移除字串的玩家，該字串尚未從其他陣列中移除

---

在這個問題中，兩位玩家玩一個遊戲，透過從他們的陣列中移除字串來進行遊戲，該字串尚未從對方的陣列中移除。我們需要決定遊戲的贏家。

我們可以使用兩種不同的方法來解決這個問題。在第一種方法中，我們可以使用集合資料結構來儲存公共字串。在第二種方法中，我們可以使用集合來儲存兩個陣列中已經移除的字串。

問題陳述 – 我們得到了兩個名為 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)，用於將陣列值儲存到集合中。