V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
gbin
V2EX  ›  算法

20180320 今日算法

  •  
  •   gbin · 2018-03-20 08:26:54 +08:00 via Android · 3218 次点击
    这是一个创建于 2201 天前的主题,其中的信息可能已经有所发展或是发生改变。
    Given a string containing only digits, restore it by returning all possible valid IP address combinations.

    For example:
    Given "25525511135",

    return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

    See https://leetcode.com/problems/restore-ip-addresses/

    PS: 希望有兴趣的小伙伴一起出题。
    11 条回复    2018-03-20 10:14:02 +08:00
    zjp
        1
    zjp  
       2018-03-20 08:44:39 +08:00 via Android
    换一种描述,在字符串里插入 3 个. 使之符合 IP 地址的规范
    每个.前的字符只能有 1-3 个,3 层循环的效率也还行
    lhx2008
        2
    lhx2008  
       2018-03-20 09:25:04 +08:00 via Android
    这个写出来惨不忍睹,用递归,下 123 位点一下,检查是不是符合 ip 规范,不符合终结。否则,继续递归,到第四次点的时候,检查是不是到尾部,是就加进答案,然后统一终止
    deadEgg
        3
    deadEgg  
       2018-03-20 09:29:06 +08:00
    递归做。

    每次取出 1-3 个字符,然后递归下去,跳出条件是取了四次或取出来的字符不符合 1-255。

    这个递归中存在部分重叠子问题。也许能改为动态规划
    deadEgg
        4
    deadEgg  
       2018-03-20 09:30:01 +08:00
    擦 被楼上抢先了
    deadEgg
        5
    deadEgg  
       2018-03-20 09:33:02 +08:00
    @deadEgg 更正,没有重叠子问题。想错了
    mooo
        6
    mooo  
       2018-03-20 09:39:18 +08:00
    检查可以组合成的 1-255 字符, 用生成的字符 组合成 ip 地址
    lhx2008
        7
    lhx2008  
       2018-03-20 09:55:58 +08:00 via Android
    @mooo 但是 ip 地址好像有 42 亿个
    mooo
        8
    mooo  
       2018-03-20 10:06:06 +08:00
    @lhx2008 四个区域 每个区域都是 1-255 的吧
    mooo
        9
    mooo  
       2018-03-20 10:06:32 +08:00
    @lhx2008 0-255
    mooo
        10
    mooo  
       2018-03-20 10:13:00 +08:00
    @lhx2008 看错题目了。
    stevenbipt
        11
    stevenbipt  
       2018-03-20 10:14:02 +08:00 via Android
    根据给定的字符串长度考虑一下,分解出来的 4 组数字哪一组的长度小于 3,先填充 0,然后直接每三位分离出来一组数字,这样会不会好一点(就是一个思路,说不定是死胡同,没验证过)(#逃
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5331 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 08:16 · PVG 16:16 · LAX 01:16 · JFK 04:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.