単語の文を形成する文字の配列が与えられたとき、その中の単語 (文字ではない) の順序を逆にする効率的なアルゴリズムを与えてください。
入力と出力の例:
>>> reverse_words("this is a string")
'string a is this'
O(N) 時間と O(1) スペースである必要があります (split()スタックのプッシュ/ポップは許可されません)。
パズルはここから取られます。
d0mine
質問する
30830 次
21 に答える
34
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) です。2 番目のパスは、O(n + すべての単語の合計の長さ / 2) = O(n + n/2) = O(n) であり、これにより O(n) アルゴリズムになります。
于 2008-09-06T12:53:35.377 に答える
4
文字列をスタックにプッシュしてからポップする - それはまだ O(1) ですか? 基本的に、それは split() を使用するのと同じです...
O(1) はインプレースを意味しませんか? 文字列などを追加するだけでこのタスクは簡単になりますが、スペースを使用します...
編集: Thomas Watnedal は正しいです。次のアルゴリズムは、時間では O(n)、空間では O(1) です。
- 文字列のインプレース逆引き (文字列に対する最初の反復)
- 各単語をインプレースで反転 (反転) (文字列に対してさらに 2 回の反復)
- 最初の単語境界を見つける
- この単語境界内で反転
- 終わるまで次の単語を繰り返す
ステップ 2 が実際には O(2n) だけであることを証明する必要があると思います...
于 2008-09-06T13:12:16.957 に答える
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;
}
}
于 2008-09-06T14:43:43.087 に答える
2
これが私の答えです。ライブラリ呼び出しも一時データ構造もありません。
#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;
}
于 2010-09-14T18:34:13.313 に答える
1
@ダレン・トーマス
D (Digital Mars) でのアルゴリズム (時間の 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);
}
出力：
これは文字列です 文字列 a はこれです
于 2008-09-06T15:31:04.720 に答える
1
このプログラムは、「C 言語」でポインターを使用して文を反転することです KONGU ENGG COLLEGE、Erode の Vasantha kumar & Sundaramoorthy 著
注: 文末に 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=p-i-1;
l=l-i;
}
else
{
p=p-i-2;
l=l-i-1;
}
count--;
}
return 0;
}
于 2016-06-17T09:03:47.553 に答える
1
擬似コード:
reverse input string
reverse each word (you will need to find word boundaries)
于 2008-09-06T12:41:57.653 に答える
1
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;
}
これにより、次の出力が得られます。
単語の文を形成する文字の配列が与えられたとき、その中の単語 (文字ではない) の順序を逆にする効率的なアルゴリズムを与えてください。
.it in )characters not( 単語 順序の逆 アルゴリズムの効率的 与えられた ,文の単語 配列の文字が与えられた形式
これには最大で 4N の時間がかかり、一定のスペースが小さくなります。残念ながら、句読点や大文字と小文字を適切に処理しません。
于 2008-09-06T12:49:31.097 に答える
1
O(N) in space and O(N) in time solution in 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
于 2008-09-06T12:50:09.910 に答える
1
反復再帰関数として知られているものを使用します。これは、完了するまでに N (N は単語数) の反復が必要なため、時間的には O(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 は、文の最初の単語境界を見つけ、その部分の文字 (スペースと句読点を含む) を取り、それを逆文に追加して、新しい逆文の内容を返します。
于 2008-09-06T13:05:58.890 に答える
1
ルビーで
"これは文字列です".split.reverse.join(" ")
于 2008-09-16T22:44:40.583 に答える
0
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();
}
}
}
編集：私は質問全体を読むべきだと思います...続けてください。
于 2008-09-06T13:28:17.260 に答える
0
ワンライナー：
l="Is this as expected ??"
" ".join(each[::-1] for each in l[::-1].split())
出力：
'?? expected as this Is'
于 2014-12-03T18:31:46.243 に答える
0
この問題は、時間では 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--;
}
}
于 2014-05-15T00:35:49.317 に答える
0
この問題を解決するためのアルゴリズムは、2 つのステップのプロセスに基づいています。最初のステップでは文字列の個々の単語を反転し、次に 2 番目のステップで文字列全体を反転します。アルゴリズムの実装には、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;
}
}
于 2016-05-30T15:44:09.480 に答える
0
私の時間の点で効率的: REBOL で書くのに 2 分もかかりませんでした:
reverse_words: func [s [string!]] [form reverse parse s none]
試してみてください: reverse_words "これは文字列です" "文字列 a はこれです"
于 2009-06-18T06:36:37.750 に答える
0
各単語をスタックにプッシュします。スタックからすべての単語をポップします。
于 2008-09-06T12:44:21.470 に答える
0
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;
}
于 2008-09-06T13:06:31.383 に答える
0
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
于 2010-07-26T17:58:24.210 に答える
0
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;
}
于 2009-06-18T05:49:14.940 に答える
0
アルゴリズム: 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);
}
}
于 2014-12-22T12:37:12.957 に答える