我刚刚在 HackerRank 上尝试了一个基于堆栈的问题

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

Alexa 有两个非负整数堆栈，堆栈 A 和堆栈 B，其中索引 0 表示堆栈的顶部。 Alexa 挑战 Nick 玩以下游戏:

在每一步中，Nick 都可以从 A 栈或 B 栈的顶部移除一个整数。

Nick 保留他从两个堆栈中删除的整数的运行总和。

如果尼克在任何时候的总和大于游戏开始时给出的某个整数 X，他将被取消比赛资格。

Nick 的最终得分是他从两个堆栈中删除的整数总数。

找出 Nick 在每场比赛中可以达到的最大可能得分(即，他可以在不被取消资格的情况下删除的最大整数数)并将其打印在新行上。

对于每场比赛，在新行上打印一个整数，表示 Nick 在不被取消资格的情况下可以达到的最大可能得分。

Sample Input 0

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

Sample Output 

4

下面是我的代码，我尝试了贪婪的方法，从堆栈顶部取出最小元素并将其添加到总和中。它适用于某些测试用例，但对于下面的输入，它会失败

1
67
19 9 8 13 1 7 18 0 19 19 10 5 15 19 0 0 16 12 5 10 - Stack A
11 17 1 18 14 12 9 18 14 3 4 13 4 12 6 5 12 16 5 11 16 8 16 3 7 8 3 3 0 1 13 4 10 7 14 - Stack B

我的代码给出的是 5 但正确的解决方案是 6 连续弹出的元素是 19,9,8,11,17,1 前三个元素来自堆栈 A，然后来自堆栈 B。

**

I don't understand the algorithm It appears like DP to me can anyone help me with the approach/algorithm?

**

public class Default {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int numOfGames = Integer.parseInt(br.readLine());
        for (int i = 0; i < numOfGames; i++) {
            String[] tmp = br.readLine().split(" ");
            int numOfElementsStackOne = Integer.parseInt(tmp[0]);
            int numOfElementsStackTwo = Integer.parseInt(tmp[1]);
            int limit = Integer.parseInt(tmp[2]);
            int sum = 0;
            int popCount = 0;

            Stack<Integer> stackOne = new Stack<Integer>();
            Stack<Integer> stackTwo = new Stack<Integer>();

            String[] stOne = br.readLine().split(" ");
            String[] stTwo = br.readLine().split(" ");

            for (int k = numOfElementsStackOne - 1; k >= 0; k--) {
                stackOne.push(Integer.parseInt(stOne[k]));
            }

            for (int j = numOfElementsStackTwo - 1; j >= 0; j--) {
                stackTwo.push(Integer.parseInt(stTwo[j]));
            }

            while (sum <= limit) {
                int pk1 = 0;
                int pk2 = 0;
                if (stackOne.isEmpty()) {
                    sum = sum + stackTwo.pop();
                    popCount++;
                } else if (stackTwo.isEmpty()) {
                    sum = sum + stackOne.pop();
                    popCount++;
                } 
                else if (!stackOne.isEmpty() && !stackTwo.isEmpty()) {
                    pk1 = stackOne.peek();
                    pk2 = stackTwo.peek();

                    if (pk1 <= pk2) {
                        sum = sum + stackOne.pop();
                        popCount++;
                    } else {
                        sum = sum + stackTwo.pop();
                        popCount++;
                    }
                } else if(stackOne.isEmpty() && stackTwo.isEmpty()){
                    break;
                }
            }

            int score = (popCount>0)?(popCount-1):0;
            System.out.println(score);
        }
    }
}

最佳答案

好的，我会尝试解释一个基本上可以用 O(n) 解决这个问题的算法，你需要自己尝试编码。

我会用简单的例子来解释，你可以反射(reflect)

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

首先你需要创建 2 个数组，数组将包含所有数字的总和，直到它的堆栈索引，例如对于堆栈 A 你将有这个数组

4 6 10 16 17  //index 0 ->4

堆栈 B 也是如此

2 3 11 16

然后对于每个数组，从数组末尾开始迭代，直到达到小于或等于“不应超过的总和”的数字

现在你的当前总和是你在两个数组中达到的点的总和，应该是 10 +3 = 13 所以为了达到 10 绝对需要删除更多条目

要删除额外的条目，我们将再次移动数组上的索引，决定移动哪个数组的索引取你指向的条目(数组 1 为 10，数组 2 为 3)并按索引设置它+1 (10/3 ~ 3) , (3/2 ~1) 然后将索引移动到最高值并重新计算总和

假设我们有:

a = 1 1 1 211 2
b = 1 85

和最大总和 = 217 现在，在计算前缀和时，

a' = 1 2 3 214 216
and b' = 1 86
current sum = 86+216 > 217

所以为了决定删除哪个索引，我们比较`

216/5~43.2` and `86/2=43`, 

所以我们在a'中移动指针。但是，这并不能解决问题 - `

214+86 is still > 217!!` 

如果我们删除了 86，那就更好了!因此，我们应该始终通过删除与前一个元素差异较大的元素来继续前进!

如果两个值相等，则将索引移动到与其前一个差异较大的值上是合乎逻辑的(记住我们正在以相反的顺序移动索引)。​​

结果将是索引的总和 +2。

关于java - HackerRank 上两个堆栈博弈的正确算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44083755/