有效地颠倒字符数组中字（不是字符）的顺序

给定一组形成一个单词的字符，给出一个有效的algorithm来颠倒单词的顺序（不是字符）。

示例input和输出：

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

它应该是O（N）时间和O（1）空间（ split()和推/popup堆栈是不允许的）。

拼图从这里被拿走。

Answer 1

C / C ++中的解决scheme：

 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], ip); p=i+1; } } //Finally reverse the last word. reverse_string(&str[p], lp); } 

这应该是O（n）在时间和O（1）在空间。

编辑：清理了一下。

string的第一遍显然是O（n / 2）= O（n）。 第二遍是O（n +所有字的组合长度）= O（n + n / 2）= O（n），这使得这是一个O（n）algorithm。

Answer 2

把一个string推到一个堆栈然后popup – 那还是O（1）吗？ 本质上，这是相同的使用split（）…

O（1）是不是就地？ 如果我们只能附加string和东西，但是使用空间，这个任务变得容易…

编辑 ：托马斯Watnedal是正确的。 下面的algorithm是O（n），O（1）是空间：

1. 反向string就地（首次迭代string）
2. 反转每个（反向）单词in-place（另外两个string迭代）
   1. find第一个字的边界
   2. 在这个单词边界内反转
   3. 重复下一个词，直到完成

我想我们需要certificate第2步实际上只有O（2n）…

Answer 3

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

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

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

在伪代码中：

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

Answer 6

@Daren Thomas

在D（数字火星）中实现你的algorithm（时间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); } 

输出：

 这是一个string
stringa是这个 

Answer 7

在Ruby中

“这是一个string”.split.reverse.join（“”）

Answer 8

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

这给出了输出：

给定一组形成一个单词的字符，给出一个有效的algorithm来颠倒单词（而不是字符）的顺序。

（其中）字符不是（对于algorithm有效性给出了相反的顺序，

这最多需要4N时间，具有小的恒定空间。 不幸的是，它不能正确处理标点或情况。

Answer 9

Python中的O（N）和O（N）中的解决scheme：

 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 10

你将使用所谓的迭代recursion函数，它是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))) 

注：我已经写了这个计划，我是一个完全新手，所以对缺乏正确的string操纵道歉。

删除第一个单词find句子的第一个单词边界，然后将该部分的字符（包括空格和标点符号）移除并返回新的句子

添加第一个单词find句子的第一个单词边界，然后将该部分字符（包括空格和标点符号）添加到反向句子中，并返回新的反向句子内容。

Answer 11

本程序将使用Erode的KONGU ENGG COLLEGE的Vasantha kumar和Sundaramoorthy以“C语言”的指针来反转SENTENCE。

注意 ：句子必须以点（。）结尾，因为NULL字符在句子末尾不会自动分配*

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

Answer 12

将每个单词推入堆栈。 从堆栈中popup所有的单词。

Answer 13

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

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

Answer 14

我的时间有效率：花了2分钟写下REBOL：

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

试试看：reverse_words“这是一个string”“stringa是这个”

Answer 15

一个C ++解决scheme：

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

一个Ruby解决scheme。

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

在C＃中，就地，O（n），并testing：

 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 18

这个问题可以用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--; } } 

Answer 19

algorithm：1）。反转string的每个字。 2）。反转结果string。

 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

一个class轮：

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

输出：

 '?? expected as this Is' 

Answer 21

解决这个问题的algorithm是基于两个步骤的过程，第一步将反转string的单个单词，然后在第二步，反转整个string。 algorithm的实现将花费O（n）时间和O（1）空间复杂度。

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