Эффективно изменить порядок слов (не символов) в массиве символов

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

Пример ввода и вывода:

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

Это должно быть время O (N), а O (1) пробел ( split() и нажатие / выключение стека не допускаются).

Головоломка взята отсюда .

    21 Solutions collect form web for “Эффективно изменить порядок слов (не символов) в массиве символов”

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

    Это должно быть O (n) во времени и O (1) в пространстве.

    Изменить: немного почистил.

    Первый проход по строке, очевидно, равен O (n / 2) = O (n). Второй проход - O (n + комбинированная длина всех слов / 2) = O (n + n / 2) = O (n), что делает этот алгоритм O (n).

    нажав строку на стек, а затем выталкивая ее – это все еще O (1)? по существу, то же самое, что и использование split () …

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

    EDIT : Томас Уотдаль прав. Следующий алгоритм O (n) во времени и O (1) в пространстве:

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

    Думаю, нам нужно будет доказать, что шаг 2 действительно только O (2n) …

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

    Вот мой ответ. Нет вызовов библиотеки и структур временных данных.

     #include  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 

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

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

    @ Daren Thomas

    Реализация вашего алгоритма (O (N) во времени, O (1) в пространстве) в D (Digital Mars):

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

    Вывод:

      это строка
     string a это 

    в Рубине

    “это строка” .split.reverse.join (“”)

    В C: (C99)

     #include  #include  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 in) символы нет (слова порядка обратного алгоритма, эффективные дайте, слова предложения - форма, которые являются символами массива a

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

    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 

    Вы должны использовать так называемую итеративно-рекурсивную функцию, которая является 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 находит первую границу слова предложения, затем принимает этот раздел символов (включая пробел и пунктуацию) и добавляет его к обратному предложению и возвращает новое обратное предложение.

    ЭТА ПРОГРАММА ОБЕСПЕЧИВАЕТ ПРЕДЛОЖЕНИЕ С ИСПОЛЬЗОВАНИЕМ УКАЗАТЕЛЕЙ НА «C-языке». Vasantha kumar & Sundaramoorthy из KONGU ENGG COLLEGE, Erode.

    ПРИМЕЧАНИЕ . Предложение должно заканчиваться точкой (.), Поскольку символ NULL не назначается автоматически в конце предложения *

      #include #include 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=pi-1; l=li; } else { p=pi-2; l=li-1; } count--; } return 0; } в  #include #include 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=pi-1; l=li; } else { p=pi-2; l=li-1; } count--; } return 0; } в  #include #include 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=pi-1; l=li; } else { p=pi-2; l=li-1; } count--; } return 0; } 

    Нажимайте каждое слово на стек. Выложите все слова из стека.

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

    редактирование: я думаю, я должен прочитать весь вопрос … продолжить.

    Эффективен с точки зрения моего времени: занял менее 2 минут, чтобы написать в REBOL:

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

    Попробуйте: reverse_words “это строка” “строка a это”

    Решение C ++:

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

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

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

    Эту проблему можно решить с помощью O (n) во времени и O (1) в пространстве. Пример кода выглядит так:

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

    Алгоритм: 1). Разверните каждое слово строки. 2). Измените результирующую строку.

     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 в 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 

    Один вкладыш:

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

    Вывод:

     '?? expected as this Is' 

    Алгоритм для решения этой проблемы основан на двухэтапном процессе, первый шаг будет отменять отдельные слова строки, а затем на втором этапе отменить целую строку. Реализация алгоритма займет время O (n) и сложность пространства O (1).

      #include  #include  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; } } 
    Interesting Posts

    Что делает postInvalidate ()?

    Как сравнить строки в выражении «if»?

    Угловая директива динамического шаблона Angular.js

    Автоматическое открытие InfoWindow при добавлении маркера Google Maps v2 Android

    Как поймать ВСЕ исключения / сбои в приложении .NET

    Узнайте, где определена $ PATH

    Самый эффективный способ протоколирования сообщений в JavaFX TextArea через streamи с помощью простых пользовательских фреймворков регистрации

    Intel SRT / RST сообщает об ошибке «без загрузочного устройства» после двух перезагрузок

    Как получить продолжительность видео с mp4, wmv, flv, mov videos

    В чем разница между compare () и compareTo ()?

    Переустановка Mac OS X без оригинального диска

    Внимание: на этапе сборки ресурсов копирования Bundle содержится файл Info.plist этой цели

    Разница между пользователем и схемой в Oracle?

    Содержимое центра в ответном бутстрапе navbar

    Можно ли добавить параметр контекстного меню проводника Windows, чтобы запустить командную строку в выбранном каталоге?

    Давайте будем гением компьютера.