Блог

Я решал задачу для игры в два стека на Hackers rank и застрял. Проблема в том, что мое решение не работает для других тестовых случаев.

https://www.hackerrank.com/challenges/game-of-two-stacks

У Alexa есть два стека неотрицательных целых чисел, стек A и стек B, где индекс 0 обозначает вершину стека. Алекса предлагает Нику сыграть в следующую игру:

За каждый ход Ник может удалить одно целое число из верхней части стека A или стека B.

Ник хранит текущую сумму целых чисел, которые он удаляет из двух стеков.

Ник выбывает из игры, если в какой-либо момент его текущая сумма становится больше некоторого целого числа X, указанного в начале игры.

Итоговый результат Ника — это общее количество целых чисел, которые он удалил из двух стеков.

найдите максимально возможный результат, которого может достичь Ник (т. Е. Максимальное количество целых чисел, которые он может удалить, не будучи дисквалифицированным) во время каждой игры, и выведите его на новой строке.

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

Пример ввода

 1 -> Number of games
10 -> sum should not exceed 10 
4 2 4 6 1  -> Stack A
2 1 8 5 -> Stack B
  

Пример вывода

 4
  

Мой код :

 static int twoStacks(int x, int[] a, int[] b) {
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        for(int i=a.length-1; i>=0; i--)
            s1.push(a[i]);

        for(int i=b.length-1; i>=0; i--)
            s2.push(b[i]);    

        return moves(x, s1, s2, 0);
    }
    static int moves(int x, Stack<Integer> a, Stack<Integer> b, int moves){
        
        if(x == 0 ) return moves-1;
        if(x < 0 ) return moves-1;

        int moves1 = a.isEmpty() ? moves : moves(x-a.pop(), a, b, moves 1);
        int moves2 = b.isEmpty() ? moves : moves(x-b.pop(), a, b, moves 1);

        return Math.max(moves1, moves2);

    }
  

Пожалуйста, не могли бы вы помочь мне, выяснив, что не так и каков был бы правильный рекурсивный подход. Многие люди решили это методом цикла, но я хочу решить это рекурсивно. Подход прост, мы должны сначала пройти по стеку один, пока не будет достигнута требуемая сумма, затем мы начинаем приближаться ко второму стеку. Всякий раз, когда сумма больше требуемой единицы, мы удаляем последнее число из стека 1.

Вы используете реальный стек и выталкиваете (изменяете) элементы, но вы выполняете алгоритм грубой силы, который полагается на то, что элементы не изменяются.

Я проиллюстрирую это на примере:

 4 2 4 1  -> Stack A
2 1 8 5 -> Stack B
  

Правильный ответ на этот вопрос таков: stackA[4 2 4 1] stackB [2 1 8 5] = 9 < 10, поэтому 4.

Вашим ответом на эту проблему будет: stackA[4 2 4 1] stackB[2 1 8 5] = 9 < 10, итак, 4.

Это тот же номер, но он совершенно неправильный. Как мы используем этот 1, когда он заблокирован за 4? Вот как это происходит:

1. stackA запускается с самого начала. и добавляется 4 = 4. ходы = 1
2. stackA извлекается из 1. и добавляется 2 = 6. ходов = 2
3. stackA извлекается из 2. и добавляется 4 = 10. 10 >= 10, поэтому moves-1. moves = 2. Обратите внимание, что 4 здесь было навсегда удалено.
4. stackB извлекается из 2. и добавляется 2 = 8. ходов = 3
5. stackA извлекается из 4. и добавляется 1 = 9. ходов = 4 … …

Вы можете выполнить любое из следующих действий:

1. Используйте другой алгоритм, который может учитывать изменяемые данные. Возможно, это тот самый метод «цикла», на который вы ссылались (не видел его, поэтому не знаю, так ли это).
2. Используйте имитированный стек вместо реального и имитируйте «всплывающее окно». Имитируемый стек на самом деле ничего не удаляет.

Пример вашего кода, изменяемого для использования имитируемого стека:

 static int twoStacks(int x, int[] a, int[] b) {
    return moves(x, s1, 0, s2, 0, 0);
}

static int moves(int x, int[] a, int aHead, int[] b, int bHead, int moves){
    if (x <= 0) return moves - 1;

    int moves1 = (aHead < a.length) ? moves(x - a[aHead], a, aHead   1, b, bHead, moves   1) : moves;
    int moves2 = (bHead < b.length) ? moves(x - b[bHead], a, aHead, b, bHead   1, moves   1) : moves;

    return Math.max(moves1, moves2);
}