【第三轮】6.16-6.22 CareerCup 1.2

【解题思路】use python way
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】
https://gist.github.com/tangxukai/b93f4e6a33c92643bbcd
【test case

【解题思路】
//a routine way
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329

【解题思路】
声明一个临时变量，把数组的元素前后对应位置交换赋值即可
【时间复杂度】

【空间复杂度】

【gist link】
https://gist.github.com/daf91c24b6cb2cdbba5e.git

【解题思路】
java，转换为数组，然后前后一起往中间move，swap。或者直接用StringBuilder，for loop逆转。
【时间复杂度】
O(n)
【空间复杂度】
O(1)/O(n)
【gist link】https://gist.github.com/UncleGarden/85509dad7178cde74c50

【解题思路】
two pointers indicating characters to be swapped, traversing from front and end of the string respectively.
first use a C style index, then improved with C++ style iterator.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/0b07ee098f3a7e0c1889
【test case】
N/A

写完了此题，翻了翻博客，这篇博客写的很赞：http://www.cnblogs.com/kirinboy/ ... verse-a-string.html

基本上列出了所有的方法~没想到StringBuffer是最快捷的~

solution 1
covert the input string to the StringBuffer and fast use the reverse() method to reverse it, finally, convert back to String type.

solution 2
1. Covert the string into a char[]
2. Two pointers which point to the head and tail(not ‘\0′, but the one before it) elements of the char[]
3. swap the value of the two nodes
Time Complexity: O(n)
Space Complexity: O(n)

Solution3
using Recursion to solve this problem

Link is here: http://www.jyuan92.com/post-270

【解题思路】
Use two pointers: one pointing to head, and the other pointing
to tail. Move the pointers towards each other and swap the two
values step by step.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoshuaTang/c0ec657385a93265c8ed

fang_wu 发表于 2014-6-17 17:48
【解题思路】java实现，先把string转换为char数组，然后跟二分法一样，维持left和right两个。一个++，一个- ...

使用了额外的数组不能算是O(1)空间复杂度吧

pyemma 发表于 2014-7-5 15:15
使用了额外的数组不能算是O(1)空间复杂度吧

额，是的，感谢哈