计算堆栈中的剩余数字
标题：计算堆栈中的剩余数字 | 时间限制：1秒 | 内存限制：32768K | 语言限制：不限
向一个空栈中依次存入正整数， 假设入栈元素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。
import java.util.Scanner;
import java.util.Stack;
public class Main {
static Stack<Long> stack = new Stack<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
String[] strNumbers = line.split(" ");
int[] numbers = new int[strNumbers.length];
for (int i = 0; i < strNumbers.length; i++) {
numbers[i] = Integer.parseInt(strNumbers[i]);
}
for (int i = 0; i < numbers.length; i++) {
tryToPush(numbers[i]);
}
StringBuilder result = new StringBuilder();
while (!stack.empty())
result.append(stack.pop()).append(" ");
System.out.println(result.toString().trim());
}
static void tryToPush(long num) {
long temp = 0;
for (int i1 = stack.size() - 1; i1 >= 0; i1--) {
temp += stack.get(i1);
if (temp == num) {
int stackSize = stack.size();
for (int j = i1; j < stackSize; j++) {
stack.pop();
}
tryToPush(temp * 2);
return;
} else if (temp > num) {
break;
}
}
stack.push(num);
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp2
{
public class Program
{
public static long MyPow(long x, long y)
{
long output = 1;
if (y == 0) return 1;
for (long i = 1; i <= y; i++)
{
output *= x;
}
return output;
}
public static bool ShouldPop(IEnumerable<long> numbers, long num, out int popAt)
{
if (numbers == null || numbers.Count() <= 0)
{
popAt = -1;
return false;
}
long sum = 0;
for (int i = 0; i <= numbers.Count() - 1; i++)
{
long currNumber = numbers.ElementAt(i);
sum += currNumber;
if (sum < num)
{
continue;
}
if (sum > num)
{
popAt = -1;
return false;
}
if (sum == num)
{
popAt = i;
return true;
}
}
popAt = -1;
return false;
}
public static void Main(string[] args)
{
string input = Console.ReadLine();
string[] numbers = input.Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
if (numbers.Length > 1000 || numbers.Length < 1)
{
Console.WriteLine();
return;
}
Stack<long> intStack = new Stack<long>();
for (int i = 0; i <= numbers.Length - 1; i++)
{
if (!long.TryParse(numbers[i], out long currNumer))
{
Console.WriteLine();
return;
}
else
{
if (currNumer < 1 || currNumer > MyPow(2, 31) - 1)
{
Console.WriteLine();
return;
}
int popAt = -1;
while (ShouldPop(intStack, currNumer, out popAt))
{
for (int j = 0; j <= popAt; j++)
{
intStack.Pop();
}
currNumer = currNumer * 2;
}
//题干中规定入栈元素属于[1,2^31-1], 此处若考虑m是否符合该条件则有测试用例无法通过
//if (currNumer > int.MaxValue)
//{
// Console.WriteLine();
// return;
//}
intStack.Push(currNumer);
}
}
string output = string.Empty;
while (intStack.Count() > 0)
{
output += intStack.Pop() + " ";
}
Console.WriteLine(output.Trim());
}
}
}
查看11道真题和解析
