Эффективно инвертируйте порядок слов (не символы) в массиве символов

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();

        }
    }
}

редактирование: я предполагаю, что должен читать, целый вопрос... продолжаются.

Решение 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;
}

Продвиньте каждое слово на стек. Вытолкайте все слова от стека.

Вы использовали бы то, что известно как повторяющаяся рекурсивная функция, которая является O (N) вовремя, поскольку он берет N (N быть количеством слов) повторения для завершения и O (1) в пространстве, поскольку каждое повторение содержит свое собственное состояние в аргументах функции.

(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)))

Примечание: Я записал это в схеме, которая я - полный новичок, таким образом, извинения из-за отсутствия корректной обработки строк.

remove-first-word находит первую границу слова предложения, затем берет тот раздел символов (включая пространство и пунктуацию) и удаляет его и возвращает новое предложение

, add-first-word находит первую границу слова предложения, затем берет тот раздел символов (включая пространство и пунктуацию) и добавляет его к обратному предложению и возвращает новое содержание обратного предложения.

O (N) в пространстве и O (N) в решении времени в 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

реализация @Daren Thomas

Вашего алгоритма (O (N) вовремя, O (1) в пространстве) в D (Цифровой Марс):

#!/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);
}

Вывод:

this is a string
string a is this

В 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;
}

Это дает вывод:

, Учитывая массив символов, которые формируют предложение слов, дайте эффективный алгоритм для инвертирования порядка слов (не символы) в нем.

.it в) символы не (слова порядка реверс к алгоритму, эффективному давание, слова предложения форма, какие символы массива, Учитывая

Это занимает самое большее время на 4 Н с маленьким постоянным пространством. К сожалению, Это не обрабатывает пунктуацию или случай корректно.

в Ruby

"это - строка" .split.reverse.join (" ")

В псевдо коде:

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

продвижение строки на стек и затем сование его прочь - является этим все еще O (1)? по существу это совпадает с разделением использования ()...

не Делает O (1), означают оперативный? Эта задача становится легкой, если мы можем просто добавить строки и материал, но это использует пространство...

РЕДАКТИРОВАНИЕ : Thomas Watnedal прав. Следующий алгоритм является O (n) вовремя и O (1) в пространстве:

1. реверс представляет в виде строки оперативный (первое повторение по строке)
2. реверс, каждое (обратное) оперативное слово (еще два повторения по строке)
   1. находит первую границу слова
   2. реверс в этой границе слова
   3. повторение для следующего слова, пока не закончено

, я предполагаю, что мы должны были бы доказать, что шаг 2 действительно только O (2n)...

#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;
    }
}

на C #, на месте, O (n), и протестировано:

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;
}

Efficient in terms of my time: took under 2 minutes to write in REBOL:

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

Try it out: reverse_words "это строка" "строка а это эта"

Рубиновый раствор.

# 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