Pregunta de entrevista: ¿Encontrar caracteres Siguiente y Anterior en una cadena dada?

Question

Tenemos un lenguaje X, que tiene un byte y dos caracteres de byte. Este lenguaje tiene las siguientes características.

1. valor de caracteres de un solo byte será siempre menor o igual a 127.
2. En dos caracteres de bytes, Primer byte será siempre mayor que 127 bytes y el segundo valor puede ser cualquier cosa.

El problema es que tenemos una cadena de longitud arbitraria y un puntero apuntando a un byte en la cadena y tenemos que averiguar cuál es el carácter anterior y cuál es el siguiente carácter.

Un enfoque simple se iniciará desde el comienzo de la cadena, verificando el valor del byte y comparando los punteros hasta que lleguemos al puntero dado. Pero en el peor de los casos, si el puntero dado apunta al último byte en la cadena dada, tenemos que recorrer todos los charaters.

Me gustaría saber si hay algún algoritmo mejor que dé el resultado en tiempo constante independientemente de la longitud de la cadena?

Answer 1

Parece que en el peor de los casos, tenemos que pasar por toda la cadena. Sólo considere caracteres A = 100 y B = 200, C = 201 y las siguientes cadenas de longitud N:

S1 = abcbcbc ... BC

S2 = BBCBCBC ... BC

Answer 2

suponiendo que saber cómo moverse hacia atrás en la cuerda (y suponiendo que el puntero que te dan está garantizado que está en el primer byte del personaje actual si es de varios bytes). Solo retroceda dos bytes.

Si los datos en la corriente -2> 127, entonces el carácter anterior son los dos últimos bytes. si los datos en la corriente -2 es < 127, entonces el carácter anterior está en la corriente -1.

Similar para el siguiente personaje. Si los datos en el +1 actual es < 127, entonces es el siguiente carácter, de lo contrario es el comienzo de un carácter de múltiples bytes.

Si no puede retroceder, no hay forma de hacerlo sin leer todo el hilo hasta llegar a la posición actual. Use una pila para hacer un seguimiento de los dos últimos bytes, cuando golpea la dirección actual, todos los datos que necesita para el personaje anterior se encuentran en la pila.

Answer 3

Escanee hacia atrás hasta que golpee dos bytes consecutivos por debajo de 127 o hasta que toque el principio de la cadena. Ahora puede contar los caracteres hasta el lugar en el que se encuentra y hasta uno después del personaje actual.

Answer 4

Anterior: Copia de seguridad de 2 bytes. Si el byte es> 127, entonces es el comienzo del carácter, de lo contrario, el carácter anterior comienza en el siguiente carácter.

Siguiente: Si el byte actual es> 127, el siguiente carácter comienza en 2 bytes, de lo contrario, el siguiente carácter comienza en 1 byte.

Answer 5

No, el tiempo constante es imposible ya que el peor de los casos es, como dice Olexiy, que casi toda la cadena tiene bytes de primer bit y debe retroceder hasta el principio para averiguar cuál es el primer -bit-set byte en la primera secuencia de dos bytes.

Esperemos que este caso patológico es rara y sólo se puede retroceder un byte a la vez hasta que se encuentra con cualquier byte bajo, en cuyo caso puede estar seguro de que el byte después es el inicio de un personaje. Luego puede caminar hacia delante nuevamente hasta que encuentre su puntero original.

Answer 6

Realmente necesita encontrar tres caracteres: el carácter actual, el carácter anterior y el siguiente carácter.

CurrentChar está en la posición P dada por el puntero o en P-1. Si la posición P apunta a un byte que es mayor que 127, P es el CurrentChar. Si P es menor que 127, mire P-1. Si P-1 es mayor que 127 entonces CurrentChar es P-1, de lo contrario CurrentChar está en la posición P.

Para obtener el PreviousChar, mira CurrentChar - 2 y si es mayor que 127 PreviousChar = CurrentChar -2 de lo contrario PreviousChar = CurrentChar -1

El NextChar puede obtenerse mirando P. Si P es mayor que 127, el siguiente carácter está en P + 2. Si P es menor que 127, NextChar está en la posición P + 1.

Answer 7

Veamos ... Ya está señalando un carácter que puede ser un byte simple o doble byte. En este último caso, podrías estar en el primer o segundo byte de este personaje. Entonces primero debes saber si estás al principio de un personaje o no. Para empeorar las cosas, el segundo byte de un carácter de dos bytes puede tener cualquier valor, ¡así que existe la posibilidad de que todos los bytes sean mayores que 127! Eso hace que sea desagradable encontrar el personaje anterior. Pero primero, determine si está al comienzo de un nuevo personaje o en medio de uno.

• Determinación del inicio del carácter: retroceda un byte hasta encontrar un byte que no tenga el bit más alto establecido. (O al comienzo de la cadena.) En función del número de bytes con el bit más alto establecido, sabrá si está al principio o no. Una cantidad impar de bits altos configurados antes del byte actual significa que debe retroceder un byte para el carácter actual.

• Determinar el carácter anterior: Retroceder dos bytes. Si se establece el bit más alto, lo encontraste. Si no, ve un byte hacia adelante.

• Determinación del siguiente carácter: compruebe el bit más alto del byte actual. Si está configurado, avance dos bytes hacia adelante. De lo contrario, solo uno.

• Determinar el número de caracteres significa que va al inicio de la cadena y comprueba el bit más alto de cada byte. Si está configurado, agregue uno a su cuenta y omita un byte. Si no está configurado, simplemente agregue uno a su cuenta. Desafortunadamente, tendrás que pasar por toda la cadena.

Supongo que tiene alguna forma de indicar el inicio y el final de la cadena. Si no, no hay indicación de dónde comienza y se detiene. (A menos que use un byte nulo para indicar inicio/detención, en cuyo caso no puede omitir los bytes porque puede omitir dicho byte nulo.)

¿Hay una manera más rápida? Bueno, si conoce las ubicaciones de inicio/final, entonces puede calcular la cantidad de bytes en esta cadena. El número de caracteres sería el número de bytes en esta cadena con sus bits más altos no establecidos. ¡Entonces solo cubra el número de bytes más bajo que 128!

Answer 8

Suponiendo que arr [] es como una cadena y un puntero a un byte es puntero a ÍNDICE

#include<stdio.h> 
#include<stdlib.h> 
int find_valid(int); 
int arr[]={128,12,128,19,128,127,128,12,32,145,12,223,54,76,23}; 
int main(){ 
    int index=1; 
    while(index != 0){ 
    printf("\nEnter the index:"); 
    scanf("%d",&index); 
    if(arr[index] < 128){ // it can be the first byte or the second byte of the Two byte 
      if(arr[index -1] < 128) printf("\nThis is the first byte in itself"); 
      else // index-1 >= 128 
       { 
        int count = find_valid(index-2); 
        if(count%2 == 0) printf("\n This is the second byte of the two bytes:");  
        else printf("\nThis is the first byte in itself:"); 
       } 
      } 
    else{ // it can be the second or the first in the two bytes 
      if (arr[index - 1] < 128) printf("\n This is the First byte of the two bytes:"); 
      else{ 
       int count = find_valid(index-2); 
       if(count%2 == 0) printf("\n This is the second byte of the two bytes:"); 
       else printf("\nThis is the First byte of the two bytes:"); 
       } 
      }   

    printf("\nHave u seen the result:"); 
    scanf("%d",&index);} 
} 

int find_valid(int i){ 
    int count=0; 
    while((arr[i] > 127) && (i>0)) { ++count; --i;} 
     return count;  
}