V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
13m
V2EX  ›  问与答

一个面试题求解决思路

  •  
  •   13m · 2013-04-28 13:44:23 +08:00 · 3651 次点击
    这是一个创建于 4212 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给出字串:
    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
        1
    ivanlw  
       2013-04-28 13:58:55 +08:00
    插入的地方的前后内容不可以直接判断吗?
    13m
        2
    13m  
    OP
       2013-04-28 14:11:31 +08:00
    @ivanlw 随机插入即可
    Cadina
        3
    Cadina  
       2013-04-28 14:15:35 +08:00
    先遍历一遍字符串,记录下可以插入的点,然后从这些点中随机选一个。
    我记得有个未知长度流中随机选取的算法,可以用来优化空间复杂度。
    13m
        4
    13m  
    OP
       2013-04-28 14:22:59 +08:00
    @Cadina 谢谢,但这个方法每次都要遍历一遍所有内容,生成一个可插入点的数组,再随机。。
    有没更好的办法
    bitsmix
        5
    bitsmix  
       2013-04-28 14:31:54 +08:00   ❤️ 1
    split(/\s/) .
    lookhi
        6
    lookhi  
       2013-04-28 14:38:16 +08:00   ❤️ 1
    直接随即个地址,再检查能否插入。成功率还是很高的。
    13m
        7
    13m  
    OP
       2013-04-28 14:45:44 +08:00
    @bitsmix 这个思路非常棒!感谢!
    oldcai
        8
    oldcai  
       2013-04-28 14:46:47 +08:00   ❤️ 1
    1.随机一个字符串长度内的数字赋值给index,检查这个index位置的字符和index+1的字符是否为空格;
    2.如果有空格,就记录这个随机数index到一个集合set,随机另外的index数值,并确保这个index不再set之中出现过,将此index带入1,重复第一步到重复次数==字符串长度;
    3.没有空格,就在index后面插入;重复次数==字符串长度,则报错或者什么的,反正就是没地方可以插了。
    Cadina
        9
    Cadina  
       2013-04-28 14:49:59 +08:00   ❤️ 1
    @13m 我后面说的优化方法就是为了解决这个问题的。。。
    @lookhi 在工程上这种方法还挺常见的,前提是空格和换行比较少
    13m
        10
    13m  
    OP
       2013-04-28 14:50:56 +08:00
    @oldcai 谢谢。。是可以解决,但如果这么答这个题一定会被毙的。。。
    astnd
        11
    astnd  
       2013-04-28 14:52:44 +08:00   ❤️ 1
    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
        12
    13m  
    OP
       2013-04-28 14:55:59 +08:00
    @oldcai @astnd
    大概是实际生产环境这种做法可以避免长内容遍历的消耗,也是很不错的方法!感谢!
    Cadina
        13
    Cadina  
       2013-04-28 14:58:27 +08:00
    @13m 不能避免遍历,不遍历是不知道length的
    13m
        14
    13m  
    OP
       2013-04-28 15:00:18 +08:00
    @Cadina 我觉得作为面试题应该在语言代码上写的尽量精简,思路明确,不能为了追求效率而代码冗长
    Cadina
        15
    Cadina  
       2013-04-28 15:01:27 +08:00   ❤️ 1
    LZ可以google一下“蓄水池抽样”这个问题,解法是类似的
    touch
        16
    touch  
       2013-04-28 15:29:17 +08:00
    在已经知道字符串情况下插入的话 没什么要求直接replace。
    Mutoo
        17
    Mutoo  
       2013-04-28 17:26:24 +08:00   ❤️ 1
    给你一种思路找可以找到所有可以插入的位置(使用正则)

    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
        18
    oldcai  
       2013-04-28 18:12:09 +08:00   ❤️ 1
    @Cadina
    一般来说,除了C里面的那种字符指针表示方法,其他地方的字符串都是封装的类,会有长度计数的,不会每次都算长度就遍历一次。

    @bitsmix
    @13m
    额,感觉也蛮简单的,你真正按split(/\s/)实现出来,有两个随机过程——随机选择一个长度大于1串,还有串内随机,最后还要join起来,同时还有个bug,某两个字符串中间有两个空格,最后join后就跟原串不一样了。
    luikore
        19
    luikore  
       2013-04-28 21:34:33 +08:00   ❤️ 1
    ruby 版完整代码 (这种问题正则里直接用非词界 \B 就可以):

    s = "wkjkjd fsk fsdjk
    bbb sss fasdf"
    pos = rand s.scan(/\B/).count # 计算插入位置
    s.gsub(/\B/){
    pos -= 1
    pos == -1 ? 'a' : ''
    }
    13m
        20
    13m  
    OP
       2013-04-28 21:38:14 +08:00
    @oldcai 的确是会有这个BUG,谢谢提醒!

    如果就效率考虑,可能最优的办法就是随机一个位置然后判断该位置前后是否符合条件然后进行插入了
    oldcai
        21
    oldcai  
       2013-04-28 21:44:18 +08:00
    @13m 这不是随机的,这样的话,有空格在近处的字符位置被插入字符的概率会变大。
    oldcai
        22
    oldcai  
       2013-04-28 21:44:42 +08:00
    @oldcai 纠正,这是随机的,但不是均衡概率的。
    tioover
        23
    tioover  
       2013-04-28 21:47:47 +08:00 via Android
    随机index 判断,不行的话再随机一个index。简单粗暴,不过最坏运行时间是无穷233
    ipconfiger
        24
    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
        25
    bitsmix  
       2013-04-29 02:27:02 +08:00 via iPhone
    @oldcai 楼主说了,求「思路」
    ipconfiger
        26
    ipconfiger  
       2013-04-29 02:31:21 +08:00   ❤️ 1
    DeeCheung
        27
    DeeCheung  
       2013-04-29 04:09:17 +08:00   ❤️ 1
    '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
        28
    DeeCheung  
       2013-04-29 04:12:42 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2849 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 02:12 · PVG 10:12 · LAX 18:12 · JFK 21:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.