g********r 发帖数: 89 | 1 大牛来指点一下代码有没有改进的地方?
方法的就是从string tail开始一个一个的读
string reverseWord(string s)
{
string result;
int i=s.size()-1; //start from the last character
while(i>=0){
while(i>=0 && isspace(s[i])) i--; //advance i to a non-space letter
int j=i-1;
while(j>=0 && !isspace(s[j])) j--; //find the previous space
result += s.substr(j+1, i-j);
if(j>=0) result += " ";
i = j-1;
}
return result;
} |
r*******e 发帖数: 971 | 2 isspace 这是啥么?有必要新造一个helper么? |
s**x 发帖数: 7506 | 3 你的方法彻头彻尾没有一点点对的地方,从函数signature 到思路。
这是个很古老的题了,为什么不先Google 一下呢?cc150 上好像就有这题。你这种刷
题方法可能效果是反的。
letter
★ 发自iPhone App: ChineseWeb 8.7
【在 g********r 的大作中提到】 : 大牛来指点一下代码有没有改进的地方? : 方法的就是从string tail开始一个一个的读 : string reverseWord(string s) : { : string result; : int i=s.size()-1; //start from the last character : while(i>=0){ : while(i>=0 && isspace(s[i])) i--; //advance i to a non-space letter : int j=i-1; : while(j>=0 && !isspace(s[j])) j--; //find the previous space
|
f***c 发帖数: 338 | 4 In Python:
def reverseWord(s):
return ' '.join([x[-1::-1] for x in s.split()])
^_^ (Sorry Python is not good for alg. demonstration but good for solution)
In C++:
if we can use strtok lib function, then we get each word from the string.
next for each word do the reverse
Is it good? waiting for comments.
letter
【在 g********r 的大作中提到】 : 大牛来指点一下代码有没有改进的地方? : 方法的就是从string tail开始一个一个的读 : string reverseWord(string s) : { : string result; : int i=s.size()-1; //start from the last character : while(i>=0){ : while(i>=0 && isspace(s[i])) i--; //advance i to a non-space letter : int j=i-1; : while(j>=0 && !isspace(s[j])) j--; //find the previous space
|
b******g 发帖数: 3616 | 5 我觉得这题的本意就是让你进行字符操作来逆转顺序,属于细节实现题。如果用现成的
库函数做,那基本就和反转linked list题你不操作指针,翻转node里的value差不多了。
【在 f***c 的大作中提到】 : In Python: : def reverseWord(s): : return ' '.join([x[-1::-1] for x in s.split()]) : ^_^ (Sorry Python is not good for alg. demonstration but good for solution) : In C++: : if we can use strtok lib function, then we get each word from the string. : next for each word do the reverse : Is it good? waiting for comments. : : letter
|
s**x 发帖数: 7506 | 6
了。
Right . 都是零分,
【在 b******g 的大作中提到】 : 我觉得这题的本意就是让你进行字符操作来逆转顺序,属于细节实现题。如果用现成的 : 库函数做,那基本就和反转linked list题你不操作指针,翻转node里的value差不多了。
|
p***r 发帖数: 1098 | 7 这个题的要求in place reversing吧,不能用extra memory。 |
f****g 发帖数: 207 | 8 这题先写reverse string函数, 吃两个pointer
你对着一个句子先做一次,
然后对着每个单词再做一次
希望有帮助 |
f********c 发帖数: 147 | 9 Java的话怎么in place啊?StringBuffer也不能用?String is immutable in Java...
【在 p***r 的大作中提到】 : 这个题的要求in place reversing吧,不能用extra memory。
|
f***c 发帖数: 338 | 10 op的帖子没有别的其它说明.
还有标点符号,或者连续多于一个的空格的情况[俺的code对这个情况没有处理,简单
试了一个,seg错误],俺的解法只对 “正常” 的输入有效。
这里的s要不要处理内存(in main)?
请专家指正。谢谢!
=============================================
给定 s = "Hello World"
要求这样 ==> "dlroW olleH"
直接swap s[i] 和 s[n-i-1] 只要 i < n - i - (2*i+1 < n)
这个简单,甚至都不要界定word,space也跟着swap了
不过题目既然叫word in string,应该这不是要的解
否则直接call下面的函数就可以了,reverseCall(s,0,s.size)
还是这样 ==> "olleH dlroW"
using namespace std;
void reverseWord(string &s, size_t start, size_t end) {
size_t i = 0;
char x;
while(i+i < end-start) { //equal to start+i < end-i
x = s[start+i];
s[start+i] = s[end-i];
s[end-i] = x; //better if swap is allowed to call
++i;
}
}
void reverse(string &s) {
size_t slen = s.size();
if (2 > slen) return; //for 1 or 0 char string
size_t i = 0, start = 0;
for(i = 0; i < slen; ++i) {
if (' ' == s[i] || i == slen-1) { //end of the word
if( i == slen - 1) reverseWord(s, start, i);
else reverseWord(s,start,i-1);
start = i + 1;//new start index
}
}
}
int main(int argc, char *argv[]) {
string s;
cout << "Please enter the string: ";
getline(cin, s);
reverse(s);
cout << "The reversed is: " << s << endl;
return 0;
}
Please enter the string: abc DEF
The reversed is: cba FED
Please enter the string: HELLO World
The reversed is: OLLEH dlroW
【在 p***r 的大作中提到】 : 这个题的要求in place reversing吧,不能用extra memory。
|
|
|
b******g 发帖数: 3616 | 11 这题没要求in place,新出的II有这个要求,但多了个条件就是首尾没有空格。虽然我
觉得首位有空格也能in place。in place主要就是靠两遍反转:第一个pass先反转整个
string,这样每个word的位置是对了,但每个word本身的字符顺序是反的;第二个pass
逐个反转每个word的字符。
【在 p***r 的大作中提到】 : 这个题的要求in place reversing吧,不能用extra memory。
|
f********c 发帖数: 147 | 12 请问哪里有新出的II?Leetcode没看到啊
pass
【在 b******g 的大作中提到】 : 这题没要求in place,新出的II有这个要求,但多了个条件就是首尾没有空格。虽然我 : 觉得首位有空格也能in place。in place主要就是靠两遍反转:第一个pass先反转整个 : string,这样每个word的位置是对了,但每个word本身的字符顺序是反的;第二个pass : 逐个反转每个word的字符。
|
g********r 发帖数: 89 | 13 上Leetcode上看了一下,发现这题还有solution。
"One simple approach is a two-pass solution: First pass to split the string
by spaces into an array of words, then second pass to extract the words in
reversed order.
We can do better in one-pass. While iterating the string in reverse order,
we keep track of a word’s begin and end position. When we are at the
beginning of a word, we append it."
我的方法就是leetcode solution说的"one-pass" solution啊。时间复杂度是O(n), 空
间复杂度也是O(n).
大牛不妨说说更好的方法?
inplace reverse两边的话,不知道怎么处理中间的space?erase掉的话会不会很浪费
时间?
【在 s**x 的大作中提到】 : 你的方法彻头彻尾没有一点点对的地方,从函数signature 到思路。 : 这是个很古老的题了,为什么不先Google 一下呢?cc150 上好像就有这题。你这种刷 : 题方法可能效果是反的。 : : letter : ★ 发自iPhone App: ChineseWeb 8.7
|
g********r 发帖数: 89 | 14 extra space怎么处理呢?
【在 f****g 的大作中提到】 : 这题先写reverse string函数, 吃两个pointer : 你对着一个句子先做一次, : 然后对着每个单词再做一次 : 希望有帮助
|
L***s 发帖数: 1148 | 15 # non-idiomatic python code
# just to illustrate the algorithm clearer
def swap_chars(s, iBgn, iEnd):
""" Reverse chars in buffer s ranging from iBgn to iEnd (exclusive).
"""
for i in range(iBgn, (iBgn+iEnd)//2):
j = iBgn + iEnd - i - 1
s[i], s[j] = s[j], s[i]
def reverse_words_inplace(s):
""" Reverse all words in a sentence in-place.
E.g. 'this is simple' -> 'simple is this'
"""
n = len(s)
# First pass, char-level reversal in the sentence
swap_chars(s, 0, n)
# Second pass, char-level reversal in each word
i, j = 0, 1
while j < n:
if s[j] == ' ':
swap_chars(s, i, j)
i = j + 1
j += 2
else:
j += 1
swap_chars(s, i, n) # last word
# Test
if __name__ == '__main__':
s = list('this is simple')
reverse_words_inplace(s)
print(''.join(s)) # simple is this
s = list('a bc cdf')
reverse_words_inplace(s) # cdf bc a
print(''.join(s))
s = list('a b c')
reverse_words_inplace(s)
print(''.join(s)) # c b a
【在 f***c 的大作中提到】 : In Python: : def reverseWord(s): : return ' '.join([x[-1::-1] for x in s.split()]) : ^_^ (Sorry Python is not good for alg. demonstration but good for solution) : In C++: : if we can use strtok lib function, then we get each word from the string. : next for each word do the reverse : Is it good? waiting for comments. : : letter
|
b*****i 发帖数: 76 | 16 我来添个乱
JavaScript 1-liner:
('abc def ghi').split('').reverse().join('').split(' ').reverse().join(' ')
//"cba fed ihg" |