我先走一步去拯救地球 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

我先走一步去拯救地球

我先走一步去拯救地球# Joke - 肚皮舞运动

g*c2014-07-28 07:07

1 楼

求问一道pocket gems的面试题：
写一个mutable string。里面有三个methods, charAt(int i), substring(int
beginIndex, int endIndex), setcharAt(int i, char c); 只能是O（1） space
毫无头绪。。。这些不是c++ stl 自带的函数么。。。跪求指导。。。最好用c++
谢谢！

c*r2014-07-28 07:07

2 楼

g*c2014-07-28 07:07

3 楼

有人会吗？求指导～～～十分感激！

t*r2014-07-28 07:07

4 楼

楼主学过C么？

e*i2014-07-28 07:07

5 楼

具体实现可以去看C++STL的源码。如果面试有人考这个题目，应该礼貌的请出题人出去。
http://www.cplusplus.com/reference/string/string/at/
http://www.cplusplus.com/reference/string/string/substr/
http://www.cplusplus.com/reference/string/string/operator[]/

g*c2014-07-28 07:07

6 楼

只知道一些基本的。是malloc一个内存，然后用指针吗？这个string class里的变量是
指针和一个内存。因为要求O(1)的space，第一个method charat可以指针在O(1) time
and O(1) space 返回对应的char即可。
第二个method substring 怎么达到O(1) space的呢？返回reference？可是新建一个
class的instance来放这个substring还是要内存啊。
第三个method setcharAt(int i, char c) 就完全不知道了。连字符都改了，又要求O(
1)的space，这个新字符放到哪呢？我想原string是不能改的，因为会有别的instance
指向这个string。那这个新的char又怎么和原string组合成新string呢？
网上搜了一下有人提了一句用tree，我没明白。
还请高人指点！谢谢！

【在 t*********r 的大作中提到】

: 楼主学过C么？

g*c2014-07-28 07:07

7 楼

自己再顶一下～求指导～～～谢谢！

n*n2014-07-28 07:07

8 楼

找本入门书看看吧。少做这些没有清晰定义的面试题，浪费时间

【在 g*****c 的大作中提到】

: 自己再顶一下～求指导～～～谢谢！

l*u2014-07-28 07:07

9 楼

想复杂了?原string可以改吧，没个method可以in place动一个char

time

【在 g*****c 的大作中提到】

: 求问一道pocket gems的面试题：
: 写一个mutable string。里面有三个methods, charAt(int i), substring(int
: beginIndex, int endIndex), setcharAt(int i, char c); 只能是O（1） space
: 毫无头绪。。。这些不是c++ stl 自带的函数么。。。跪求指导。。。最好用c++
: 谢谢！