Implementar la clase de pila desde cero para un desafío H-Rango -- java campo con linked-list campo con time-limit-exceeded campo con stack camp codereview Relacionados El problema

Implement stack class from scratch for a h-rank challenge


-2
vote

problema

Español

Escriba una clase de pila desde cero a los enteros de la casa utilizando cualquier idioma de programación de su elección que implementa los siguientes métodos:

  push(integer n) // adds the integer to top of the stack pop()           // removes the top-most item from the stack peek()          // gets the integer from top of the stack without removing it depth()         // determines the number of integers in the stack   

Use esta clase de pila en un programa que se lee en una línea de fichas, la procesa, y emite los resultados.

No utilice clases de pila preexistentes proporcionadas por un idioma, biblioteca, paquete o marco en particular. Su solución debe contener su propia implementación de una clase de pila utilizando las mejores prácticas de programación orientadas a objetos.

Formato de entrada

Una sola línea de texto que contiene tokens separados por espacios. Un token puede ser cualquier número entero, el carácter menos ( - ), el carácter del signo de interrogación ( 99887776655443332 ), o el carácter hash ( 99887776655443333 ) , separados por espacios. Cada token tiene el siguiente significado:

  • Si un número, entonces el número se empuja a la pila
  • Si el carácter menos ( - ), se realiza una operación 99887776655544335 contra la pila
  • Si el carácter del signo de interrogación ( ?6), se realiza una operación 9988776655544337
  • Si el carácter hash ( 99887776655443388 ), se realiza una operación 9988776655544339

Restricciones

    Las entradas
  • no harán que la pila se inclusive
  • La pila debe soportar la profundidad -0 , donde 99887766555443311 Sin desbordarse
  • -2
  • El uso de una clase de pila preexistente proporcionada por el lenguaje de programación, la biblioteca, el paquete o el marco no es aceptable

Formato de salida

Habrá una línea de salida para cada token en la entrada, según lo siguiente:

  • Para un token entero, salga de la profundidad de la pila después de la operación de empuje
  • para un carácter menos ( -3 ), salga del entero saliendo de la pila
  • Para un carácter de signo de interrogación ( -4 ), salida El elemento se asoma de la pila
  • para un personaje de hash ( -5 ), salida la profundidad de la pila

Entrada de muestra

  -6  

Salida de muestra

  -7  

Explicación

  • Antes de que se empuje cualquier entero en la pila, la pila está vacía y, por lo tanto, tiene elementos cero. Según la especificación del formato de entrada, y se debe imprimir "0".
  • Cuando se encuentra el token 34, se empuja hacia la pila, ya que es un entero. Ahora la pila tiene un elemento, y se debe imprimir "1".
  • cuando se encuentra el token 25, también se empuja a la pila. La pila ahora tiene dos elementos, y se debe imprimir "2".
  • Cuando se encuentra el token -8 , se asoma a la pila, y se imprime "25", ya que ese es el elemento más alto en la pila.
  • Cuando se encuentra el token -5, se empuja a la pila y se imprime "3".
  • cuando se encuentra el token -9 , el elemento más alto se incluye de la pila, y "-5" se imprime
  • Cuando se encuentra el token ?0 se imprime porque la pila ahora tiene dos elementos.
  • cuando se encuentra el token ?1 se imprime porque está en la parte superior de la pila.

Así es como lo implementé:

  ?2  

Esto pasa cada prueba, excepto por uno donde salga. Había intentado resolverlo sin regex (usado:

  ?3  

...... pero aún así falló el caso de prueba del tiempo de espera.

Original en ingles

Write a stack class from scratch to house integers using any programming language of your choosing that implements the following methods:

push(integer n) // adds the integer to top of the stack pop()           // removes the top-most item from the stack peek()          // gets the integer from top of the stack without removing it depth()         // determines the number of integers in the stack 

Use this stack class in a program that reads in a line of tokens, processes it, and outputs the results.

Do NOT use a pre-existing stack classes provided by a particular language, library, package, or framework. Your solution must contain your own implementation of a Stack class using best object-oriented programming practices.

Input Format

A single line of text containing tokens separated by spaces. A token can be any integer, the minus character (-), the question mark character (?), or the hash character (#), separated by spaces. Each token has the following meaning:

  • If a number, then the number is pushed onto the stack
  • If the minus character (-), a pop operation is performed against the stack
  • If the question mark character (?), a peek operation is performed
  • If the hash character (#), a depth operation is performed

Constraints

  • Inputs will not cause the stack to underflow
  • The stack must support depth d, where d < 2,000,000 without overflowing
  • -1048576000000 < n < 1048576000000
  • Using a pre-existing stack class provided by the programming language, library, package, or framework is not acceptable

Output Format

There shall be one line of output for each token in the input, per the following:

  • For an integer token, output the depth of the stack after the push operation
  • For a minus character (-), output the integer popped from the stack
  • For a question mark character (?), output the element peeked from the stack
  • For a hash character (#), output the depth of the stack

Sample Input

34 25 ? -5 - # ? 

Sample Output

0 1 2 25 3 -5 2 25 

Explanation

  • Before any integer is pushed onto the stack, the stack is empty, and therefore has zero elements. Per the input format specification, and "0" should be printed.
  • When token 34 is encountered, it is pushed onto the stack since it is an integer. Now stack has one element, and "1" should be printed.
  • When token 25 is encountered, it is pushed onto the stack as well. Stack now has two elements, and "2" should be printed.
  • When token ? is encountered, it peeks at the stack, and prints "25" since that is the top-most element in the stack.
  • When token -5 is encountered, it is pushed onto the stack and "3" is printed.
  • When token - is encountered, the top-most element is popped from the stack, and "-5" is printed
  • When token # is encountered, "2" is printed because the stack now has two elements.
  • When token ? is encountered, "25" is printed because it is at the top of the stack.

This is how I implemented it:

import java.io.*; import java.util.*; import java.lang.*;  public class StackThemUp {   private static LinkedList<Long> list = new LinkedList<>();     @SuppressWarnings("resource")   public static void main(String[] args) {      int stackSize;     long lastInt;     String line = "";     try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {          line = reader.readLine(); } catch (IOException exc) { } for (String s : line.split(" ")) {   try {     if (s.equals("?")) {         lastInt = peek();         System.out.println(lastInt);     } else if (s.equals("#")) {         if(list.size()>0){          stackSize = depth();         System.out.println(stackSize);         }     } else if (s.equals("-")) {        if(list.size()>0){        lastInt = peek();        System.out.println(lastInt);        pop();        }     } else if (s.matches("[-]?\\d+")) {         push(Long.parseLong(s));         stackSize = depth();         System.out.println(stackSize);     } else {       throw new IllegalArgumentException();     }   } catch (IllegalArgumentException ex) {     }  } }   private static void push(Long number) {   list.add(number);   }    private static Long peek() {   return list.getLast();   }    private static int depth() {   return list.size();   }    private static void pop() {   if (list.size() > 0)   list.removeLast();   } } 

This passes every test except for one where it times out. I had tried to solve it without regex (used :

private static boolean validateInteger(String text) {   try {     Long.parseLong(text);     return true;   } catch (NumberFormatException ex) {     return false;   } } 

......but still it failed the timed-out test case.

           
       
       

Lista de respuestas

1
 
vote
  if cond is None:4  

A if cond is None:5 Implementa una interfaz if cond is None:6 , que admite 99887776655443317 Operaciones. Puede fallar el requisito de "desde cero". Si estuviera haciendo esto, probablemente usaría una matriz.

  if cond is None:8  

Dado que está garantizado una profundidad máxima de 2,000,000, puede seguir adelante y asignar esa mucha memoria de inmediato. Prácticamente está garantizado para necesitar mucho memoria para al menos un caso de prueba.

  if cond is None:9  

con una matriz

  if cond == None:0  

Como no sabemos por qué su código fue programado, no sabemos si esto lo arreglará. Que podría. Una lista vinculada es una estructura de datos deficientes para hacer muchas inserciones, ya que tiene que seguir asignando la memoria. Este código asigna la memoria solo una vez.

Tenga en cuenta que no prometen no desbordar la pila, solo para no lo inflar. Tal vez el tiempo de espera es que le esperen que rechacen un desbordamiento de pila. Ausente más detalle, es solo la especulación.

  if cond == None:1  

Dos cosas. Primero, usaría un if cond == None:2 .

  if cond == None:3  

Segundo, no arrojaría una excepción dentro de un if cond == None:4

También puede dejar el registro de 99887766655443325

, ya que prometen nunca hacerlo. No lo comprobará en if cond == None:6 , que tiene el mismo problema.

Podría if cond == None:7 Simplemente el if cond == None:8 En lugar de el más general if cond == None:9 , pero dudo que importa.

 
  private static LinkedList<Long> list = new LinkedList<>(); 

A LinkedList implements a Deque interface, which supports Stack operations. It may fail the "from scratch" requirement. If I were doing this, I would likely use an array.

  private static long[] stack = new long[2000000];   int size = 0; 

Since you're guaranteed a maximum depth of 2,000,000, you can go ahead and allocate that much memory immediately. You're virtually guaranteed to need that much memory for at least one test case.

  private static void push(Long number) {   list.add(number);   }    private static Long peek() {   return list.getLast();   }    private static int depth() {   return list.size();   }    private static void pop() {   if (list.size() > 0)   list.removeLast();   } 

With an array

  private static void push(long number) {     stack[size] = number;     size++;   }    private static long peek() {     return stack[size - 1];   }    private static int depth() {     return size;   }    private static void pop() {     if (size > 0) {       size--;     }   } 

As we don't know why your code was timing out, we don't know if this will fix it. It might. A linked list is a poor data structure for doing lots of inserts, as it has to keep allocating memory. This code allocates memory just once.

Note that they don't promise not to overflow the stack, just not to underflow it. Maybe the timeout is that they are waiting for you to reject a stack overflow. Absent more detail, it's all just speculation.

  try {     if (s.equals("?")) {         lastInt = peek();         System.out.println(lastInt);     } else if (s.equals("#")) {         if(list.size()>0){          stackSize = depth();         System.out.println(stackSize);         }     } else if (s.equals("-")) {        if(list.size()>0){        lastInt = peek();        System.out.println(lastInt);        pop();        }     } else if (s.matches("[-]?\\d+")) {         push(Long.parseLong(s));         stackSize = depth();         System.out.println(stackSize);     } else {       throw new IllegalArgumentException();     }   } catch (IllegalArgumentException ex) {     }  } 

Two things. First, I'd use a switch.

if (str.length() == 1) {   switch (s.charAt(0)) {     case '?':       System.out.println(peek());       break;     case '#':       System.out.println(depth());       break;     case '-':       if (size > 0) {         System.out.println(peek());         pop();       }       break;     default:       push(Long.parseLong(s));       System.out.println(depth());   } } else {   push(Long.parseLong(s));   System.out.println(depth()); } 

Second, I wouldn't throw an exception inside a try to be caught without effect. Just skip it.

You also might leave off the size > 0 check, since they promise to never do that. You don't check it on peek, which has the same problem.

You could catch just the NumberFormatException rather than the more general IllegalArgumentException, but I doubt it matters.

 
 
       
       

Relacionados problema

3  Cadena de cambio circular  ( Circular shift string ) 
Entonces, básicamente estoy trabajando en un algoritmo para cambiar circular una cadena hasta una posición. Hay dos parámetros requeridos aquí. cadena de t...

4  ADT Pila con Linkedlist  ( Adt stack with linkedlist ) 
Actualmente estoy preparando para mi examen y estoy tratando de implementar algunos tipos de datos abstractos con listas vinculadas como preparación para el e...

4  Linkedlist para ser utilizado en una pila o cola  ( Linkedlist to be used in a stack or queue ) 
Todo esto funciona. Solo quería asegurarse de que no me perdí nada. Viniendo de C ++ y trabajando en mi camino a través de algoritmos, 4ta ed. Aquí está mi cl...

7  Implementación de la pila con una lista vinculada  ( Stack implementation with a linked list ) 
¿Podría alguien proporcionar alguna crítica constructiva? Estoy tratando de obtener un salto en las estructuras de datos antes de que comiencen las clases. ...

5  Plantilla de pila usando la lista vinculada  ( Stack template using linked list ) 
Estoy trabajando en una implementación de pila usando una lista vinculada, pero tengo una fuerte sensación de haber superado mi solución. Le agradecería si re...

8  Implementación de STL STACK  ( Stl stack implementation ) 
I implementé std::stack desde el STL para una comprensión más profunda del idioma y la memoria, ya que sigo siendo solo un principiante. Implementé la pila ...

2  ADT STACK con una lista enlazada doblemente circular  ( Adt stack with a doubly circular linked list ) 
He logrado implementar un yes1 con una lista circularmente vinculada. Me gustaría saber si hay cosas que podría haber hecho mejor o, debería mejorar. yes...

1  Clase de pila en C ++  ( Stack class in c ) 
Por favor revise esto: #include <iostream> #include <vector> #include <cassert> using namespace std; template <class T> class Stack { public: Stack() {}...

6  Implementación de una pila en C  ( Implementation of a stack in c ) 
A continuación se muestra mi implementación de una pila en C . ¿Es correcto? ¿Y / o hay algo que debo arreglar para mejorarlo de alguna manera? stack.h ...

2  Implementación de pila usando vectores y plantillas sin desbordamiento versión 1.3  ( Stack implementation using vectors and templates with no overflow version 1 3 ) 
A continuación se muestra el código para la pila junto con una o dos opciones adicionales. Por favor, avíseme si hay alguna inquietud / problemas críticos. A ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos