颠倒string中单词的sorting
我有这个string s1 = "My name is XYZ" ，我想颠倒单词的顺序，这样s1 = "ZYX is name My" 。
我可以使用额外的数组。 我想很难，但有可能做到位（不使用额外的数据结构），时间复杂度是O（n）？
反转整个string，然后颠倒每个单词的字母。
第一次通过后，string将会是
s1 = "ZYX si eman yM"
在第二次传球之后
s1 = "ZYX is name My"
扭转string，然后在第二遍中，反转每个单词…
在C＃中，完全就地没有额外的数组：
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; }
Not exactly in place, but anyway: Python: >>> a = "These pretzels are making me thirsty" >>> " ".join(a.split()[::-1]) 'thirsty me making are pretzels These'
在Smalltalk中：
'These pretzels are making me thirsty' subStrings reduce: [:a :b| b, ' ', a]
我知道没有人关心Smalltalk，但对我来说太美了。
没有至less一些额外的数据结构，你不能做反转。 我认为当你交换字母时，最小的结构将是一个字符作为缓冲区。 它仍然可以被认为是“到位”，但它不完全是“额外的数据结构免费”。
下面是代码实施什么比尔蜥蜴描述：
string words = "this is a test"; // Reverse the entire string for(int i = 0; i < strlen(words) / 2; ++i) { char temp = words[i]; words[i] = words[strlen(words) - i]; words[strlen(words) - i] = temp; } // Reverse each word for(int i = 0; i < strlen(words); ++i) { int wordstart = -1; int wordend = -1; if(words[i] != ' ') { wordstart = i; for(int j = wordstart; j < strlen(words); ++j) { if(words[j] == ' ') { wordend = j - 1; break; } } if(wordend == -1) wordend = strlen(words); for(int j = wordstart ; j <= (wordend + wordstart) / 2 ; ++j) { char temp = words[j]; words[j] = words[wordend - (j - wordstart)]; words[wordend - (j - wordstart)] = temp; } i = wordend; } }
什么语言？ 如果PHP，你可以在空间上爆炸，然后将结果传递给array_reverse。
如果它不是PHP，你将不得不做一些更复杂的事情，比如：
words = aString.split(" "); for (i = 0; i < words.length; i++) { words[i] = words[words.length-i]; }
public static String ReverseString(String str) { int word_length = 0; String result = ""; for (int i=0; i<str.Length; i++) { if (str[i] == ' ') { result = " " + result; word_length = 0; } else { result = result.Insert(word_length, str[i].ToString()); word_length++; } } return result; }
这是C＃代码。
In Python... ip = "My name is XYZ" words = ip.split() words.reverse() print ' '.join(words)
无论如何，cookamunga使用python提供了很好的内联解决scheme！
这是假设所有的单词都是由空格分隔的：
#include <stdio.h> #include <string.h> int main() { char string[] = "What are you looking at"; int i, n = strlen(string); int tail = n-1; for(i=n-1;i>=0;i--) { if(string[i] == ' ' || i == 0) { int cursor = (i==0? i: i+1); while(cursor <= tail) printf("%c", string[cursor++]); printf(" "); tail = i-1; } } return 0; }
class Program { static void Main(string[] args) { string s1 =" My Name varma:; string[] arr = s1.Split(' '); Array.Reverse(arr); string str = string.Join(" ", arr); Console.WriteLine(str); Console.ReadLine(); } }
这不是完美的，但它现在适合我。 我不知道它是否有O（n）运行时间btw（仍然在研究它^^），但它使用一个额外的数组来完成任务。
这可能不是您的问题的最佳答案，因为我使用deststring来保存反转版本，而不是replace源string中的每个单词。 问题是我使用名为buf的本地堆栈variables来复制所有单词，而我不能复制到源string中，因为如果源string是const char *types，这会导致崩溃。
但是这是我第一次写作s.th. 像这样:)好吧blablub。 这里是代码：
#include <iostream> using namespace std; void reverse(char *des, char * const s); int main (int argc, const char * argv[]) { char* s = (char*)"reservered. rights All Saints. The 2011 (c) Copyright 11/10/11 on Pfundstein Markus by Created"; char *x = (char*)"Dogfish! White-spotted Shark, Bullhead"; printf("Before: |%s|\n", x); printf("Before: |%s|\n", s); char *d = (char*)malloc((strlen(s)+1)*sizeof(char)); char *i = (char*)malloc((strlen(x)+1)*sizeof(char)); reverse(d,s); reverse(i,x); printf("After: |%s|\n", i); printf("After: |%s|\n", d); free (i); free (d); return 0; } void reverse(char *dest, char *const s) { // create a temporary pointer if (strlen(s)==0) return; unsigned long offset = strlen(s)+1; char *buf = (char*)malloc((offset)*sizeof(char)); memset(buf, 0, offset); char *p; // iterate from end to begin and count how much words we have for (unsigned long i = offset; i != 0; i--) { p = s+i; // if we discover a whitespace we know that we have a whole word if (*p == ' ' || *p == '\0') { // we increment the counter if (*p != '\0') { // we write the word into the buffer ++p; int d = (int)(strlen(p)-strlen(buf)); strncat(buf, p, d); strcat(buf, " "); } } } // copy the last word p -= 1; int d = (int)(strlen(p)-strlen(buf)); strncat(buf, p, d); strcat(buf, "\0"); // copy stuff to destination string for (int i = 0; i < offset; ++i) { *(dest+i)=*(buf+i); } free(buf); }
我们可以将string插入到堆栈中，当我们提取单词时，它们将以相反的顺序排列。
void ReverseWords(char Arr[]) { std::stack<std::string> s; char *str; int length = strlen(Arr); str = new char[length+1]; std::string ReversedArr; str = strtok(Arr," "); while(str!= NULL) { s.push(str); str = strtok(NULL," "); } while(!s.empty()) { ReversedArr = s.top(); cout << " " << ReversedArr; s.pop(); } }
这个快速程序工作..虽然不检查angular落案件。
#include <stdio.h> #include <stdlib.h> struct node { char word[50]; struct node *next; }; struct stack { struct node *top; }; void print (struct stack *stk); void func (struct stack **stk, char *str); main() { struct stack *stk = NULL; char string[500] = "the sun is yellow and the sky is blue"; printf("\n%s\n", string); func (&stk, string); print (stk); } void func (struct stack **stk, char *str) { char *p1 = str; struct node *new = NULL, *list = NULL; int i, j; if (*stk == NULL) { *stk = (struct stack*)malloc(sizeof(struct stack)); if (*stk == NULL) printf("\n####### stack is not allocated #####\n"); (*stk)->top = NULL; } i = 0; while (*(p1+i) != '\0') { if (*(p1+i) != ' ') { new = (struct node*)malloc(sizeof(struct node)); if (new == NULL) printf("\n####### new is not allocated #####\n"); j = 0; while (*(p1+i) != ' ' && *(p1+i) != '\0') { new->word[j] = *(p1 + i); i++; j++; } new->word[j++] = ' '; new->word[j] = '\0'; new->next = (*stk)->top; (*stk)->top = new; } i++; } } void print (struct stack *stk) { struct node *tmp = stk->top; int i; while (tmp != NULL) { i = 0; while (tmp->word[i] != '\0') { printf ("%c" , tmp->word[i]); i++; } tmp = tmp->next; } printf("\n"); }
这些答案中的大多数未能解释inputstring中的前导和/或尾随空格。 考虑一下str=" Hello world" …反转整个string和反转单个单词的简单algorithm最终会导致f(str) == "world Hello "翻转分隔符。
OP说：“我想扭转单词的顺序”，并没有提到前后空格也应该翻转！ 所以，虽然已经有了很多的答案，但我会在C ++中提供一个[希望]更正确的答案：
#include <string> #include <algorithm> void strReverseWords_inPlace(std::string &str) { const char delim = ' '; std::string::iterator w_begin, w_end; if (str.size() == 0) return; w_begin = str.begin(); w_end = str.begin(); while (w_begin != str.end()) { if (w_end == str.end() || *w_end == delim) { if (w_begin != w_end) std::reverse(w_begin, w_end); if (w_end == str.end()) break; else w_begin = ++w_end; } else { ++w_end; } } // instead of reversing str.begin() to str.end(), use two iterators that // ...represent the *logical* begin and end, ignoring leading/traling delims std::string::iterator str_begin = str.begin(), str_end = str.end(); while (str_begin != str_end && *str_begin == delim) ++str_begin; --str_end; while (str_end != str_begin && *str_end == delim) --str_end; ++str_end; std::reverse(str_begin, str_end); }
我使用堆栈的版本：
public class Solution { public String reverseWords(String s) { StringBuilder sb = new StringBuilder(); String ns= s.trim(); Stack<Character> reverse = new Stack<Character>(); boolean hadspace=false; //first pass for (int i=0; i< ns.length();i++){ char c = ns.charAt(i); if (c==' '){ if (!hadspace){ reverse.push(c); hadspace=true; } }else{ hadspace=false; reverse.push(c); } } Stack<Character> t = new Stack<Character>(); while (!reverse.empty()){ char temp =reverse.pop(); if(temp==' '){ //get the stack content out append to StringBuilder while (!t.empty()){ char c =t.pop(); sb.append(c); } sb.append(' '); }else{ //push to stack t.push(temp); } } while (!t.empty()){ char c =t.pop(); sb.append(c); } return sb.toString(); } }
将每个单词作为string存储在数组中，然后从最后打印
public void rev2() { String str = "my name is ABCD"; String A[] = str.split(" "); for (int i = A.length - 1; i >= 0; i--) { if (i != 0) { System.out.print(A[i] + " "); } else { System.out.print(A[i]); } } }
在Python中，如果你不能使用[:: – 1]或者反向（），以下是简单的方法：
def reverse(text): r_text = text.split(" ") res = [] for word in range(len(r_text) - 1, -1, -1): res.append(r_text[word]) return " ".join(res) print (reverse("Hello World")) >> World Hello [Finished in 0.1s]
使用C＃按给定语句的相反顺序打印单词：
void ReverseWords(string str) { int j = 0; for (int i = (str.Length - 1); i >= 0; i--) { if (str[i] == ' ' || i == 0) { j = i == 0 ? i : i + 1; while (j < str.Length && str[j] != ' ') Console.Write(str[j++]); Console.Write(' '); } } }
其实第一个答案是：
words = aString.split(" "); for (i = 0; i < words.length; i++) { words[i] = words[words.length-i]; }
因为它在上半年的循环的后半部分没有实现。 所以，我<words.length / 2会起作用，但更清晰的例子是：
words = aString.split(" "); // make up a list i = 0; j = words.length - 1; // find the first and last elements while (i < j) { temp = words[i]; words[i] = words[j]; words[j] = temp; //ie swap the elements i++; j--; }
注意：我不熟悉PHP语法，因为它看起来与Perl相似，所以我已经猜到了增加和减less的语法。
怎么样 …
var words = "My name is XYZ"; var wr = String.Join( " ", words.Split(' ').Reverse().ToArray() );
我想这不是在线的寿。
在c中，这是你如何做，O（N）和只使用O（1）数据结构（即字符）。
#include<stdio.h> #include<stdlib.h> main(){ char* a = malloc(1000); fscanf(stdin, "%[^\0\n]", a); int x = 0, y; while(a[x]!='\0') { if (a[x]==' ' || a[x]=='\n') { x++; } else { y=x; while(a[y]!='\0' && a[y]!=' ' && a[y]!='\n') { y++; } int z=y; while(x<y) { y--; char c=a[x];a[x]=a[y];a[y]=c; x++; } x=z; } } fprintf(stdout,a); return 0; }
使用sscanf可以做得更简单：
void revertWords(char *s); void revertString(char *s, int start, int n); void revertWordsInString(char *s); void revertString(char *s, int start, int end) { while(start<end) { char temp = s[start]; s[start] = s[end]; s[end]=temp; start++; end --; } } void revertWords(char *s) { int start = 0; char *temp = (char *)malloc(strlen(s) + 1); int numCharacters = 0; while(sscanf(&s[start], "%s", temp) !=EOF) { numCharacters = strlen(temp); revertString(s, start, start+numCharacters -1); start = start+numCharacters + 1; if(s[start-1] == 0) return; } free (temp); } void revertWordsInString(char *s) { revertString(s,0, strlen(s)-1); revertWords(s); } int main() { char *s= new char [strlen("abc deff gh1 jkl")+1]; strcpy(s,"abc deff gh1 jkl"); revertWordsInString(s); printf("%s",s); return 0; }
import java.util.Scanner; public class revString { static char[] str; public static void main(String[] args) { //Initialize string //str = new char[] { 'h', 'e', 'l', 'l', 'o', ' ', 'a', ' ', 'w', 'o', //'r', 'l', 'd' }; getInput(); // reverse entire string reverse(0, str.length - 1); // reverse the words (delimeted by space) back to normal int i = 0, j = 0; while (j < str.length) { if (str[j] == ' ' || j == str.length - 1) { int m = i; int n; //dont include space in the swap. //(special case is end of line) if (j == str.length - 1) n = j; else n = j -1; //reuse reverse reverse(m, n); i = j + 1; } j++; } displayArray(); } private static void reverse(int i, int j) { while (i < j) { char temp; temp = str[i]; str[i] = str[j]; str[j] = temp; i++; j--; } } private static void getInput() { System.out.print("Enter string to reverse: "); Scanner scan = new Scanner(System.in); str = scan.nextLine().trim().toCharArray(); } private static void displayArray() { //Print the array for (int i = 0; i < str.length; i++) { System.out.print(str[i]); } }
}
在Java中使用额外的String（使用StringBuilder）：
public static final String reverseWordsWithAdditionalStorage(String string) { StringBuilder builder = new StringBuilder(); char c = 0; int index = 0; int last = string.length(); int length = string.length()-1; StringBuilder temp = new StringBuilder(); for (int i=length; i>=0; i--) { c = string.charAt(i); if (c == SPACE || i==0) { index = (i==0)?0:i+1; temp.append(string.substring(index, last)); if (index!=0) temp.append(c); builder.append(temp); temp.delete(0, temp.length()); last = i; } } return builder.toString(); }
在Java中：
public static final String reverseWordsInPlace(String string) { char[] chars = string.toCharArray(); int lengthI = 0; int lastI = 0; int lengthJ = 0; int lastJ = chars.length-1; int i = 0; char iChar = 0; char jChar = 0; while (i<chars.length && i<=lastJ) { iChar = chars[i]; if (iChar == SPACE) { lengthI = i-lastI; for (int j=lastJ; j>=i; j--) { jChar = chars[j]; if (jChar == SPACE) { lengthJ = lastJ-j; swapWords(lastI, i-1, j+1, lastJ, chars); lastJ = lastJ-lengthI-1; break; } } lastI = lastI+lengthJ+1; i = lastI; } else { i++; } } return String.valueOf(chars); } private static final void swapWords(int startA, int endA, int startB, int endB, char[] array) { int lengthA = endA-startA+1; int lengthB = endB-startB+1; int length = lengthA; if (lengthA>lengthB) length = lengthB; int indexA = 0; int indexB = 0; char c = 0; for (int i=0; i<length; i++) { indexA = startA+i; indexB = startB+i; c = array[indexB]; array[indexB] = array[indexA]; array[indexA] = c; } if (lengthB>lengthA) { length = lengthB-lengthA; int end = 0; for (int i=0; i<length; i++) { end = endB-((length-1)-i); c = array[end]; shiftRight(endA+i,end,array); array[endA+1+i] = c; } } else if (lengthA>lengthB) { length = lengthA-lengthB; for (int i=0; i<length; i++) { c = array[endA]; shiftLeft(endA,endB,array); array[endB+i] = c; } } } private static final void shiftRight(int start, int end, char[] array) { for (int i=end; i>start; i--) { array[i] = array[i-1]; } } private static final void shiftLeft(int start, int end, char[] array) { for (int i=start; i<end; i++) { array[i] = array[i+1]; } }
这是一个C实现，它正在执行逆向插入这个词，它具有O(n)复杂性。
char* reverse(char *str, char wordend=0) { char c; size_t len = 0; if (wordend==0) { len = strlen(str); } else { for(size_t i=0;str[i]!=wordend && str[i]!=0;i++) len = i+1; } for(size_t i=0;i<len/2;i++) { c = str[i]; str[i] = str[len-i-1]; str[len-i-1] = c; } return str; } char* inplace_reverse_words(char *w) { reverse(w); // reverse all letters first bool is_word_start = (w[0]!=0x20); for(size_t i=0;i<strlen(w);i++){ if(w[i]!=0x20 && is_word_start) { reverse(&w[i], 0x20); // reverse one word only is_word_start = false; } if (!is_word_start && w[i]==0x20) // found new word is_word_start = true; } return w; }
c＃解决scheme来翻译一个句子中的单词
using System; class helloworld { public void ReverseString(String[] words) { int end = words.Length-1; for (int start = 0; start < end; start++) { String tempc; if (start < end ) { tempc = words[start]; words[start] = words[end]; words[end--] = tempc; } } foreach (String s1 in words) { Console.Write("{0} ",s1); } } } class reverse { static void Main() { string s= "beauty lies in the heart of the peaople"; String[] sent_char=s.Split(' '); helloworld h1 = new helloworld(); h1.ReverseString(sent_char); } }
输出：peaople心中的美女按任意键继续。 。 。
更好的版本
检查我的博客http://bamaracoulibaly.blogspot.co.uk/2012/04/19-reverse-order-of-words-in-text.html
public string reverseTheWords(string description) { if(!(string.IsNullOrEmpty(description)) && (description.IndexOf(" ") > 1)) { string[] words= description.Split(' '); Array.Reverse(words); foreach (string word in words) { string phrase = string.Join(" ", words); Console.WriteLine(phrase); } return phrase; } return description; }
public class manip{ public static char[] rev(char[] a,int left,int right) { char temp; for (int i=0;i<(right - left)/2;i++) { temp = a[i + left]; a[i + left] = a[right -i -1]; a[right -i -1] = temp; } return a; } public static void main(String[] args) throws IOException { String s= "i think this works"; char[] str = s.toCharArray(); int i=0; rev(str,i,s.length()); int j=0; while(j < str.length) { if (str[j] != ' ' && j != str.length -1) { j++; } else { if (j == (str.length -1)) { j++; } rev(str,i,j); i=j+1; j=i; } } System.out.println(str); }
我知道有几个正确的答案。 我想到了C中的那个。 这是例外答案的执行。 时间复杂度是O（n），不用额外的string。
#include<stdio.h> char * strRev(char *str, char tok) { int len = 0, i; char *temp = str; char swap; while(*temp != tok && *temp != '\0') { len++; temp++; } len--; for(i = 0; i < len/2; i++) { swap = str[i]; str[i] = str[len - i]; str[len - i] = swap; } // Return pointer to the next token. return str + len + 1; } int main(void) { char a[] = "Reverse this string."; char *temp = a; if (a == NULL) return -1; // Reverse whole string character by character. strRev(a, '\0'); // Reverse every word in the string again. while(1) { temp = strRev(temp, ' '); if (*temp == '\0') break; temp++; } printf("Reversed string: %s\n", a); return 0; }
用法
char str[50] = {0}; strcpy(str, (char*)"My name is Khan"); reverseWords(str);
方法
void reverseWords(char* pString){ if(NULL ==pString){ return; } int nLen = strlen(pString); reverseString(pString,nLen); char* start = pString; char* end = pString; nLen = 0; while (*end) { if(*end == ' ' ){ reverseString(start,nLen); end++; start = end; nLen = 0; continue; } nLen++; end++; } reverseString(start,nLen); printf("\n Reversed: %s",pString); } void reverseString(char* start,int nLen){ char* end = start+ nLen-1; while(nLen > 0){ char temp = *start; *start = *end; *end = temp; end--; start++; nLen-=2; } }
