486. Predict the Winner

leetcode medium

#array#csharp#leetcode#math#medium#queue#two-pointers

Task

Дан целочисленный массив nums. Два игрока играют в игру с этим массивом: игрок 1 и игрок 2.

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

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

Пример:

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# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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
}

Explanation

Algorithm

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

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

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

😎