Electroni c shop hackerRank Challenge в Javascript

Question

Привет, я не прошел все тесты, только 9/16. поэтому я хочу знать, в чем проблема в моей ссылке на проблему с кодом: https://www.hackerrank.com/challenges/electronics-shop/problem

function getMoneySpent(keyboards, drives, b) {
    let arr = [];
   let lenOfArr1 = keyboards.length;
    let lenOfArr2 = drives.length;
    let j = drives.length;
    arr = keyboards.slice(0);
    for (let number of drives) {
        arr.push(number);
    }
    return (challenge(arr, lenOfArr1, b));
}


function challenge(arr, lenOfArr1, m) {
    let result = [];
   let j = lenOfArr1;
    for (let i = 0; i < lenOfArr1; i++) {
        if (arr[i] >= m || arr[j] >= m) return -1;
        if (arr[i] + arr[j] < m) {
            result.push(arr[i] + arr[j]);
        }
        i--;
        j++;
        if (j == arr.length) {
            i++;
            j = lenOfArr1;
        }
    }
    if (result.length == 0) return -1;
    return result.sort()[result.length - 1];
}

Answer 1

Следующая строка заставляет ваш код возвращать -1, когда может быть решение:

if (arr[i] >= m || arr[j] >= m) return -1;

Даже если одна цена может быть выше бюджета, вы должны учитывать, что могут быть доступны более дешевые товары. Возможно, у вас уже есть решения в result, или они все еще могут быть найдены в более поздней итерации.

Мне не ясно, зачем вы сначала создаете объединенный массив из обоих входных массивов. Похоже, что это не приносит никакой пользы.

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

function getMoneySpent(keyboards, drives, b) {
    keyboards = [...keyboards].sort((a, b) => b - a) // descending
    drives = [...drives].sort((a, b) => a - b); // ascending
    let k = keyboards.length - 1; // cheapest
    let d = drives.length - 1; // most expensive
    let maxSum = -1;
    while (d >= 0 && k >= 0) {
        let sum = keyboards[k] + drives[d];
        if (sum === b) return b;
        if (sum < b) {
            if (sum > maxSum) maxSum = sum;
            k--; // will increase sum 
        } else {
            d--; // will decrease sum
        }
    }
    return maxSum;
}

Answer 2

Исходя из ограничений в постановке задачи, вам не нужно такое сложное решение.

Вот алгоритм:

1. Инициализировать переменную maxValue, чтобы иметь значение как -1.
2. Начните два цикла for для drives и keyboards, возьмите все комбинации и просуммируйте значение каждого drive с каждым keyboard.
3. Внутри в циклах for проверьте, должна ли сумма drive + keyboard быть меньше или равна сумме денег, которые есть у Моники, и отслеживайте максимальное значение, которое вы получаете от любой комбинации в maxValue.
4. После вычисление кода, возврат maxValue.

Код: -

function getMoneySpent(keyboards, drives, b) {
    let maxValue = -1;
    for (let drive of drives) {
        for(let keyboard of keyboards) {
            let cost = drive + keyboard;
            if(cost > maxValue && cost <= b) {
                maxValue = cost;
            }
        }
    }
    return maxValue;
}

Общая временная сложность - O(n^2).

Надеюсь, это поможет!