一个面试题求解决思路

[13m]

给出字串：
wkjkjd fsk fsdjk
bbb sss fasdf

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

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

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

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

谢谢！

[ivanlw]

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

[13m]

@ivanlw 随机插入即可

[Cadina]

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

[13m]

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

[bitsmix]

split(/\s/) .

[lookhi]

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

[13m]

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

[oldcai]

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

[Cadina]

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

[13m]

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

[astnd]

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]

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

[Cadina]

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

[13m]

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

[Cadina]

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

[touch]

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

[Mutoo]

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

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]

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

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

[luikore]

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

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

[13m]

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

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