1510. Stone Game IV

LeetCode hard original: C# #csharp #graph #hard #hash-table #heap #leetcode #math #queue

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

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

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

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

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

Ví dụ:

Input: n = 1

Output: true

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

C# lời giải

đã khớp/gốc

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ời giải

bản nháp tự động, xem lại trước khi gửi

#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ời giải

đã khớp/gốc

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ời giải

đã khớp/gốc

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ời giải

đã khớp/gốc

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.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.