打印

面试算法题

[复制链接]
1134|5
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
dfsa|  楼主 | 2013-8-28 19:05 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
去面试,这道题没答上来,百思不得其解,求大牛给讲讲,郁闷中。

题目如下:
   大概是这么个意思。要求解析一个string,但是这个string里边包含很多特殊意义的字符,比如%,#这一类的字符,当解析到这类字符的时候,就要去一个map中去查询它对应的字符串,比如 %对应 “haha”, #对应“xixi”,然后将解析出来的字符串替换原来的字符串。
   难度在于,查询map出来的字符串也可能包含特殊字符,这样就有可能导致死循环,比如 % 查询出来 haha#,
   查#, 又查到“xixi%”, 这样就会出现死循环?更复杂一点,当替换层数很深的时候,在每一层都有可能出现死循环,所以没法用递归吧?

相关帖子

沙发
无冕之王| | 2013-8-28 19:20 | 只看该作者
只有一个符号扩展了自身的时候才会死循环
那么扩展的时候存放一个状态,表示每一个符号是否已经被展开过。如果被展开过的符号还需要再展开那就丢死循环的错误。否则就能有限次结束。

使用特权

评论回复
板凳
baidudz| | 2013-8-28 19:58 | 只看该作者
面试题目本身要求逐个层次替换吗?这个应该问清楚啊,如果只需要一次替换,就不用管死循环的问题了,设计算法的时候保证不对已经替换完成的串再操作就可以了。如果需要逐个层次替换,那这种死循环就是无限扩展了,不合理逻辑。

使用特权

评论回复
地板
秋天落叶| | 2013-8-28 20:02 | 只看该作者
这个题目就要是考虑多层替换啊,如果只替换一次,那没有什么难度,难就难在不停的替换下去,是否会出现死循环,这个题目就是要求检查是否能出现死循环,没有死循环的话,把替换结果给出来。

使用特权

评论回复
5
火箭球迷| | 2013-8-30 19:12 | 只看该作者
这个是什么公司的面试题

使用特权

评论回复
6
txcy| | 2013-8-31 09:30 | 只看该作者
没太看懂这都算法题

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

282

主题

2404

帖子

2

粉丝