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" |
