l********h
发帖数: 130 | 1 最最经典和简单的一个java面试题，要求占用最少的内存和最好的算反。
我能想出至少3种方法，但是不知道那种最好。
Reverse words in a string. Example: AA BBB cccc -> cccc BBB AA
不允许用java.util
我知道的：
1）String.Split
2) Pattern
3）StringBuffer.reverse
请大牛问问有啥最好的算法并前占用最少的内存 |
l********h
发帖数: 130 | |
i**********e
发帖数: 1145 | 3 The idea is simple but subtle. This trick is discussed in Programming Pearls.
Reverse the entire string.
Then reverse the characters for each individual word.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
j*****u
发帖数: 1133 | 4 不了解Java，在.NET里，string是immutable的，也就意味着除非传入的parameter是
StringBuilder，return之前至少要copy一次
如果你用了string.Split然后再reverse，construct new string至少memory copy了2次
StringBuilder/StringBuffer做in-place reverse(i.e. reverse whole string then
reverse each word)，memory只copy了1次
假设StringBuilder/StringBuffer的ToString都没有allocate new memory |
l********h
发帖数: 130 | 5 对不起，我没有说明白。
以上3步是3中不同的解法，不是按顺序的。任何一种方法都可以直接reverse.我只是列
出了我知道的几种方法。 |
j*****u
发帖数: 1133 | 6 I think lz asks the string operations in Java, which is different with C/C++
since Java/.NET string is immutable - means mem copy cannot be avoided
anyway.
Pearls.
【在 i**********e 的大作中提到】
: The idea is simple but subtle. This trick is discussed in Programming Pearls.
: Reverse the entire string.
: Then reverse the characters for each individual word.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
h******3
发帖数: 351 | 7 IDK how pattern is implementted.
1) String.split copy each substring to temporary buffer, deal with each one,
copy all of them back to one string.
2) the implementation of StringBuffer.reverse might be as efficient as the
solution mentioned in PIE. The only question is that we might not be able to
use it when interviewed.
【在 l********h 的大作中提到】
: 最最经典和简单的一个java面试题，要求占用最少的内存和最好的算反。
: 我能想出至少3种方法，但是不知道那种最好。
: Reverse words in a string. Example: AA BBB cccc -> cccc BBB AA
: 不允许用java.util
: 我知道的：
: 1）String.Split
: 2) Pattern
: 3）StringBuffer.reverse
: 请大牛问问有啥最好的算法并前占用最少的内存
|
c********t
发帖数: 5706 | 8 re这个，我选StringBuilder.reverse
2次
then
【在 j*****u 的大作中提到】
: 不了解Java，在.NET里，string是immutable的，也就意味着除非传入的parameter是
: StringBuilder，return之前至少要copy一次
: 如果你用了string.Split然后再reverse，construct new string至少memory copy了2次
: StringBuilder/StringBuffer做in-place reverse(i.e. reverse whole string then
: reverse each word)，memory只copy了1次
: 假设StringBuilder/StringBuffer的ToString都没有allocate new memory
|
|
s****3
发帖数: 257 | |
c********t
发帖数: 5706 | 10 In this case, do you think creating a character array and using split
reverse will be the best answer? complexity n/2?
For LZ's case, because the question only required no java.util, I think he
might be able to use StringBuilder/StringBuffer.
one,
to
【在 h******3 的大作中提到】
: IDK how pattern is implementted.
: 1) String.split copy each substring to temporary buffer, deal with each one,
: copy all of them back to one string.
: 2) the implementation of StringBuffer.reverse might be as efficient as the
: solution mentioned in PIE. The only question is that we might not be able to
: use it when interviewed.
|
