문자 배열에서 단어(문자 아님)의 순서를 효율적으로 반대로 바꿉니다.
https://stackoverflow.com/questions/47402
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
단어의 문장을 구성하는 문자 배열이 주어지면 그 안에 있는 단어(문자가 아닌)의 순서를 바꾸는 효율적인 알고리즘을 제공하십시오.
입력 및 출력 예시:
>>> reverse_words("this is a string")
'string a is this'
O(N) 시간과 O(1) 공간이어야 합니다(split() 스택을 밀거나 터뜨리는 것은 허용되지 않습니다.
퍼즐은 다음에서 가져왔습니다. 여기.
해결책
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) 알고리즘이 됩니다.
다른 팁
문자열을 스택에 밀어넣고 터뜨리는 것 - 아직도 O(1)인가요?본질적으로 이는 Split()을 사용하는 것과 같습니다...
O(1)은 in-place를 의미하지 않나요?문자열 등을 추가하면 이 작업이 쉬워지지만 공간을 사용하게 됩니다...
편집하다:토마스 와트네달이 옳습니다.다음 알고리즘은 시간에서는 O(n)이고 공간에서는 O(1)입니다.
- 제자리에서 문자열 역방향(문자열에 대한 첫 번째 반복)
- 각 (역전된) 단어를 제자리에서 뒤집습니다(문자열에 대해 또 다른 두 번의 반복).
- 첫 번째 단어 경계 찾기
- 이 단어 경계 내에서 반전
- 끝날 때까지 다음 단어를 반복하세요
제 생각에는 2단계가 실제로 O(2n)에 불과하다는 것을 증명해야 할 것 같습니다...
#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;
}
}
내 대답은 다음과 같습니다.라이브러리 호출도 없고 임시 데이터 구조도 없습니다.
#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;
}
의사 코드에서:
reverse input string
reverse each word (you will need to find word boundaries)
@다렌 토마스
D(디지털 화성)에서 알고리즘(시간 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);
}
산출:
this is a string string a is this
루비에서
"이것은 문자열입니다.".split.reverse.join(" ")
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) 문자 (단어의 단어는 알고리즘에 대한 반대의 반대 효율적인 주어진 문장, 주어진 배열의 문자가있는 형식입니다.
일정한 공간이 작고 최대 4N 시간이 소요됩니다.불행하게도 구두점이나 대소문자를 정상적으로 처리하지 못합니다.
Python의 공간 솔루션에서는 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
반복 재귀 함수라고 알려진 것을 사용합니다. 이는 완료하는 데 N(N은 단어 수) 반복이 필요하고 각 반복이 자체 상태를 유지하므로 공간에서는 O(1)이므로 시간상 O(N)입니다. 함수 인수.
(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는 문장의 첫 번째 단어 경계를 찾은 다음 해당 문자 섹션(공백 및 구두점 포함)을 가져와 이를 역문장에 추가하고 새로운 역문장 내용을 반환합니다.
이 프로그램은 "C 언어"에서 포인터를 사용하여 문장을 뒤집는 것입니다. 작성자: Erode, KONGU ENGG COLLEGE의 Vasantha kumar 및 Sundaramoorthy.
메모:문장은 다음으로 끝나야 합니다. 점(.)널 문자는 문장 끝에 자동으로 할당되지 않기 때문에*
#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;
}
각 단어를 스택에 푸시합니다.스택에서 모든 단어를 팝합니다.
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();
}
}
}
편집하다:질문을 다 읽어야 할 것 같아요...계속하세요.
내 시간 측면에서 효율적입니다.REBOL에 작성하는 데 2분도 채 걸리지 않았습니다.
reverse_words: func [s [string!]] [form reverse parse s none]
사용해 보세요:reverse_words "이것은 문자열입니다" "문자열 a입니다."
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;
}
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
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;
}
이 문제는 시간에서는 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--;
}
}
연산: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);
}
}
하나의 라이너 :
l="Is this as expected ??"
" ".join(each[::-1] for each in l[::-1].split())
산출:
'?? expected as this Is'
이 문제를 해결하기 위한 알고리즘은 두 단계 프로세스를 기반으로 합니다. 첫 번째 단계에서는 문자열의 개별 단어를 뒤집고 두 번째 단계에서는 전체 문자열을 뒤집습니다.알고리즘을 구현하려면 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;
}
}
제휴하지 않습니다 StackOverflow
