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

请教个算法问题

  •  
  •   shunai · 2013-11-26 09:49:19 +08:00 · 4452 次点击
    这是一个创建于 3997 天前的主题,其中的信息可能已经有所发展或是发生改变。
    现在有2w个手机卡号,已经在Excel中,如何从这些卡号中宣传一些靓号,这些良好的规则如下:

    1. 重复A的话,选出相同且相连,并包含A个数的号码,
    如:AAA,那么13(444)267879、13426(777)879均能被选出

    2. 如果是ABC...(字母递增,最长11位),那么宣传号码递增的号码,
    如:ABCD,那么134(4567)8879、1344426(1234),均被选出


    嗯,好像描述的还行,谢谢各位大大。
    第 1 条附言  ·  2013-11-26 16:05:41 +08:00
    修改文字上的一些错误。

    宣传=选出
    良好=靓号

    用惯了搜狗输入法,切换到ibus总是不顺,囧,让大家看辛苦了
    24 条回复    1970-01-01 08:00:00 +08:00
    tabris17
        1
    tabris17  
       2013-11-26 09:54:46 +08:00
    算法你不是都描述出来么
    megaforce
        2
    megaforce  
       2013-11-26 09:56:19 +08:00   ❤️ 1
    看这个是否可以达到你的要求:
    http://www.itpub.net/thread-1801997-2-1.html
    Mutoo
        3
    Mutoo  
       2013-11-26 10:11:03 +08:00   ❤️ 1
    第一种情况用正则很容易构造 \d{3}
    第二个情况实际上也可以构造正则,因为数量太少了
    (0123)|(1234)|(2345)|(3456)|(4567)|(5678)|(6789)|(7890)
    shunai
        4
    shunai  
    OP
       2013-11-26 10:51:02 +08:00
    @Mutoo
    第一种情况正则比较简单,
    第二种情况,要枚举好多,因为不一定是4个递增的字母

    其实需求还隐含着,AAA***DEF 这些格式
    shunai
        5
    shunai  
    OP
       2013-11-26 10:56:43 +08:00
    @megaforce

    确实有相同需求,不过我需要更灵活点,类似这种格式(AAA***DEF)也能筛选
    shunai
        6
    shunai  
    OP
       2013-11-26 10:57:29 +08:00
    @tabris17

    可以说是算法描述,而不是算法实现
    tabris17
        7
    tabris17  
       2013-11-26 11:01:48 +08:00   ❤️ 1
    @shunai 死做呗,查找字符串内是否包含子串:
    111,1111,11111,……
    222,2222,22222,……
    ……
    999,9999,99999,……
    000,0000,00000,……

    123、1234、12345、……
    234、2345、23456、……
    ……
    678,6789
    789

    2w条记录也很快就出来了
    seeker
        8
    seeker  
       2013-11-26 13:23:18 +08:00   ❤️ 1
    以前遇到过个银行卡号的正则,主要靠枚举,4000个字符不够存了,后来还增大数据库字段的长度...
    alexrezit
        9
    alexrezit  
       2013-11-26 13:31:03 +08:00   ❤️ 1
    你可以自己写一个算法来给每个号码的 "亮" 度打分然后排序...

    (虽然我觉得毫无任何科学依据地把一些数字排列说成 "亮" 很脑残...)
    shunai
        10
    shunai  
    OP
       2013-11-26 16:07:13 +08:00
    @tabris17 2w是我大概描述的一个数据,早知道写个200w
    shunai
        11
    shunai  
    OP
       2013-11-26 16:09:04 +08:00
    @seeker 枚举好粗暴,而且即使枚举出来也不好比较,太多项了
    tabris17
        12
    tabris17  
       2013-11-26 16:09:11 +08:00
    @shunai 放心吧,和你通用算法相比,这种办法耗时差不了一个数量级的
    shunai
        13
    shunai  
    OP
       2013-11-26 16:10:06 +08:00
    @alexrezit 首先要知道打分的算法
    luikore
        14
    luikore  
       2013-11-26 17:02:29 +08:00
    从靓到丑排列打印(ruby)

    puts numbers.sort_by{|n|
    a = (n[/(\d)\1+/] || '').size
    b = n.count /01|12|23|34|45|56|67|78|89/
    [a, b].max
    }
    luikore
        15
    luikore  
       2013-11-26 17:06:09 +08:00
    呃, 上一帖加个 .reverse, 意思明白就好
    wangyongbo
        16
    wangyongbo  
       2013-11-26 17:08:20 +08:00
    规则很多,用个 有限状态 自动机 ? 停止的时候,就是符合某个规则的靓号
    nealnote
        17
    nealnote  
       2013-11-26 17:37:46 +08:00   ❤️ 1
    大家都在说正则。
    我换个思路说,不是正则,
    用 charcode
    0: 48
    1: 49
    计算2个相邻字的code差值,相差不大于1的,不是相等就是连号。
    用这个方法就不限于数字,字母也可以用。
    fanzeyi
        18
    fanzeyi  
       2013-11-26 18:34:47 +08:00
    个人倾向于给每个手机好评定出一个分数。

    手机号码每一位依次往后扫,比如这一位是 6 ,就这个号码加 2 分,然后这一位的前面有 n 个 6,那么就加 2 * n 分,等等这些规则,最后统计每个号码的分数,结果就有了。
    fanzeyi
        19
    fanzeyi  
       2013-11-26 18:35:14 +08:00
    啊,第一句应该是「手机号」,不是「手机好」,笔误..
    meta
        20
    meta  
       2013-11-26 19:11:36 +08:00
    好像没啥现成的办法,只能用原始的方法,把这些号码拆成单个数字,扔到一颗树里面,从根节点开始遍历。
    wxstorm
        21
    wxstorm  
       2013-11-26 19:22:40 +08:00
    @tabris17 re~~~
    就这点数据,这点东西要啥算法啊,excel查找不就好了~~
    shunai
        22
    shunai  
    OP
       2013-11-26 20:04:18 +08:00
    @nealnote

    如果比较charcode还不如直接比较数字
    kfqb536
        23
    kfqb536  
       2013-11-26 21:02:33 +08:00
    mark
    coldear
        24
    coldear  
       2013-11-28 04:49:11 +08:00
    这个问题其实就是从一个字符串中同时找到最长递增序列和最长重复序列。
    大O是 m(字符串个数)*n(单个字符串长度)。 就每个字符串扫一遍。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3345 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 10:55 · PVG 18:55 · LAX 02:55 · JFK 05:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.