(C卷,100分)- 堆栈中的剩余数字（Java & JS & Python）

题目描述

向一个空栈中依次存入正整数，假设入栈元素 n(1<=n<=2^31-1)按顺序依次为 nx…n4、 n3、n2、 n1, 每当元素入栈时，如果 n1=n2+…+ny(y 的范围[2,x]， 1<=x<=1000)，则 n1~ny 全部元素出栈，重新入栈新元素 m(m=2*n1)。

如：依次向栈存入 6、 1、 2、 3, 当存入 6、 1、 2 时，栈底至栈顶依次为[6、 1、 2]；当存入 3时， 3=2+1， 3、 2、 1 全部出栈，重新入栈元素 6(6=2*3)，此时栈中有元素 6；

因为 6=6，所以两个 6 全部出栈，存入 12，最终栈中只剩一个元素 12。

输入描述

使用单个空格隔开的正整数的字符串，如”5 6 7 8″， 左边的数字先入栈，输入的正整数个数为 x， 1<=x<=1000。

输出描述

最终栈中存留的元素值，元素值使用空格隔开，如”8 7 6 5″， 栈顶数字在左边。 6 1 2 3

用例

题目解析

本题较为简单的解题思路是：

每当有元素num将要入栈前，都尝试num去依次减去栈顶到栈底方向的栈中元素（注意这只是遍历栈的过程，而不是弹栈过程）：

1. 如果有出现num == 0，则将遍历过栈元素全部弹栈，并压入num * 2。
2. 如果没有出现num == 0，则栈不做变动，只压栈num

但是需要注意的是，对于情况1而言，我们需要注意题目描述中的这句话：

每当元素入栈时，如果 n1=n2+…+ny(y 的范围[2,x]， 1<=x<=1000)，则 n1~ny 全部元素出栈，重新入栈新元素 m(m=2*n1)

那么压栈 num * 2 是否也算新元素入栈呢？是否需要继续检查等价栈元素呢？

我理解是需要的，即这个压栈num * 2 的过程是一个需要递归的过程。

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    System.out.println(getResult(nums));
  }

  public static String getResult(int[] nums) {
    LinkedList<Integer> stack = new LinkedList<>();
    stack.add(nums[0]);

    for (int i = 1; i < nums.length; i++) {
      push(nums[i], stack);
    }

    StringJoiner sj = new StringJoiner(" ");
    while (stack.size() > 0) {
      sj.add(stack.removeLast() + "");
    }
    return sj.toString();
  }

  public static void push(int num, LinkedList<Integer> stack) {
    int sum = num;

    for (int i = stack.size() - 1; i >= 0; i--) {
      sum -= stack.get(i);

      if (sum == 0) {
        stack.subList(i, stack.size()).clear();
        push(num * 2, stack);
        return;
      } else if (sum < 0) {
        break;
      }
    }

    stack.add(num);
  }
}

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const nums = line.split(" ").map(Number);
  console.log(getResult(nums));
});

function getResult(nums) {
  const stack = [nums[0]];

  for (let i = 1; i < nums.length; i++) {
    push(nums[i], stack);
  }

  return stack.reverse().join(" ");
}

function push(num, stack) {
  let sum = num;

  for (let i = stack.length - 1; i >= 0; i--) {
    sum -= stack[i];

    if (sum == 0) {
      stack.splice(i);
      push(num * 2, stack);
      return;
    } else if (sum < 0) {
      break;
    }
  }

  stack.push(num);
}

Python算法源码

# 输入获取
nums = list(map(int, input().split()))


def push(num, stack):
    total = num

    for i in range(len(stack)-1, -1, -1):
        total -= stack[i]

        if total == 0:
            del stack[i:]
            push(num * 2, stack)
            return
        elif total < 0:
            break

    stack.append(num)


# 算法入口
def getResult():
    stack = [nums[0]]

    for i in range(1, len(nums)):
        push(nums[i], stack)

    stack.reverse()

    return " ".join(map(str, stack))


# 算法调用
print(getResult())