Limite los caracteres por línea sin dividir la palabra -- java campo con algorithm camp codereview Relacionados El problema

Limit characters by line without splitting word


6
vote

problema

Español

Tengo esta pregunta en una entrevista. Dada una cadena de palabras, imprima, como cada línea, a lo largo de los caracteres, si una palabra no cabe en la línea, imprima en la siguiente línea y así sucesivamente.

Esta es mi implementación:

  public static void main(String[] args) {         String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles.";         wordWrapper(s, 11);      }      public static void wordWrapper(String s, int limit) {         // Time complexity: O(n) - n size of s         // Space complexity: O(n) - n number of words in s         int charCount = 0;         int i = 0;         String[] words = s.split(" ");         while (i < words.length) {             if (charCount + words[i].length() > limit) {                 System.out.println();                 charCount = 0;             }             charCount += words[i].length();             System.out.print(words[i] + " ");             i++;         }     }   

Estoy tratando de reducir la complejidad del espacio, y solo usar los punteros en lugar de split() , esto es lo que tengo hasta ahora, estoy pensando en mantener un seguimiento del último espacio en blanco y volver Para insertar una línea antes de esa palabra cuando se alcanza el límite, si ejecuta el código, la nueva línea se inserta correctamente, pero la mitad de la palabra aún se imprimirá antes de la nueva línea. Por favor, hágamelo saber lo que me falta. También me encantaría mirar mejores enfoques. ¡Gracias!

  public static void wordWrapper1(String s, int limit) {     int i = 0;     int lastWhitespaceIdx = -1;     int lineCount = 0;     if (s.length() == 0) {         return;     }     while (i < s.length()) {         if (Character.isWhitespace(s.charAt(i))) {             lastWhitespaceIdx = i;         }         if (lineCount + 1 > limit) {             if (!Character.isWhitespace(s.charAt(i + 1))) {                 i = lastWhitespaceIdx + 1;                 System.out.println();                 lineCount = 0;                 continue;             } else {                 System.out.println();                 lineCount = 0;             }         }         lineCount += 1;         System.out.print(s.charAt(i));         i++;     } }   
Original en ingles

I got this question in an interview. Given a string of words, print it such as each line has at most limit characters, if a word does not fit on the line, print it on the next line and so on.

This is my implementation:

public static void main(String[] args) {         String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles.";         wordWrapper(s, 11);      }      public static void wordWrapper(String s, int limit) {         // Time complexity: O(n) - n size of s         // Space complexity: O(n) - n number of words in s         int charCount = 0;         int i = 0;         String[] words = s.split(" ");         while (i < words.length) {             if (charCount + words[i].length() > limit) {                 System.out.println();                 charCount = 0;             }             charCount += words[i].length();             System.out.print(words[i] + " ");             i++;         }     } 

I'm trying to reduce the space complexity, and just use pointers instead of split(), this is what I have so far, I'm thinking of keeping track of the last whitespace and going back to insert a line before that word when the limit is reached, if you run the code the new line is inserted correctly but half of the word would still print before the new line. Please let me know what I'm missing. I also would love to look at better approaches. Thank you!

public static void wordWrapper1(String s, int limit) {     int i = 0;     int lastWhitespaceIdx = -1;     int lineCount = 0;     if (s.length() == 0) {         return;     }     while (i < s.length()) {         if (Character.isWhitespace(s.charAt(i))) {             lastWhitespaceIdx = i;         }         if (lineCount + 1 > limit) {             if (!Character.isWhitespace(s.charAt(i + 1))) {                 i = lastWhitespaceIdx + 1;                 System.out.println();                 lineCount = 0;                 continue;             } else {                 System.out.println();                 lineCount = 0;             }         }         lineCount += 1;         System.out.print(s.charAt(i));         i++;     } } 
     
       
       

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 
          String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles.";   

s no es un buen nombre de variable. Mi regla es que solo se le permite usar los nombres de variables de un solo carácter cuando se trata de dimensiones (sí, que también rechazan i / j / k8 Para los bucles, también).


  public static void wordWrapper(String s, int limit) {   

El nombramiento está desactivado, esta no es una "envoltura de palabras", es una función que envuelve una cadena por palabras, por lo que más como ssh.connect(hostname = name, username = user, key_filename = key_file)0 o ssh.connect(hostname = name, username = user, key_filename = key_file)1 .


  ssh.connect(hostname = name, username = user, key_filename = key_file)2  

No estoy seguro de que sea correcto. Podría estar muy bien confundido aquí porque rara vez necesito pensar en las limitaciones de la complejidad, pero creo que está más cerca de "O (N + M), con" N "siendo la cantidad de caracteres (la división), y "M" Siendo el número de palabras (su bucle). El espacio debe ser "O (n * 2)", con "N" siendo la cantidad de caracteres en la cadena, ya que necesita mantener cada personaje dos veces en la memoria, una vez en el original, y una vez en la cadena de palabras.

Sin embargo, la mayoría de los JVM están implementando "subcadenas", lo que significa que la matriz de CodePounts solo se lleva a cabo en la memoria, y si realiza un 998877766555443313 , recibirá un nuevo 99887766655443314 con la misma matriz pero un índice de inicio / extremo diferente.


  ssh.connect(hostname = name, username = user, key_filename = key_file)5  

Este código podría simplificarse a A para cada bucle:

  ssh.connect(hostname = name, username = user, key_filename = key_file)6  

Tenga en cuenta que su implementación, y esta revisada, tiene tres problemas que deben tratarse en algún momento:

  1. Los espacios no se tienen en cuenta para la longitud de la línea máxima.
  2. Imprime un espacio adicional al final de cada línea.
  3. cómo se debe tratar una palabra que es más larga que la longitud de la línea máxima.

... y solo use los punteros en lugar de dividir (), ...

No hay tal cosa como "un puntero para cuerdas" en Java. Sin embargo, lo más probable es que signifique, para iterar sobre la cadena y realizar un seguimiento del índice, pero "puntero" es una palabra muy prejuicios, y me mantendría alejado de ella y en su lugar usaría "índice".


  ssh.connect(hostname = name, username = user, key_filename = key_file)7  

No acorte los nombres solo porque puede, hace que el código sea más difícil de leer al final del día.


  ssh.connect(hostname = name, username = user, key_filename = key_file)8  

El nombre de esta variable es incorrecto, no cuenta las líneas, cuenta caracteres en la línea actual, se debe nombrar en consecuencia.


  ssh.connect(hostname = name, username = user, key_filename = key_file)9  

No estoy seguro de por qué use un stdin, stdout, stderr = ssh.exec_command(command)0 cuando un 99887766555443321 sería perfecto para lo que está haciendo aquí.


  stdin, stdout, stderr = ssh.exec_command(command)2  

Impresión de caracteres individuales a la vez puede ser bastante inundable, depende de si la corriente admite algún tipo de búfer o no.


Puede usar stdin, stdout, stderr = ssh.exec_command(command)3 y stdin, stdout, stderr = ssh.exec_command(command)4 para iterar sobre la cadena y simplificar su lógica. Luego use stdin, stdout, stderr = ssh.exec_command(command)5 para extraer la parte de la cadena entre los espacios e imprimirlo, o imprimir ese carácter de la pieza por carácter.

 
        String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles."; 

s is not a good variable name. My rule is that you're only allowed to use single-character variable names when dealing with dimensions (yes, that also disallows i/j/k for loops, too).


public static void wordWrapper(String s, int limit) { 

The naming is off, this is not a "word wrapper" it's a function that does wrap a string by words, so more like wrap or wrapText.


        // Time complexity: O(n) - n size of s         // Space complexity: O(n) - n number of words in s 

I'm not sure that is correct. I could be very well mistaken here because I rarely need to think about complexity limitations at all, but I think it is closer to "O(n + m)", with "n" being the number of characters (the split), and "m" being the number of words (your loop). Space should be "O(n*2)", with "n" being the number of characters in the string, as you need to keep each character twice in memory, once in the original, and once in the word string.

However, most JVMs are implementing "substrings", which means that the array of codepoints is only held one in memory, and if you do a substring, you will receive a new String with the same array but different start/end index.


        int charCount = 0;         int i = 0;         String[] words = s.split(" ");         while (i < words.length) {             if (charCount + words[i].length() > limit) {                 System.out.println();                 charCount = 0;             }             charCount += words[i].length();             System.out.print(words[i] + " ");             i++;         } 

This code could be simplified to a for-each loop:

int currentLineLength = 0;  for (String word : text.split(" ")) {     if ((currentLineLength + word.length()) > maxCharactersPerLine) {         System.out.println();         currentLineLength = 0;     }          System.out.print(word + " ");     currentLineLength = currentLineLength + word.length(); } 

Note that your implementation, and this revised one, has three problems which should be dealt with at some point:

  1. The spaces are not taken into account for the maximum line length.
  2. It prints an extra space at the end of each line.
  3. How a word should be treated that is longer than the maximum line length.

...and just use pointers instead of split(),...

There is no such thing as "a pointer for strings" in Java. Though, you most likely mean, to iterate over the String and keep track of the index, but "pointer" is a heavily prejudiced word, and I would stay clear of it and instead use "index".


int lastWhitespaceIdx = -1; 

Don't shorten names just because you can, it does make the code harder to read in the end of the day.


int lineCount = 0; 

The name of this variable is incorrect, it does not count lines, it counts characters on the current line, it should be named accordingly.


while (i < s.length()) { 

Not sure why you use a while when a for would be perfect for what you're doing here.


System.out.print(s.charAt(i)); 

Printing single characters at a time can be quite wasteful, depends on whether the stream supports some sort of buffer or not.


You could use String.indexOf(String) and String.index(String, int) to iterate over the string and simplify your logic. Then use substring to extract the part of the String between the spaces and print that, or print that part character by character.

 
 
 
 

Relacionados problema

5  Orden de número más grande en cadena  ( Largest number order in string ) 
Dada una cadena, suponiendo que la cadena sea solo números, reorganice la cadena a la que sea el mayor número posible. a continuación es mi solución al pr...

35  Demasiados bucles en la aplicación de dibujo  ( Too many loops in drawing app ) 
Tengo un método que tiene muchos bucles: #ifndef __RUNES_STRUCTURES_H #define __RUNES_STRUCTURES_H /* Runes structures. */ struct Game { char board[2...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

25  Algoritmo para transformar una palabra a otra a través de palabras válidas  ( Algorithm to transform one word to another through valid words ) 
He estado practicando retroceso y quería saber cómo puedo mejorar mi código. Por ejemplo, no quiero usarlo global. Además, no estoy seguro de si mi código fun...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...




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