C++ 找到逐步删除给定字符串的第一个字符以为空的游戏的获胜者

在这个游戏中，我们给出了一个长度为N的字符串数组。每个字符串只包含数字1到N。游戏从第一个人开始，他移除第0个索引的第一个字符，然后将从字符串数字player中移除的字符进行下一步操作。每个索引为y的玩家将从索引y-1处的字符串中删除数字，然后一个移除的数字将移动到下一个玩家。当任何玩家无法删除字符时，将获胜游戏。

示例

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

输入

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

输出

Player 2

解释

首先，玩家1将移除字符3，然后玩家3将移除字符2，接着玩家2将移除字符2，并且再次轮到它的回合，但此时第二个字符串的所有元素都被移除，所以它将成为游戏的赢家。

方法一

在这种方法中，我们将为每个字符串将所有的字符添加到队列中，因为这样可以轻松地弹出第一个字符。

我们将为每个玩家维护一个队列向量，并从第一个玩家开始，直到任何一个玩家的队列变为空为止，使用一个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)，因为我们使用了额外的队列向量来存储元素。

方法二

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

示例

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