Рубрики

Найдите победителя Игры, чтобы выиграть, удалив любые два последовательных одинаковых алфавита

Дана строка, состоящая из строчных букв.

Правила игры:

  • Игрок может выбрать пару похожих последовательных персонажей и стереть их.
  • В игре участвуют два игрока, побеждает тот, кто делает последний ход.

Задача состоит в том, чтобы найти победителя, если А идет первым и оба играют оптимально.

Примеры:

Input: str = "kaak" 
Output: B
Explanation:
    Initial String: "kaak"
    A's turn:
        removes: "aa"
        Remaining String: "kk"
    B's turn:
        removes: "kk"
        Remaining String: ""
    Since B was the last one to play
    B is the winner.

Input: str = "kk"
Output: A

Подход: мы можем использовать стек, чтобы упростить задачу.

  • Каждый раз, когда мы сталкиваемся с персонажем, который отличается от того, который присутствует в верхней части стека, мы добавляем его в стек.
  • Если вершина стека и следующий символ совпадают, мы извлекаем символ из такта и увеличиваем количество.
  • В конце нам просто нужно посмотреть, кто победит, проверив количество% 2.

Ниже приведена реализация вышеуказанного подхода:

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Функция для игры
// и найти победителя

void findWinner(string s)

{

    int i, count = 0, n;

    n = s.length();

    stack<char> st;

  

    // проверяем вершину стека с помощью

    // i-й символ строки

    // добавляем его в стек, если они разные

    // в противном случае счетчик приращений

    for (i = 0; i < n; i++) {

        if (st.empty() || st.top() != s[i]) {

            st.push(s[i]);

        }

        else {

            count++;

            st.pop();

        }

    }

  

    // Проверьте, кто победил

    if (count % 2 == 0) {

        cout << "B" << endl;

    }

    else {

        cout << "A" << endl;

    }

}

  
// Код драйвера

int main()

{

    string s = "kaak";

  

    findWinner(s);

  

    return 0;

}

Джава

// Java реализация для вышеуказанного подхода

import java.util.*;

  

class GFG 

{

  
// Функция для игры
// и найти победителя

static void findWinner(String s) 

{

    int i, count = 0, n;

    n = s.length();

    Stack<Character> st = new Stack<Character>();

  

    // проверяем вершину стека с помощью

    // i-й символ строки

    // добавляем его в стек, если они разные

    // в противном случае счетчик приращений

    for (i = 0; i < n; i++) 

    {

        if (st.isEmpty() || 

            st.peek() != s.charAt(i))

        {

            st.push(s.charAt(i));

        

        else

        {

            count++;

            st.pop();

        }

    }

  

    // Проверьте, кто победил

    if (count % 2 == 0

    {

        System.out.println("B");

    

    else

    {

        System.out.println("A");

    }

}

  
// Код драйвера

public static void main(String[] args) 

{

    String s = "kaak";

  

    findWinner(s);

}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 реализация подхода

  
# Функция играть в игру
# и найти победителя

def findWinner(s) : 

  

    count = 0

    n = len(s); 

    st = []; 

  

    # проверка вершины стека с помощью

    # i-й символ строки

    # добавить его в стек, если они разные

    # иначе счетчик приращений

    for i in range(n) :

        if (len(st) == 0 or st[-1] != s[i]) : 

            st.append(s[i]); 

              

        else

            count += 1

            st.pop(); 

  

    # Проверьте, кто победил

    if (count % 2 == 0) :

        print("B"); 

      

    else :

        print("A"); 

          
# Код драйвера

if __name__ == "__main__"

  

    s = "kaak"

  

    findWinner(s);

  
# Этот код предоставлен AnkitRai01

C #

// реализация C # для вышеуказанного подхода

using System;

using System.Collections.Generic;

  

class GFG 

{

  
// Функция для игры
// и найти победителя

static void findWinner(String s) 

{

    int i, count = 0, n;

    n = s.Length;

    Stack<char> st = new Stack<char>();

  

    // проверяем вершину стека с помощью

    // i-й символ строки

    // добавляем его в стек, если они разные

    // в противном случае счетчик приращений

    for (i = 0; i < n; i++) 

    {

        if (st.Count == 0 || 

            st.Peek() != s[i])

        {

            st.Push(s[i]);

        

        else

        {

            count++;

            st.Pop();

        }

    }

  

    // Проверьте, кто победил

    if (count % 2 == 0) 

    {

        Console.WriteLine("B");

    

    else

    {

        Console.WriteLine("A");

    }

}

  
// Код драйвера

public static void Main(String[] args) 

{

    String s = "kaak";

  

    findWinner(s);

}

  
// Этот код предоставлен 29AjayKumar

Выход:

B

Рекомендуемые посты:

Найдите победителя Игры, чтобы выиграть, удалив любые два последовательных одинаковых алфавита

0.00 (0%) 0 votes