c****8
发帖数: 76 | 1 大家好，reverse string: abcd --> dcba. 其实方法很简单，就是two pointers，一
个从头开始扫，一个从尾开始扫，然后swap就行。复杂度为：O(n)。但被问及是否可以
做到O(logn)，我怎么想也没有想出O(logn)的方法，就算是divide and conquer 或者
类似 binary search的方法，最后的复杂度也是O(n)。因为递推公式是：T(n)=2T(n/2)
+1。
想问问大家有没有O(logn)的算法？谢啦。 |
x**********g
发帖数: 44 | |
l****h
发帖数: 1189 | 3 题目是你的具体例子还是泛指reverse任意长的string? |
s**x
发帖数: 7506 | 4 这么明显的最优也得O(n)的问题还在找更优解法。 |
n******n
发帖数: 12088 | 5 问是否有？回答没有不就可以了？
2)
【在 c****8 的大作中提到】
: 大家好，reverse string: abcd --> dcba. 其实方法很简单，就是two pointers，一
: 个从头开始扫，一个从尾开始扫，然后swap就行。复杂度为：O(n)。但被问及是否可以
: 做到O(logn)，我怎么想也没有想出O(logn)的方法，就算是divide and conquer 或者
: 类似 binary search的方法，最后的复杂度也是O(n)。因为递推公式是：T(n)=2T(n/2)
: +1。
: 想问问大家有没有O(logn)的算法？谢啦。
|
c****8
发帖数: 76 | 6 泛指任意长度的string
【在 l****h 的大作中提到】
: 题目是你的具体例子还是泛指reverse任意长的string?
|
c****8
发帖数: 76 | 7 我是觉得没有，我跟他说没有。他说再想想。最后我其实答了divide and conquer，因
为我实在想不到O(logn)的方法，最后他居然满意了。但是divide and conquer是O(n)
啊。
【在 n******n 的大作中提到】
: 问是否有？回答没有不就可以了？
:
: 2)
|
