- 主题:Re: 谁给我写一个高效算法，可以支付宝或者微信转账
这不难
要多高效？
【 在 speedboy2998 () 的大作中提到: 】
: 一个检测电话号码重复冲突的算法。
:
: 一个输入框，允许用如下形式输入电话号码：
: 13877692008
--
FROM 138.19.103.*
如果号码长度（十进制）上界为L
已经输入了n个不冲突的区间/前缀通配
那判断下一个输入是否冲突/如果不冲突的话更新n+1的时间/空间复杂度是log(nL)/L
输入所有n组的复杂度是n*log(nL)/nL
还行吧
【 在 fanci () 的大作中提到: 】
: 这不难
:
: 要多高效？
:
--
修改:fanci FROM 138.19.103.*
FROM 138.19.103.*
说个思路你自己实现一下吧。其实二楼已经说得八九不离十了。如果没有前缀通配，那这个问题就是整数区间求并求交，二分法不难。而对于前缀通配，比如13*，而已转换成以下区间的并：13, 130-139, 1300-1399, 13000-13999, 等等，其个数是电话号码的长度上界L。
【 在 speedboy2998 () 的大作中提到: 】
: 可以。能私信报价吗？
:
:
: 【 在 fanci 的大作中提到: 】
--
FROM 138.19.103.*
擦我想开两千的
【 在 smthwang00 () 的大作中提到: 】
: 500
:
: 【 在 speedboy2998 的大作中提到: 】
: #发送自zSMTH@IOS
--
FROM 138.19.103.*
用Trie确实更好
【 在 galaxy123 () 的大作中提到: 】
: 按你目前提的需求，很容易做。
:
: 如果*可以出现在任何位置，如*138*4*5* 这种，就稍微麻烦点，如果你再加其他需求，如.只匹配一个数字，或限定数字范围，或限定匹配段的长度，那就更麻烦了。
:
--
FROM 138.19.103.*
可以是可以，但是要分很多情况，麻烦。
【 在 here080 () 的大作中提到: 】
: trie前缀不好处理a-b的这种格式。
: 【 在 ble (ble) 的大作中提到: 】
--
FROM 203.145.94.*
可以把13*变成13, 130-139, 1300-1399 等的并
你的程序稍微改改就行了！
【 在 here080 () 的大作中提到: 】
: 不过不固定的话，问题就不能当成数字range来处理了。
: 【 在 speedboy2998 (极品飞车) 的大作中提到: 】
--
FROM 203.145.94.*
*X 稍微麻烦点，而且目测意义不大。首先你会发现 X* 和 *Y 不能共存。然后 要把*Y 从a-b里抠出去，你会发现非常容易冲突。
【 在 speedboy2998 () 的大作中提到: 】
: *XX不是必须的。
:
: XX*是必须
:
--
FROM 203.145.94.*
眼睛好尖！
【 在 here080 () 的大作中提到: 】
: 是冲突的，你的138后面有9个9，所以800 **** ****都被包括了。
: 【 在 speedboy2998 (极品飞车) 的大作中提到: 】
--
FROM 203.145.94.*
我还没懂…是不是完全变成前缀树的问题了
【 在 here080 () 的大作中提到: 】
: 我懂了……
: 其实更简单了。
: 等我改改。
: 【 在 speedboy2998 (极品飞车) 的大作中提到: 】
--
FROM 203.145.94.*