algorithm - strings - leer cadena de caracteres en c

Revertir de manera eficiente el orden de las palabras(no los caracteres) en una matriz de caracteres

Question

Dado un conjunto de caracteres que forman una oración de palabras, proporcione un algoritmo eficiente para invertir el orden de las palabras (no los caracteres) en él.

Ejemplo de entrada y salida:

>>> reverse_words("this is a string")
''string a is this''

Debería ser el tiempo O (N) y el espacio O (1) ( split() y empujar / estallar fuera de la pila no están permitidos).

El rompecabezas está tomado de aquí .

Answer 1

Un trazador de líneas uno:

l="Is this as expected ??"
" ".join(each[::-1] for each in l[::-1].split())

Salida:

''?? expected as this Is''

Answer 2

Aquí está mi respuesta. No hay llamadas a la biblioteca ni estructuras de datos temporales.

#include <stdio.h>

void reverse(char* string, int length){
    int i;
    for (i = 0; i < length/2; i++){
        string[length - 1 - i] ^= string[i] ;
        string[i] ^= string[length - 1 - i];
        string[length - 1 - i] ^= string[i];
    }   
}

int main () {
char string[] = "This is a test string";
char *ptr;
int i = 0;
int word = 0;
ptr = (char *)&string;
printf("%s/n", string);
int length=0;
while (*ptr++){
    ++length;
}
reverse(string, length);
printf("%s/n", string);

for (i=0;i<length;i++){
    if(string[i] == '' ''){
       reverse(&string[word], i-word);
       word = i+1;
       }
}   
reverse(&string[word], i-word); //for last word             
printf("/n%s/n", string);
return 0;
}

Answer 3

En C: (C99)

#include <stdio.h>
#include <string.h>

void reverseString(char* string, int length)
{
    char swap;
    for (int i = 0; i < length/2; i++)
    {
        swap = string[length - 1 - i];
        string[length - 1 - i] = string[i];
        string[i] = swap;
    }   
}

int main (int argc, const char * argv[]) {
    char teststring[] = "Given an array of characters which form a sentence of words, give an efficient algorithm to reverse the order of the words (not characters) in it.";
    printf("%s/n", teststring);
    int length = strlen(teststring);
    reverseString(teststring, length);
    int i = 0;
    while (i < length)
    {
        int wordlength = strspn(teststring + i, "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
        reverseString(teststring + i, wordlength);
        i += wordlength + 1;
    }
    printf("%s/n", teststring);
    return 0;
}

Esto da salida:

Dado un conjunto de caracteres que forman una oración de palabras, proporcione un algoritmo eficiente para invertir el orden de las palabras (no los caracteres) en él.

.it in) caracteres no (palabras del orden inverso al algoritmo eficiente y un give, palabras de la oración a form which characters of array an Given

Esto toma como mucho 4N veces, con un pequeño espacio constante. Desafortunadamente, no maneja la puntuación o el caso con gracia.

Answer 4

O (N) en el espacio y O (N) en solución de tiempo en Python:

def reverse_words_nosplit(str_):
  """
  >>> f = reverse_words_nosplit
  >>> f("this is a string")
  ''string a is this''
  """
  iend = len(str_)
  s = ""
  while True:
    ispace = str_.rfind(" ", 0, iend)
    if ispace == -1:
      s += str_[:iend]
      break
    s += str_[ispace+1:iend]
    s += " "
    iend = ispace
  return s

Answer 5

Una solución de C ++:

#include <string>
#include <iostream>
using namespace std;

string revwords(string in) {
    string rev;
    int wordlen = 0;
    for (int i = in.length(); i >= 0; --i) {
        if (i == 0 || iswspace(in[i-1])) {
            if (wordlen) {
                for (int j = i; wordlen--; )
                    rev.push_back(in[j++]);
                wordlen = 0;
            }
            if (i > 0)
                rev.push_back(in[i-1]);
        }
        else
            ++wordlen;
    }
    return rev;
}

int main() {
    cout << revwords("this is a sentence") << "." << endl;
    cout << revwords("  a sentence   with extra    spaces   ") << "." << endl;
    return 0;
}

Answer 6

Una solución de Ruby.

# Reverse all words in string
def reverse_words(string)
  return string if string == ''''

  reverse(string, 0, string.size - 1)

  bounds = next_word_bounds(string, 0)

  while bounds.all? { |b| b < string.size }
    reverse(string, bounds[:from], bounds[:to])
    bounds = next_word_bounds(string, bounds[:to] + 1)
  end

  string
end

# Reverse a single word between indices "from" and "to" in "string"
def reverse(s, from, to)
    half = (from - to) / 2 + 1

    half.times do |i|
        s[from], s[to] = s[to], s[from]
        from, to = from.next, to.next
    end

    s
end

# Find the boundaries of the next word starting at index "from"
def next_word_bounds(s, from)
  from = s.index(//S/, from) || s.size
  to = s.index(//s/, from + 1) || s.size

  return { from: from, to: to - 1 }
end

Answer 7

Una solución en C / C ++:

void swap(char* str, int i, int j){
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length){
    for(int i=0; i<length/2; i++){
        swap(str, i, length-i-1);
    }
}
void reverse_words(char* str){
    int l = strlen(str);
    //Reverse string
    reverse_string(str,strlen(str));
    int p=0;
    //Find word boundaries and reverse word by word
    for(int i=0; i<l; i++){
        if(str[i] == '' ''){
            reverse_string(&str[p], i-p);
            p=i+1;
        }
    }
    //Finally reverse the last word.
    reverse_string(&str[p], l-p);
}

Esto debería ser O (n) en el tiempo y O (1) en el espacio.

Editar: lo limpié un poco.

El primer paso sobre la cadena es obviamente O (n / 2) = O (n). El segundo pase es O (n + longitud combinada de todas las palabras / 2) = O (n + n / 2) = O (n), lo que lo convierte en un algoritmo O (n).

Answer 8

Utilizaría lo que se conoce como una función recursiva iterativa, que es O (N) en el tiempo, ya que requiere N (N es el número de palabras) iteraciones para completar y O (1) en el espacio ya que cada iteración mantiene su propio estado dentro los argumentos de la función.

(define (reverse sentence-to-reverse)
  (reverse-iter (sentence-to-reverse ""))

(define (reverse-iter(sentence, reverse-sentence)
  (if (= 0 string-length sentence)
    reverse-sentence
    ( reverse-iter( remove-first-word(sentence), add-first-word(sentence, reverse-sentence)))

Nota: He escrito esto en el esquema que soy un novato completo, así que me disculpo por la falta de manipulación correcta de la secuencia.

remove-first-word encuentra la primera palabra límite de la oración, luego toma esa sección de caracteres (incluyendo espacio y puntuación) y la elimina y devuelve una nueva oración

add-first-word encuentra la primera palabra límite de la oración, luego toma esa sección de caracteres (incluyendo espacio y puntuación) y la agrega a la oración inversa y devuelve nuevos contenidos de oraciones inversas.

Answer 9

en C #, in situ, O (n), y probado:

static char[] ReverseAllWords(char[] in_text)
{
    int lindex = 0;
    int rindex = in_text.Length - 1;
    if (rindex > 1)
    {
        //reverse complete phrase
        in_text = ReverseString(in_text, 0, rindex);

        //reverse each word in resultant reversed phrase
        for (rindex = 0; rindex <= in_text.Length; rindex++)
        {
            if (rindex == in_text.Length || in_text[rindex] == '' '')
            {
                in_text = ReverseString(in_text, lindex, rindex - 1);
                lindex = rindex + 1;
            }
        }
    }
    return in_text;
}

static char[] ReverseString(char[] intext, int lindex, int rindex)
{
    char tempc;
    while (lindex < rindex)
    {
        tempc = intext[lindex];
        intext[lindex++] = intext[rindex];
        intext[rindex--] = tempc;
    }
    return intext;
}

Answer 10

#include <string>
#include <boost/next_prior.hpp>

void reverse(std::string& foo) {
    using namespace std;
    std::reverse(foo.begin(), foo.end());
    string::iterator begin = foo.begin();
    while (1) {
        string::iterator space = find(begin, foo.end(), '' '');
        std::reverse(begin, space);
        begin = boost::next(space);
        if (space == foo.end())
            break;
    }
}

Answer 11

En pseudo código:

reverse input string
reverse each word (you will need to find word boundaries)

Answer 12

Presione cada palabra en una pila. Pop todas las palabras de la pila.

Answer 13

empujar una cuerda en una pila y luego soltarla, ¿sigue siendo O (1)? esencialmente, eso es lo mismo que usar split () ...

¿O (1) no significa en el lugar? Esta tarea es más fácil si solo podemos agregar cadenas y otras cosas, pero eso usa espacio ...

EDITAR : Thomas Watnedal tiene razón. El siguiente algoritmo es O (n) en el tiempo y O (1) en el espacio:

1. cadena inversa en el lugar (primera iteración sobre la cadena)
2. revertir cada palabra (invertida) in situ (otras dos iteraciones sobre la cadena)
   1. encontrar el límite de la primera palabra
   2. revertir dentro de este límite de palabra
   3. repita para la próxima palabra hasta que termine

Creo que deberíamos probar que el paso 2 es realmente solo O (2n) ...

Answer 14

using System;

namespace q47407
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string s = Console.ReadLine();
            string[] r = s.Split('' '');
            for(int i = r.Length-1 ; i >= 0; i--)
                Console.Write(r[i] + " ");
            Console.WriteLine();

        }
    }
}

editar: supongo que debería leer toda la pregunta ... continuar.

Answer 15

@Daren Thomas

Implementación de su algoritmo (O (N) en el tiempo, O (1) en el espacio) en D (Marte digital):

#!/usr/bin/dmd -run
/**
 * to compile & run:
 * $ dmd -run reverse_words.d
 * to optimize:
 * $ dmd -O -inline -release reverse_words.d
 */
import std.algorithm: reverse;
import std.stdio: writeln;
import std.string: find;

void reverse_words(char[] str) {
  // reverse whole string
  reverse(str);

  // reverse each word
  for (auto i = 0; (i = find(str, " ")) != -1; str = str[i + 1..length])
    reverse(str[0..i]);

  // reverse last word
  reverse(str);
}

void main() {
  char[] str = cast(char[])("this is a string");
  writeln(str);
  reverse_words(str);
  writeln(str);
}

Salida:

this is a string string a is this

Answer 16

en Ruby

"esto es una cadena" .split.reverse.join ("")

Answer 17

Eficiente en términos de mi tiempo: me llevó menos de 2 minutos escribir en REBOL:

reverse_words: func [s [string!]] [form reverse parse s none]

Pruébelo: reverse_words "this is a string" "string a is this"

Answer 18

Este problema se puede resolver con O (n) en el tiempo y O (1) en el espacio. El código de muestra se ve como se menciona a continuación:

    public static string reverseWords(String s)
    {

        char[] stringChar = s.ToCharArray();
        int length = stringChar.Length, tempIndex = 0;

        Swap(stringChar, 0, length - 1);

        for (int i = 0; i < length; i++)
        {
            if (i == length-1)
            {
                Swap(stringChar, tempIndex, i);
                tempIndex = i + 1;
            }
            else if (stringChar[i] == '' '')
            {
                Swap(stringChar, tempIndex, i-1);
                tempIndex = i + 1;
            }
        }

        return new String(stringChar);
    }

    private static void Swap(char[] p, int startIndex, int endIndex)
    {
        while (startIndex < endIndex)
        {
            p[startIndex] ^= p[endIndex];
            p[endIndex] ^= p[startIndex];
            p[startIndex] ^= p[endIndex];
            startIndex++;
            endIndex--;
        }
    }

Answer 19

Algoritmo: 1). Resuelve cada palabra de la cadena. 2) .Rose resultante Cadena.

public class Solution {
public String reverseWords(String p) {
   String reg=" ";
  if(p==null||p.length()==0||p.equals(""))
{
    return "";
}
String[] a=p.split("//s+");
StringBuilder res=new StringBuilder();;
for(int i=0;i<a.length;i++)
{

    String temp=doReverseString(a[i]);
    res.append(temp);
    res.append(" ");
}
String resultant=doReverseString(res.toString());
System.out.println(res);
return resultant.toString().replaceAll("^//s+|//s+$", ""); 
}


public String doReverseString(String s)`{`


char str[]=s.toCharArray();
int start=0,end=s.length()-1;
while(start<end)
{
char temp=str[start];
str[start]=str[end];
str[end]=temp;
start++;
end--;
}
String a=new String(str);
return a;

}

public static void main(String[] args)
{
Solution r=new Solution();
String main=r.reverseWords("kya hua");
//System.out.println(re);
System.out.println(main);
}
}

Answer 20

El algoritmo para resolver este problema se basa en el proceso de dos pasos, el primer paso invertirá las palabras individuales de la cadena, luego en el segundo paso, invertirá la secuencia completa. La implementación del algoritmo tendrá O (n) tiempo y O (1) complejidad del espacio.

      #include <stdio.h>
      #include <string.h>

      void reverseStr(char* s, int start, int end);

      int main()
      {
              char s[] = "This is test string";

              int start = 0;
              int end = 0;
              int i = 0;

              while (1) {

              if (s[i] == '' '' || s[i] == ''/0'')
              {
                    reverseStr(s, start, end-1);
                    start = i + 1;
                    end = start;
              }
              else{
                    end++;
              }

              if(s[i] == ''/0''){
                   break;
              }
              i++;
      }

      reverseStr(s, 0, strlen(s)-1);
      printf("/n/noutput= %s/n/n", s);

      return 0;
  }

  void reverseStr(char* s, int start, int end)
  {
     char temp;
     int j = end;
     int i = start;

     for (i = start; i < j ; i++, j--) {
          temp = s[i];
          s[i] = s[j];
          s[j] = temp;
     }
 }

Answer 21

ESTE PROGRAMA ES INVALIDAR LA ORACIÓN MEDIANTE EL USO DE INDICADORES EN "C". Por Vasantha kumar y Sundaramoorthy de KONGU ENGG COLLEGE, Erode.

NOTA : la oración debe terminar con punto (.) Porque el carácter NULL no se asigna automáticamente al final de la oración *

 #include<stdio.h>
 #include<string.h>

int main()
{
char *p,*s="this is good.",*t;
int i,j,a,l,count=0;

l=strlen(s);

p=&s[l-1];

t=&s[-1];
while(*t)
   {
      if(*t=='' '')
     count++;
     t++;
   }
   a=count;
  while(l!=0)
   {
for(i=0;*p!='' ''&&t!=p;p--,i++);
   p++;

  for(;((*p)!=''.'')&&(*p!='' '');p++)
    printf("%c",*p);
  printf(" ");
  if(a==count)
   {
     p=p-i-1;
     l=l-i;
   }
  else
   {
     p=p-i-2;
     l=l-i-1;
   }

count--;
  }

return 0;  
}