عكس ترتيب الكلمات (وليس الأحرف) في مجموعة من الأحرف بكفاءة

Question

بالنظر إلى مجموعة من الأحرف التي تشكل جملة من الكلمات، قم بتوفير خوارزمية فعالة لعكس ترتيب الكلمات (وليس الأحرف) فيها.

مثال الإدخال والإخراج:

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

يجب أن يكون وقت O(N) ومساحة O(1) (split() والدفع/الخروج من المكدس غير مسموح به).

اللغز مأخوذ من هنا.

Answer 1

الحل في 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).

Answer 2

دفع سلسلة إلى مكدس ثم إخراجها - هل لا يزال هذا O(1)؟في الأساس، هذا هو نفس استخدام الانقسام () ...

ألا يعني O(1) في المكان؟تصبح هذه المهمة سهلة إذا تمكنا فقط من إلحاق السلاسل والأشياء، ولكن ذلك يستخدم مساحة...

يحرر:توماس واتنيدال على حق.الخوارزمية التالية هي O(n) في الوقت وO(1) في الفضاء:

1. سلسلة عكسية في مكانها (التكرار الأول على السلسلة)
2. عكس كل كلمة (معكوسة) في مكانها (تكراران آخران عبر السلسلة)
   1. العثور على حدود الكلمة الأولى
   2. عكس داخل حدود هذه الكلمة
   3. كرر للكلمة التالية حتى الانتهاء

أعتقد أننا سنحتاج إلى إثبات أن الخطوة 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

@ دارين توماس

تنفيذ الخوارزمية الخاصة بك (O(N) في الوقت المناسب، O(1) في الفضاء) في D (المريخ الرقمي):

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

Answer 7

في روبي

"هذه سلسلة".split.reverse.join(" ")

Answer 8

شركة:(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;
}

وهذا يعطي الإخراج:

بالنظر إلى مجموعة من الأحرف التي تشكل جملة من الكلمات ، أعط خوارزمية فعالة لعكس ترتيب الكلمات (وليس الأحرف) فيها.

.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 على الأكثر، مع مساحة ثابتة صغيرة.لسوء الحظ، فإنه لا يتعامل مع علامات الترقيم أو حالة الأحرف بأمان.

Answer 9

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

Answer 10

يمكنك استخدام ما يُعرف بالدالة العودية التكرارية، وهي 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)))

ملحوظة:لقد كتبت هذا في المخطط الذي أنا مبتدئ تمامًا، لذا أعتذر عن عدم التلاعب الصحيح بالسلسلة.

تقوم عملية إزالة الكلمة الأولى بالبحث عن حدود الكلمة الأولى من الجملة، ثم تأخذ هذا القسم من الأحرف (بما في ذلك المسافة وعلامات الترقيم) وتزيله وتعيد جملة جديدة

تبحث ميزة add-first-word عن حد الكلمة الأولى من الجملة، ثم تأخذ هذا القسم من الأحرف (بما في ذلك المسافة وعلامات الترقيم) وتضيفه إلى الجملة العكسية وتعيد محتويات الجملة العكسية الجديدة.

Answer 11

يهدف هذا البرنامج إلى عكس الجملة باستخدام المؤشرات في "لغة C" بقلم Vasantha kumar & Sundaramoorthy من KONGU ENGG COLLEGE، Erode.

ملحوظة:يجب أن تنتهي الجملة ب نقطة(.)لأنه لا يتم تعيين الحرف الفارغ تلقائيًا في نهاية الجملة*

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

Answer 12

ادفع كل كلمة إلى كومة.قم بإخراج كل الكلمات من المكدس.

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

فعال من حيث وقتي:استغرق الأمر أقل من دقيقتين للكتابة في REBOL:

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

حاول:revers_words "هذه سلسلة" "سلسلة A هي هذا"

Answer 15

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

Answer 16

حل روبي.

# 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)، وتم اختباره:

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

الخوارزمية: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<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

بطانة واحدة:

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

انتاج:

'?? expected as this Is'

Answer 21

تعتمد الخوارزمية لحل هذه المشكلة على عملية من خطوتين، الخطوة الأولى ستعكس الكلمات الفردية للسلسلة، ثم في الخطوة الثانية، ستعكس السلسلة بأكملها.سيستغرق تنفيذ الخوارزمية وقتًا 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;
     }
 }