一个面试题求解决思路

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4264 天前的主题，其中的信息可能已经有所发展或是发生改变。

给出字串：
wkjkjd fsk fsdjk
bbb sss fasdf

两行随机的英文字母，每行中间有空格

现在需要随机插入一个字母a，要求a必须插入两个字母中间，
例如：babb或者bbab
不能出现：abbb或者bbba

也就是判断插入a的前后是否为换行，空格或者行末

怎样最简单的实现该需求？
用js或者伪码写均可

谢谢！

第 1 条附言 · 2013-04-28 14:46:46 +08:00

感谢 @bitsmix 提供思路： split(/\s/) .
期待能有更好的方案

插入

或者

空格

28 条回复 • 1970-01-01 08:00:00 +08:00

ivanlw

2013-04-28 13:58:55 +08:00

插入的地方的前后内容不可以直接判断吗？

13m

2013-04-28 14:11:31 +08:00

@ivanlw 随机插入即可

Cadina

2013-04-28 14:15:35 +08:00

先遍历一遍字符串，记录下可以插入的点，然后从这些点中随机选一个。
我记得有个未知长度流中随机选取的算法，可以用来优化空间复杂度。

13m

2013-04-28 14:22:59 +08:00

@Cadina 谢谢，但这个方法每次都要遍历一遍所有内容，生成一个可插入点的数组，再随机。。
有没更好的办法

bitsmix

2013-04-28 14:31:54 +08:00

split(/\s/) .

lookhi

2013-04-28 14:38:16 +08:00

直接随即个地址，再检查能否插入。成功率还是很高的。

13m

2013-04-28 14:45:44 +08:00

@bitsmix 这个思路非常棒！感谢！

oldcai

2013-04-28 14:46:47 +08:00

1.随机一个字符串长度内的数字赋值给index，检查这个index位置的字符和index+1的字符是否为空格;
2.如果有空格，就记录这个随机数index到一个集合set，随机另外的index数值，并确保这个index不再set之中出现过，将此index带入1，重复第一步到重复次数==字符串长度;
3.没有空格，就在index后面插入;重复次数==字符串长度，则报错或者什么的，反正就是没地方可以插了。

Cadina

2013-04-28 14:49:59 +08:00

@13m 我后面说的优化方法就是为了解决这个问题的。。。
@lookhi 在工程上这种方法还挺常见的，前提是空格和换行比较少

13m

2013-04-28 14:50:56 +08:00

@oldcai 谢谢。。是可以解决，但如果这么答这个题一定会被毙的。。。

astnd

2013-04-28 14:52:44 +08:00

1 随机Index 判断index和index+1中有没有空格
2 若无插入程序返回
3 若index是空格 index+1也是空格将从index-1 index index+1 index+2排除重复1
4 若index是空格将从index-1 index index+1排除重复1
5 若index是空格将从index index+1 index+2排除重复1

大概是这样

13m

2013-04-28 14:55:59 +08:00

@oldcai @astnd
大概是实际生产环境这种做法可以避免长内容遍历的消耗，也是很不错的方法！感谢！

Cadina

2013-04-28 14:58:27 +08:00

@13m 不能避免遍历，不遍历是不知道length的

13m

2013-04-28 15:00:18 +08:00

@Cadina 我觉得作为面试题应该在语言代码上写的尽量精简，思路明确，不能为了追求效率而代码冗长

Cadina

2013-04-28 15:01:27 +08:00

LZ可以google一下“蓄水池抽样”这个问题，解法是类似的

touch

2013-04-28 15:29:17 +08:00

在已经知道字符串情况下插入的话没什么要求直接replace。

Mutoo

2013-04-28 17:26:24 +08:00

给你一种思路找可以找到所有可以插入的位置（使用正则）

var str = "wkjkjd fsk fsdjk\nbbb sss fasdf";

var reg = new RegExp(/\w(?=\w)/g);

reg.exec(str); // 搜索下一个可插入的位置
reg.lastIndex+1; // 可插入的位置

（可以不断重复）

reg.exec(str); // 搜索下一个可插入的位置
reg.lastIndex+1; // 可插入的位置

参考资料 http://www.w3school.com.cn/js/jsref_exec_regexp.asp

至少你想在什么时候插入，可以用随机函数决定

oldcai

2013-04-28 18:12:09 +08:00

@Cadina
一般来说，除了C里面的那种字符指针表示方法，其他地方的字符串都是封装的类，会有长度计数的，不会每次都算长度就遍历一次。

@bitsmix
@13m
额，感觉也蛮简单的，你真正按split(/\s/)实现出来，有两个随机过程——随机选择一个长度大于1串，还有串内随机，最后还要join起来，同时还有个bug，某两个字符串中间有两个空格，最后join后就跟原串不一样了。

luikore

2013-04-28 21:34:33 +08:00

ruby 版完整代码 (这种问题正则里直接用非词界 \B 就可以):

s = "wkjkjd fsk fsdjk
bbb sss fasdf"
pos = rand s.scan(/\B/).count # 计算插入位置
s.gsub(/\B/){
pos -= 1
pos == -1 ? 'a' : ''
}

13m

2013-04-28 21:38:14 +08:00

@oldcai 的确是会有这个BUG,谢谢提醒！

如果就效率考虑，可能最优的办法就是随机一个位置然后判断该位置前后是否符合条件然后进行插入了

oldcai

2013-04-28 21:44:18 +08:00

@13m 这不是随机的，这样的话，有空格在近处的字符位置被插入字符的概率会变大。

oldcai

2013-04-28 21:44:42 +08:00

@oldcai 纠正，这是随机的，但不是均衡概率的。

tioover

2013-04-28 21:47:47 +08:00 via Android

随机index 判断，不行的话再随机一个index。简单粗暴，不过最坏运行时间是无穷233

ipconfiger

2013-04-29 02:27:01 +08:00

import random

s = "wkjkjd fsk fsdjk bbb sss fasdf"

def insert(s):
if not s:
return "a"
idx = random.randint(0,len(s)-1)
return "".join([s[0:idx],"a",s[idx:len(s)]])

result = " ".join(["".join([word[0],insert(word[1:-1]),word[-1]]) for word in s.split()])

bitsmix

2013-04-29 02:27:02 +08:00 via iPhone

@oldcai 楼主说了，求「思路」

ipconfiger

2013-04-29 02:31:21 +08:00

@13m https://gist.github.com/ipconfiger/062836b91407e13f98b8

DeeCheung

2013-04-29 04:09:17 +08:00

'wkjkjd fsk fsdjk\nbbb sss fasdf'.replace(/(bbb|sss)(\s)?/g, function(match, p1, p2){
var min = 1,
max = p1.length - 1,
pos = Math.floor(Math.random() * (max - min + 1)) + min; //ranint
return p1.substr(0, pos) + 'a' + p1.substr(pos, p1.length - 1) + p2;
});

DeeCheung

2013-04-29 04:12:42 +08:00

https://gist.github.com/DC3/5478249