查找反复移除第一个字符直至字符串为空的游戏获胜者

---

在这个游戏中，我们得到一个长度为 N 的字符串数组。每个字符串仅由数字 1 到 N 组成。游戏从第一个人开始，移除第 0 个索引的第一个字符，然后由被移除字符对应的数字玩家进行下一步操作。每个索引为 y 的玩家将移除索引为 y-1 的字符串中的数字，然后由被移除数字对应的玩家继续操作。当任何玩家无法移除字符时，该玩家获胜。

示例

让我们通过输入输出示例来理解这个问题：

输入

string arr[] = {"323", "2", "2"}

输出

Player 2

解释

第一个玩家 1 将移除字符 3，然后玩家 3 将移除字符 2，然后玩家 2 将移除字符 2，并且再次轮到他，但是现在第二个字符串的所有元素都被移除了，他将赢得游戏。

方法 1

在这种方法中，我们将把所有字符串字符添加到每个字符串的队列中，因为这将使弹出第一个字符更容易。

我们将为每个玩家维护一个队列向量，并从第一个玩家开始，直到任何玩家的队列为空，使用 while 循环。

在每次迭代中，我们将弹出第一个字符并将其存储在新字符中，因为这将是我们的下一个玩家。

示例

#include <bits/stdc++.h>
using namespace std;

// function to get the winner of the game 
int getWinner(vector<string>& arr){
   int len = arr.size(); // maximum number of players 
   // storing each string character to the queue to make poping first character easy 
   // also convert character to an integer to make accessing easy 
   vector<queue<int>> q(len);
   // using for loop, traversing over the array 
   for(int i = 0; i < len; i++){
      // get the current string length 
      int cur_len = arr[i].size();
      // using nested for loop traverse over the current string 
      for (int j = 0; j < cur_len; j++){
         // push current character to the string by making it integer 
         q[i].push(arr[i][j] - '1');
      }
   }
   // starting with the first player
   int cur_player = 0;
   // using while loop traversing over the vector of queue 
   while(q[cur_player].empty() == false){
      // get the next player 
      int nextPlayer = q[cur_player].front();
      // remove current player 
      q[cur_player].pop();
      // update player to next player
      cur_player = nextPlayer;
   }
   // return the winner 
   return cur_player + 1;
}
int main(){
   int N = 3; // number of players
   vector<string> arr = { "323", "2", "2" }; // given array 
   // calling the function to get the winner 
   cout<<"The winner of the game is the player:" << getWinner(arr) << endl;
   return 0;
}

输出

The winner of the game is the player: 2

时间和空间复杂度

上述代码的时间复杂度为 O(N*M)，其中 N 为玩家数或数组大小，M 为字符串大小。

空间复杂度与时间复杂度相同，即 O(N*M)，因为我们使用额外的队列向量来存储元素。

方法 2

在这种方法中，我们将仅使用指针替换队列，指针将遍历到下一个位置，而不是弹出最后一个字符，只需将指针移动到下一个位置，直到任何玩家的指针到达各自的末尾并获胜。让我们看看代码：

示例

#include <bits/stdc++.h>
using namespace std;
// function to get the winner of the game 
int getWinner(vector<string>& arr){
   int len = arr.size(); // maximum number of players 
   vector<queue<int>> q(len);
   // using for loop, traversing over the array 
   for(int i = 0; i < len; i++){
      // get the current string length 
      int cur_len = arr[i].size();
      // using nested for loop traverse over the current string 
      for (int j = 0; j < cur_len; j++){
         // push current character to the string by making it integer 
         q[i].push(arr[i][j] - '1');
      }
   }
   // starting with the first player
   int cur_player = 0;
   // using while loop traversing over the vector of queue 
   while(q[cur_player].empty() == false){
      int nextPlayer = q[cur_player].front(); // get the next player 
      q[cur_player].pop(); // remove current player 
      cur_player = nextPlayer;// update player to next player
   }
   return cur_player + 1; // return the winner 
}
int main(){
   int N = 3; // number of players
   vector<string> arr = { "323", "2", "2" }; // given array 
   cout<<"The winner of the game is the player:" << getWinner(arr) << endl;
   return 0;
}

输出

The winner of the game is the player: 2

时间和空间复杂度

上述代码的时间复杂度为 O(N*M)，其中 N 为玩家数或数组大小，M 为字符串大小。

空间复杂度为 O(N)，因为我们只使用一个大小为 N 的线性数组。

结论

在本教程中，我们实现了一个程序来查找游戏获胜者，在这个游戏中，我们得到一个大小为 N 的数组，其中包含包含 1 到 N 范围内字符的字符串。从玩家 1 开始，我们将移动到从前一个玩家的字符串中移除字符的玩家。我们已经实现了两个具有相同时间复杂度的程序和一个具有更好空间复杂度的程序。