486. Predict the Winner

LeetCode medium original: C# #array #csharp #leetcode #math #medium #queue #two-pointers

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

Дан số nguyên mảng nums. Два игрока играют в игру с этим mảngом: игрок 1 и игрок 2.

Игрок 1 и игрок 2 ходят по очереди, начиная с игрока 1. Оба игрока начинают игру с нулевым счетом. В каждый ход игрок берет одно из чисел с любого конца mảngа (то есть nums[0] или nums[nums.length - 1]), что уменьшает размер mảngа на 1. Игрок добавляет выбранное number к своему счету. Игра заканчивается, когда в mảngе не останется elementов.

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

Ví dụ:

Input: nums = [1,5,2]

Output: false

Explanation: Initially, player 1 can choose between 1 and 2.

If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).

So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.

Hence, player 1 will never be the winner and you need to return

C# lời giải

đã khớp/gốc

public class Solution {
    private int MaxDiff(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int scoreByLeft = nums[left] - MaxDiff(nums, left + 1, right);
        int scoreByRight = nums[right] - MaxDiff(nums, left, right - 1);
        return Math.Max(scoreByLeft, scoreByRight);
    }
    public bool PredictTheWinner(int[] nums) {
        return MaxDiff(nums, 0, nums.Length - 1) >= 0;
    }
}

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:
    private int MaxDiff(vector<int>& nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int scoreByLeft = nums[left] - MaxDiff(nums, left + 1, right);
        int scoreByRight = nums[right] - MaxDiff(nums, left, right - 1);
        return max(scoreByLeft, scoreByRight);
    }
    public bool PredictTheWinner(vector<int>& nums) {
        return MaxDiff(nums, 0, nums.size() - 1) >= 0;
    }
}

Java lời giải

đã khớp/gốc

class Solution {
    private int maxDiff(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int scoreByLeft = nums[left] - maxDiff(nums, left + 1, right);
        int scoreByRight = nums[right] - maxDiff(nums, left, right - 1);

        return Math.max(scoreByLeft, scoreByRight);
    }

    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        return maxDiff(nums, 0, n - 1) >= 0;
    }
}

JavaScript lời giải

đã khớp/gốc

var maxDiff = function(nums, left, right) {
    if (left === right) {
        return nums[left]
    }

    let scoreByLeft = nums[left] - maxDiff(nums, left + 1, right)
    let scoreByRight = nums[right] - maxDiff(nums, left, right - 1)

    return Math.max(scoreByLeft, scoreByRight)
}

var predictTheWinner = function(nums) {
    return maxDiff(nums, 0, nums.length - 1) >= 0
}

Python lời giải

đã khớp/gốc

class Solution:
    def maxDiff(self, nums: List[int], left: int, right: int) -> int:
        if left == right:
            return nums[left]

        scoreByLeft = nums[left] - self.maxDiff(nums, left + 1, right)
        scoreByRight = nums[right] - self.maxDiff(nums, left, right - 1)

        return max(scoreByLeft, scoreByRight)

    def predictTheWinner(self, nums: List[int]) -> bool:
        return self.maxDiff(nums, 0, len(nums) - 1) >= 0

Go lời giải

đã khớp/gốc

func maxDiff(nums []int, left int, right int) int {
    if left == right {
        return nums[left]
    }

    scoreByLeft := nums[left] - maxDiff(nums, left+1, right)
    scoreByRight := nums[right] - maxDiff(nums, left, right-1)

    if scoreByLeft > scoreByRight {
        return scoreByLeft
    }
    return scoreByRight
}

func predictTheWinner(nums []int) bool {
    return maxDiff(nums, 0, len(nums)-1) >= 0
}

Algorithm

Определите maxDiff(left, right) как максимальную разницу в счете, которую текущий игрок может достичь. Если left = right, return nums[left].

В противном случае текущий игрок может выбрать nums[left] или nums[right]. Максимальная разница в счете, которую он может получить, равна большему из значений nums[left] - maxDiff(left + 1, right) и nums[right] - maxDiff(left, right - 1).

return true, если maxDiff(0, n - 1) >= 0. Этот вызов сделан с точки зрения первого игрока, и первый игрок является победителем, если у игроков одинаковый счет (разница 0).

😎

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.