Đảo ngược thứ tự các từ (không phải ký tự) một cách hiệu quả trong một dãy ký tự

Question

Cho một dãy các ký tự tạo thành một câu, cung cấp thuật toán hiệu quả để đảo ngược thứ tự của các từ (không phải ký tự) trong đó.

Ví dụ đầu vào và đầu ra:

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

Nên O (N) thời gian và O (1) không gian (split() và đẩy bật/popping ra khỏi ngăn xếp không được phép).

Câu đố được lấy từ here.

Answer 1

Một giải pháp trong 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); 
} 

này cần được O (n) trong thời gian và O (1) trong không gian.

Chỉnh sửa: Làm sạch nó một chút.

Vượt qua đầu tiên qua chuỗi rõ ràng là O (n/2) = O (n). Pass thứ hai là O (n + chiều dài kết hợp của tất cả các từ/2) = O (n + n/2) = O (n), mà làm cho một thuật toán O (n).

Answer 2

Trong mã giả:

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

Answer 3

Đẩy mỗi từ trên một chồng. Bật tất cả các từ khỏi ngăn xếp.

Answer 4

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

Điều này cho phép đầu ra:

Với một loạt các ký tự mà hình thức một câu từ, đưa ra một thuật toán hiệu quả để đảo ngược thứ tự của các từ (không phải ký tự) trong .

.it in) ký tự không (lời trật tự ngược lại để thuật toán hiệu quả một Hãy cho, lời của câu một hình thức mà nhân vật của mảng một Với

này cần có thời gian ở 4N nhất ., với không gian liên tục nhỏ Thật không may, nó không xử lý dấu chấm câu hoặc trường hợp một cách duyên dáng

Answer 5

O (N) trong không gian và O (N) trong dung dịch thời gian bằng 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 

Answer 6

Bạn sẽ sử dụng hàm được gọi là hàm đệ quy lặp lại, là O (N) theo thời gian khi cần N (N là số từ) lặp và O (1) trong không gian vì mỗi lần lặp trạng thái riêng của nó trong các đối số hàm.

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

Lưu ý: Tôi đã viết đề án này là một người mới hoàn chỉnh, vì vậy xin lỗi vì thiếu thao tác chuỗi chính xác.

remove-đầu-word thấy ranh giới từ đầu tiên của câu, sau đó mất rằng phần của nhân vật (bao gồm cả không gian và dấu chấm câu) và loại bỏ nó và trả về câu mới

add-đầu-word thấy từ đầu tiên ranh giới của câu, sau đó lấy phần ký tự đó (bao gồm dấu cách và dấu chấm câu) và thêm nó vào câu ngược và trả về nội dung câu ngược mới.

Answer 7

Một C++ giải pháp:

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

đẩy một chuỗi lên một chồng và sau đó popping nó đi - đó là vẫn còn O (1)? về cơ bản, điều đó giống như sử dụng split() ...

Không O (1) có nghĩa là tại chỗ? Công việc này trở nên dễ dàng nếu chúng ta chỉ có thể nối chuỗi và nội dung, nhưng sử dụng không gian ...

EDIT: Thomas Watnedal là đúng. Thuật toán sau đây là O (n) trong thời gian và O (1) trong không gian:

1. chuỗi ngược tại chỗ (lặp đầu tiên trên string)
2. đảo ngược từng từ (đảo ngược) tại chỗ (hai khác lặp đi lặp lại qua chuỗi)
   1. tìm ranh giới từ đầu tiên
   2. ngược bên trong ranh giới từ này
   3. lặp lại cho từ kế tiếp cho đến khi xong

Tôi đoán chúng ta sẽ cần phải chứng minh rằng bước 2 thực sự là chỉ O (2n) ...

Answer 9

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

     } 
    } 
} 

chỉnh sửa: tôi đoán tôi nên đọc toàn bộ câu hỏi ... mang về.

Answer 10

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

@Daren Thomas

Thực hiện các thuật toán của bạn (O (N) trong thời gian, O (1) trong không gian) trong 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); 
} 

Output:

this is a string 
string a is this

Answer 12

trong Ruby

"đây là chuỗi" .split.reverse.tham gia (" ")

Answer 13

trong C#, tại chỗ, O (n), và thử nghiệm:

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 14

hiệu quả về mặt thời gian của tôi: mất dưới 2 phút để viết trong REBOL :

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

Hãy thử nó ra: reverse_words "này là một chuỗi" "chuỗi a là này"

Answer 15

Giải pháp 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 

Answer 16

Đây là câu trả lời của tôi. Không có cuộc gọi thư viện và không có cấu trúc dữ liệu tạm thời.

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

Vấn đề này có thể được giải quyết bằng O (n) theo thời gian và O (1) trong không gian. Mẫu mã trông như đã đề cập dưới đây:

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 18

Một lót:

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

Output:

'?? expected as this Is' 

Answer 19

Thuật toán: 1) .Reverse mỗi từ của chuỗi. 2) .Reverse resultant 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

Thuật toán để giải quyết vấn đề này được dựa trên quá trình hai bước, bước đầu tiên sẽ đảo ngược những từ riêng lẻ của chuỗi, sau đó trong bước thứ hai, ngược lại toàn bộ chuỗi. Việc thực hiện thuật toán sẽ mất thời gian O (n) và độ phức tạp không gian 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; 
    } 
} 

Answer 21

chương trình này là để đảo ngược bản án sử dụng con trỏ IN "ngôn ngữ C" Bằng Vasantha kumar & Sundaramoorthy từ Kongu ENGG COLLEGE, Erode.

LƯU Ý: Câu phải kết thúc với dot vì nhân vật NULL không được gán tự động ở phần cuối của câu *

#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=p-i-1; 
    l=l-i; 
    } 
    else 
    { 
    p=p-i-2; 
    l=l-i-1; 
    } 

count--; 
    } 

return 0; 
}