294. Flip Game II

LeetCode medium original: C# #array #csharp #leetcode #medium #queue #recursion #string

题目文本会按所选界面语言从俄语翻译；代码保持不变。

LeetCode Static

Вы играете в игру Flip со своим другом.

Вам дана 字符串 currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.

return true, если начальный игрок может гарантировать победу, и false в противном случае.

示例:

Input: currentState = "++++"

Output: true

Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

C# 解法

匹配/原始

public class Solution {
    public bool CanWin(string currentState) {
        char[] stateArray = currentState.ToCharArray();
        
        for (int i = 0; i < stateArray.Length - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState = new string(stateArray);
                
                if (!CanWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

C++ 解法

自动草稿，提交前请检查

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanWin(string currentState) {
        char[] stateArray = currentState.ToCharArray();
        
        for (int i = 0; i < stateArray.size() - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState = new string(stateArray);
                
                if (!CanWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

Java 解法

匹配/原始

public class Solution {
    public boolean canWin(String currentState) {
        char[] stateArray = currentState.toCharArray();
        
        for (int i = 0; i < stateArray.length - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                String newState = new String(stateArray);
                
                if (!canWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

JavaScript 解法

匹配/原始

class Solution {
    canWin(currentState) {
        let stateArray = currentState.split('');
        
        for (let i = 0; i < stateArray.length - 1; i++) {
            if (stateArray[i] === '+' && stateArray[i + 1] === '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                let newState = stateArray.join('');
                
                if (!this.canWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

Python 解法

匹配/原始

class Solution:
    def canWin(self, currentState: str) -> bool:
        stateArray = list(currentState)
        
        for i in range(len(stateArray) - 1):
            if stateArray[i] == '+' and stateArray[i + 1] == '+':
                stateArray[i] = '-'
                stateArray[i + 1] = '-'
                newState = ''.join(stateArray)
                
                if not self.canWin(newState):
                    stateArray[i] = '+'
                    stateArray[i + 1] = '+'
                    return True
                
                stateArray[i] = '+'
                stateArray[i + 1] = '+'
        
        return False

Go 解法

匹配/原始

package main

func canWin(currentState string) bool {
  stateArray := []rune(currentState)
    
  for i := 0; i < len(stateArray)-1; i++ {
    if stateArray[i] == '+' && stateArray[i+1] == '+' {
      stateArray[i] = '-'
      stateArray[i+1] = '-'
      newState := string(stateArray)
            
      if !canWin(newState) {
        stateArray[i] = '+'
        stateArray[i+1] = '+'
        return true
      }
            
      stateArray[i] = '+'
      stateArray[i+1] = '+'
    }
  }
    
  return false
}

Algorithm

Генерация всех возможных следующих ходов:

Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--".

Рекурсивная проверка выигрыша:

Для каждого нового состояния вызовите функцию рекурсивно, чтобы проверить, может ли противник проиграть в этом новом состоянии.

Если противник не может сделать ход, return true, так как начальный игрок гарантирует победу.

Проверка всех возможных ходов:

Если для всех возможных ходов начальный игрок не может гарантировать победу, return false.

Иначе, если есть хотя бы один ход, при котором противник проигрывает, return true.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位

目前还没有活跃职位。