给定一个组成单词句子的字符数组，请提供一种有效的算法来反转单词(不是字符)在其中的顺序。

输入和输出示例：

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

应该是O(N)时间和O(1)空间(不允许使用split()和压入/弹出堆栈)。

难题是从这里拿走的。

解决方案

回答

用伪代码：

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

回答

将每个单词推入堆栈。弹出所有单词。

回答

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

这给出了输出：

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. 
  
  .it in )characters not( words the
  of order the reverse to algorithm
  efficient an give ,words of sentence a
  form which characters of array an
  Given

这最多需要4N的时间，并且占用的空间很小。
不幸的是，它不能优雅地处理标点符号或者大小写。

回答

Python中空间的O(N)和时间的O(N)：

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

回答

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

时间上应为O(n)，空间上应为O(1)。

编辑：清理了一下。

字符串的第一遍显然是O(n / 2)= O(n)。第二遍是O(n +所有单词的总长度/ 2)= O(n + n / 2)= O(n)，这使其成为O(n)算法。

回答

我们将使用所谓的迭代递归函数，它是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 ++解决方案：

#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(1)？
本质上，这与使用split()相同。

O(1)不是就地意味着吗？如果我们仅可以追加字符串和内容，则此任务将变得很容易，但这会占用空间...

编辑：托马斯·沃特纳达尔是正确的。以下算法在时间上是O(n)在空间上是O(1)：

• 原位反向字符串(字符串的第一次迭代)
• 在这个词的边界内反转
• 重复下一个单词直到完成

我想我们需要证明步骤2实际上只是O(2n)...

回答

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

        }
    }
}

编辑：我想我应该阅读整个问题...继续。

回答

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

回答

@达伦·托马斯(Daren Thomas)

在D(数字火星)中实现算法(时间为O(N)，时间为O(1))：

#!/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

回答

在Ruby中

"this is a string".split.reverse.join(" ")

回答

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

回答

我的时间效率高：用不到2分钟的时间用REBOL编写：

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

试试看：
reverse_words"这是一个字符串"
"字符串a是这个"

回答

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

回答

这是我的答案。没有库调用，也没有临时数据结构。

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