375. Guess Number Higher or Lower II

leetcode easy

#csharp#easy#leetcode#math

Task

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.

Вы угадываете число.

Если вы угадаете правильное число, вы выигрываете игру.

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

Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.

Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.

Пример:

Input: n = 1

Output: 0

Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

C# solution

matched/original

public class Solution {
    public int Calculate(int low, int high) {
        if (low >= high)
            return 0;
        int minres = int.MaxValue;
        for (int i = low; i <= high; i++) {
            int res = i + Math.Max(Calculate(i + 1, high), Calculate(low, i - 1));
            minres = Math.Min(res, minres);
        }
        return minres;
    }
    public int GetMoneyAmount(int n) {
        return Calculate(1, n);
    }
}

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:
    public int Calculate(int low, int high) {
        if (low >= high)
            return 0;
        int minres = int.MaxValue;
        for (int i = low; i <= high; i++) {
            int res = i + max(Calculate(i + 1, high), Calculate(low, i - 1));
            minres = min(res, minres);
        }
        return minres;
    }
    public int GetMoneyAmount(int n) {
        return Calculate(1, n);
    }
}

Java solution

matched/original

public class Solution {
    public int calculate(int low, int high) {
        if (low >= high)
            return 0;
        int minres = Integer.MAX_VALUE;
        for (int i = low; i <= high; i++) {
            int res = i + Math.max(calculate(i + 1, high), calculate(low, i - 1));
            minres = Math.min(res, minres);
        }
        return minres;
    }

    public int getMoneyAmount(int n) {
        return calculate(1, n);
    }
}

JavaScript solution

matched/original

var calculate = function(low, high) {
    if (low >= high) return 0;
    let minres = Infinity;
    for (let i = low; i <= high; i++) {
        let res = i + Math.max(calculate(i + 1, high), calculate(low, i - 1));
        minres = Math.min(res, minres);
    }
    return minres;
};

var getMoneyAmount = function(n) {
    return calculate(1, n);
};

Python solution

matched/original

class Solution:
    def calculate(self, low, high):
        if low >= high:
            return 0
        minres = float('inf')
        for i in range(low, high + 1):
            res = i + max(self.calculate(i + 1, high), self.calculate(low, i - 1))
            minres = min(res, minres)
        return minres

    def getMoneyAmount(self, n: int) -> int:
        return self.calculate(1, n)

Go solution

matched/original

package main

func calculate(low, high int) int {
    if low >= high {
        return 0
    }
    minres := int(^uint(0) >> 1)
    for i := low; i <= high; i++ {
        res := i + max(calculate(i+1, high), calculate(low, i-1))
        if res < minres {
            minres = res
        }
    }
    return minres
}

func getMoneyAmount(n int) int {
    return calculate(1, n)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.

Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.

Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.

😎