f*********l
发帖数: 46 | 1 reverse string的变种。 只reverse word不reverse punctuation。比如 "this,,,is.
a word" -> "word,,,a.is this" |
j**********3
发帖数: 3211 | |
d******e
发帖数: 2265 | 3 split成两个list. reverse word list, merge.
is.
【在 f*********l 的大作中提到】
: reverse string的变种。 只reverse word不reverse punctuation。比如 "this,,,is.
: a word" -> "word,,,a.is this"
|
l*****a
发帖数: 14598 | 4 如果转成list的话,一个就够了
头尾两个index,swap string only and skip symbols
【在 d******e 的大作中提到】
: split成两个list. reverse word list, merge.
:
: is.
|
d******e
发帖数: 2265 | 5 这是c时代的做法。现在string都是immutable的。总之还要在复制出去，在复制回来。
不差那点代价了。
这题一般来说，不应该考。以前c程序用指针是重要技巧。现在基本没人用了。
【在 l*****a 的大作中提到】
: 如果转成list的话,一个就够了
: 头尾两个index,swap string only and skip symbols
|
l*****a
发帖数: 14598 | 6 sorry , what I said is index of the list,not pointer
那你merge怎么考虑顺序呢
上code吧
【在 d******e 的大作中提到】
: 这是c时代的做法。现在string都是immutable的。总之还要在复制出去，在复制回来。
: 不差那点代价了。
: 这题一般来说，不应该考。以前c程序用指针是重要技巧。现在基本没人用了。
|
f*********l
发帖数: 46 | 7 大牛可以给个code吗？一直没写出来，谢谢！
【在 l*****a 的大作中提到】
: 如果转成list的话,一个就够了
: 头尾两个index,swap string only and skip symbols
|
r**o
发帖数: 430 | |
l*****a
发帖数: 14598 | 9 弄到一个string list里,然后再生成结果也写不出来吗?
【在 f*********l 的大作中提到】
: 大牛可以给个code吗？一直没写出来，谢谢！
|
l*****a
发帖数: 14598 | 10 in place的话就得移来移去,很费时间..
【在 r**o 的大作中提到】
: O(N)原地没有办法解吧？
|
|
|
l******s
发帖数: 3045 | 11 双指针也可解,left找symbol，right找字符串，两个指针都扫描整个字符串。 |
f*********l
发帖数: 46 | 12 我是说in place的写不出来
【在 l*****a 的大作中提到】
: 弄到一个string list里,然后再生成结果也写不出来吗?
|
f*********l
发帖数: 46 | 13 写了一个用list的版本
public static String reverse(String s) {
List list = new ArrayList();
boolean word = Character.isLetter(s.charAt(0));
int i = 0, n = s.length(), start = 0;
while(i < n) {
char cur = s.charAt(i);
while(i < n && ((word&&Character.isLetter(cur)) || (!word&&
Character.isLetter(cur)))) {
++i;
}
list.add(s.substring(start, i));
start = i;
word = !word;
}
i = 0;
int j = list.size()-1;
while(i < j) {
if(!Character.isLetter(list.get(i).charAt(0))) {
++i;
continue;
}
if(!Character.isLetter(list.get(j).charAt(0))) {
--j;
continue;
}
String tmp = list.get(i);
list.set(i, list.get(j));
list.set(j, tmp);
++i;
--j;
}
StringBuilder res = new StringBuilder();
for(String e : list) res.append(e);
return res.toString();
} |
r**o
发帖数: 430 | 14 不是原地的话这题还有啥point，我大可再弄个buffer然后原来string两头扫放进去不
就行了。。 |
d******e
发帖数: 2265 | 15 如果是split到list.那么就是看regex split出两个还是一个lis的问题了。
如果split到一个list,if isword, 指针交换，
如果split到两个lists, merge splited word和 splitters.
python的话，
>>> re.split('(W+)', 'this,,,is.a word')
['this', ',,,', 'is', '.', 'a', ' ', 'word']
剩下的没有什么难度了。
【在 l*****a 的大作中提到】
: sorry , what I said is index of the list,not pointer
: 那你merge怎么考虑顺序呢
: 上code吧
|
u**l
发帖数: 35 | 16 c/c++的code好像不受欢迎：
#include
#include
using namespace std;
char* GetAlphabet(char* str) {
while ('\0' != *str && !((*str >= 'a' && *str <= 'z') || (*str >= 'A' &&
*str <= 'Z'))) {
++str;
}
return str;
}
char* GetOthers(char* str) {
while ((*str >= 'a' && *str <= 'z') || (*str >= 'A' && *str <= 'Z')) {
++str;
}
return str;
}
void Reverse(char* s, char* e) {
while (s < e) {
char c1 = *s;
char c2 = *e;
*s = c2;
*e = c1;
++s;
--e;
}
}
void Reverse(char* str) {
char* s = GetAlphabet(str);
while ('\0' != *s) {
char* e = GetOthers(s);
Reverse(s, e - 1);
s = GetAlphabet(e);
}
Reverse(str, s - 1);
}
int main() {
string str = "this,,,is.a word";
Reverse(const_cast(str.c_str()));
cout << str << endl;
return 0;
} |
d******e
发帖数: 2265 | 17 string你不可能写inplace的。
要是非要上效率的。就是两个指针，从尾部读word,从头部读sperator.
char[] char_arr = new char[len(s)];
int i = len(s) -1;
int j = 0;
// read word from end and save to char_arr
while (i > -1 && j < len(s)){
// read word from end and save to char_arr reverse
// read separtor from begin and save to char_arr
}
return new StringBuilder(char_arr).toString()
【在 f*********l 的大作中提到】
: 我是说in place的写不出来
|
l*****a
发帖数: 14598 | 18 我们都知道java的string 是immutable的
我们就是用string.toCharArray()转成字符数组...
【在 d******e 的大作中提到】
: string你不可能写inplace的。
: 要是非要上效率的。就是两个指针，从尾部读word,从头部读sperator.
: char[] char_arr = new char[len(s)];
: int i = len(s) -1;
: int j = 0;
: // read word from end and save to char_arr
: while (i > -1 && j < len(s)){
: // read word from end and save to char_arr reverse
: // read separtor from begin and save to char_arr
: }
|
l******s
发帖数: 3045 | 19 C# Solution. Tested. 2-Pointer in space O(n) time
private string reverse(string s){
StringBuilder result = new StringBuilder();
for (int left = 0, right = s.Length - 1; left < s.Length || right >= 0;){
while (left < s.Length && !char.IsLetter(s[left]))
result.Append(s[left++]);
while (right >= 0 && !char.IsLetter(s[right]))
right--;
int newRight = right;
while (newRight > 0 && char.IsLetter(s[newRight - 1]))
newRight--;
if (newRight >= 0){
result.Append(s.Substring(newRight, right - newRight + 1));
right = newRight - 1;
}
while (left < s.Length && char.IsLetter(s[left]))
left++;
}
return result.ToString();
}
【在 l******s 的大作中提到】
: 双指针也可解,left找symbol，right找字符串，两个指针都扫描整个字符串。
|
l*****a
发帖数: 14598 | 20 你这个work???
第一遍单词保持原状,然后整个reverse
现在你的单词是reversed的吧? punction的位置似乎也不符合要求
【在 u**l 的大作中提到】
: c/c++的code好像不受欢迎：
: #include
: #include
: using namespace std;
: char* GetAlphabet(char* str) {
: while ('\0' != *str && !((*str >= 'a' && *str <= 'z') || (*str >= 'A' &&
: *str <= 'Z'))) {
: ++str;
: }
: return str;
|
d******e
发帖数: 2265 | 21 我写的那段是不要 call tocharAarry
思路是allocate一块空间，然后从原来的string上读，然后交叉取词和sperators
merge入新的char array.
【在 l*****a 的大作中提到】
: 我们都知道java的string 是immutable的
: 我们就是用string.toCharArray()转成字符数组...
|
w**z
发帖数: 8232 | 22 写code都不加comments？看别人code，猜别人思路太费神。
【在 l*****a 的大作中提到】
: 你这个work???
: 第一遍单词保持原状,然后整个reverse
: 现在你的单词是reversed的吧? punction的位置似乎也不符合要求
|
