一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 456|回复: 4
收起左侧

[字符串] 删除和复制特定字符

[复制链接] |试试Instant~ |关注本帖
OracleDesire 发表于 2013-12-20 16:44:10 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给一个大小为n的字符数组,保存着一个字符串以'\0'结尾。这个n可能大于字符串长度,也就是说字符串后面还有一些可用空间。
现在要求删除所有的'#',并且如果里面有'$',那么就将其变为'$$'。如果最后的长度大于n,则抛出异常。
要求in place完成。

例子:
"ab#c$d",n = 10
变为
"abc$$d"

想了好久没什么好想法,发上来求大神。
doveonthewing 发表于 2013-12-20 23:09:12 | 显示全部楼层
1. 遍历一遍 计算最后的长度n_1, 如果n_1>n 则抛出异常
2. 遍历一遍 in place删掉所有的#
3. 从右向左遍历 in place double所有的$

O(n) 不知道有没有常数优化

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| OracleDesire 发表于 2013-12-21 09:32:18 | 显示全部楼层

有几个地方不明白……如何in place删掉所有的#?
是删除后将后面的向前移动,还是就放着不动了?
double $的时候,附近的空位不够如何做?

谢谢
回复 支持 反对

使用道具 举报

doveonthewing 发表于 2013-12-21 10:07:15 | 显示全部楼层
OracleDesire 发表于 2013-12-21 09:32
有几个地方不明白……如何in place删掉所有的#?
是删除后将后面的向前移动,还是就放着不动了?
doubl ...

(1) 删除后把后面的向前移动
(2) 你已经知道n_1了 所以不会不够
回复 支持 反对

使用道具 举报

 楼主| OracleDesire 发表于 2013-12-21 10:20:46 | 显示全部楼层
doveonthewing 发表于 2013-12-21 10:07
(1) 删除后把后面的向前移动
(2) 你已经知道n_1了 所以不会不够

这是一个方法,但是这个方法复杂度太高,删除过程中无效的移来移去太多了,很可能不是面试时好的答案。
不知道还有没有什么高见?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表