1510. Stone Game IV

LeetCode hard original: C# #csharp #graph #hard #hash-table #heap #leetcode #math #queue
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
LeetCode Static

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

Изначально в куче n камней. В ходе каждого хода игрок удаляет любое ненулевое количество камней, являющееся квадратом целого числа.

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

given положительное Ganzzahl n, return true, если и только если Алиса выиграет игру, иначе return false, предполагая, что оба игрока играют оптимально.

Beispiel:

Input: n = 1

Output: true

Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

C# Lösung

zugeordnet/original 
public class Solution {
    public bool WinnerSquareGame(int n) {
        Dictionary<int, bool> cache = new Dictionary<int, bool>();
        cache[0] = false;
        return Dfs(cache, n);
    }
    public bool Dfs(Dictionary<int, bool> cache, int remain) {
        if (cache.ContainsKey(remain)) {
            return cache[remain];
        }
        int sqrtRoot = (int) Math.Sqrt(remain);
        for (int i = 1; i <= sqrtRoot; ++i) {
            if (!Dfs(cache, remain - i * i)) {
                cache[remain] = true;
                return true;
            }
        }
        cache[remain] = false;
        return false;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
#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 WinnerSquareGame(int n) {
        unordered_map<int, bool> cache = new unordered_map<int, bool>();
        cache[0] = false;
        return Dfs(cache, n);
    }
    public bool Dfs(unordered_map<int, bool> cache, int remain) {
        if (cache.count(remain)) {
            return cache[remain];
        }
        int sqrtRoot = (int) Math.Sqrt(remain);
        for (int i = 1; i <= sqrtRoot; ++i) {
            if (!Dfs(cache, remain - i * i)) {
                cache[remain] = true;
                return true;
            }
        }
        cache[remain] = false;
        return false;
    }
}

Java Lösung

zugeordnet/original 
class Solution {
    public boolean winnerSquareGame(int n) {
        HashMap<Integer, Boolean> cache = new HashMap<>();
        cache.put(0, false);
        return dfs(cache, n);
    }

    public boolean dfs(HashMap<Integer, Boolean> cache, int remain) {
        if (cache.containsKey(remain)) {
            return cache.get(remain);
        }
        int sqrt_root = (int) Math.sqrt(remain);
        for (int i = 1; i <= sqrt_root; i++) {
            if (!dfs(cache, remain - i * i)) {
                cache.put(remain, true);
                return true;
            }
        }
        cache.put(remain, false);
        return false;
    }
}

JavaScript Lösung

zugeordnet/original 
var winnerSquareGame = function(n) {
    const cache = new Map();
    cache.set(0, false);

    const dfs = (remain) => {
        if (cache.has(remain)) {
            return cache.get(remain);
        }
        const sqrtRoot = Math.floor(Math.sqrt(remain));
        for (let i = 1; i <= sqrtRoot; i++) {
            if (!dfs(remain - i * i)) {
                cache.set(remain, true);
                return true;
            }
        }
        cache.set(remain, false);
        return false;
    };

    return dfs(n);
};

Go Lösung

zugeordnet/original 
func winnerSquareGame(n int) bool {
    cache := map[int]bool{0: false}
    return dfs(cache, n)
}

func dfs(cache map[int]bool, remain int) bool {
    if res, exists := cache[remain]; exists {
        return res
    }
    sqrtRoot := int(math.Sqrt(float64(remain)))
    for i := 1; i <= sqrtRoot; i++ {
        if !dfs(cache, remain-i*i) {
            cache[remain] = true
            return true
        }
    }
    cache[remain] = false
    return false
}

Algorithm

Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.