出道题给大家耍下，有闲的各位请接招

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2980 天前的主题，其中的信息可能已经有所发展或是发生改变。

有这样的输入字符串
“ tt2012g2 ”

求该字符串中，最长的连续数字子串。

语言不限～： P

字符

子串

tt2012g2

学学

21 条回复 • 2016-02-29 22:20:05 +08:00

northisland

2016-02-26 18:37:55 +08:00

def temp(line,flag,pos,lvl=0):
if line[pos].isdigit():
flag[pos]=lvl+1
if pos+1<len(line):
return temp(line,flag,pos+1,lvl+1)
else:
return pos+1,lvl
else:
flag[pos]=0
lvl=0
return pos+1,lvl

def extract_digits(line):
"""
extract longest digit sub-str from line
:param line:
:return:
"""
flag=[0 for x in range(len(line))]
print flag
pos=0
while pos<len(flag):
pos,lvl=temp(line,flag,pos)
print flag
length=max(flag)
if length>0:
pe=flag.index(length)
return line[pe-length+1:pe+1]
else:
return ''

if __name__=='__main__':
print extract_digits('tt2012g2t11111g')

northisland

2016-02-26 18:41:44 +08:00

http://gist.github.com/5885857ecfeef423be7a

northisland

2016-02-26 18:47:51 +08:00

xiaolajiao

2016-02-26 22:21:01 +08:00

import re
def maximum(string):
split_list = re.split('[a-zA-z]', string)
return max(split_list)

manfay

2016-02-27 00:22:51 +08:00 via iPad

ruby

/\d+/.match("tt2012g2")[0]

manfay

2016-02-27 00:31:51 +08:00 via iPad

错了😂

function007

2016-02-27 00:52:58 +08:00

$str = 'tt2012dg2';
preg_match_all('/\d+/', $str,$result);
rsort($result[0]);
echo $result[0][0];

imcotton

2016-02-27 01:20:05 +08:00

'tt2012dg2'.match(/\d+/g).reduce((a, b) => a.length > b.length ? a : b)

-ES2015

ETiV

2016-02-27 01:21:20 +08:00

写法 1, 不考虑长度并列:
INPUT_STRING.match(/(\d+)/g).sort(function(m,n){return n.length - m.length})[0];

2, 考虑并列长度:
var l=0;
INPUT_STRING.match(/(\d+)/g).map(function(n){l=n.length>l?n.length:l;return n;}).filter(function(n){return l == n.length});

vibbow

2016-02-27 01:27:01 +08:00

<?php
$input = 'tt2012g2';
preg_match_all('/(\d+)/', $input, $matches);
echo max($matches[0]);

scarlex

2016-02-27 01:37:59 +08:00

python

"tt2012g2"[2:6]

allan888

2016-02-27 09:16:36 +08:00

其实不太明白楼主写的啥意思，感觉不是 O(n)复杂度的样子，贴一个 O(n)的
https://gist.github.com/jieaozhu/3387e2561bfb0280635c

yuriko

2016-02-27 09:23:37 +08:00

唉我感觉是不是理解错了……
直接遍历一遍数数字个数不就好了？

northisland

2016-02-27 09:36:46 +08:00 via Android

@yuriko 这道题数一遍确实就好了，但是我想玩下递归算法。。。这种情况比较简单，所以体现不出递归的好处。

这几天想用递归写点复杂的算法，自己也在算法上进步进步~

allan888

2016-02-27 09:41:40 +08:00

@northisland 递归的话你多找找 backtracking 和深度优先的题目来做啊。。。

yuriko

2016-02-27 09:43:53 +08:00

@northisland 递归是降低逻辑复杂度的办法，但反过来效率经常都不怎么好。
递归也只是一种把未知问题降低为已知问题的手段罢了，强用也是强扭的瓜……

以及，我太不喜欢用递归

myid

2016-02-28 20:16:56 +08:00

Haskell 代码。 O(n) 。递归。

import Data.Char (isDigit)

longestInts :: String -> [Int]
longestInts xs = map (digitsToInt) $ longestLength $ extractDigits xs

extractDigits :: String -> [String]
extractDigits [] = []
extractDigits xs
| null $ dropWhile (not.isDigit) xs = []
| otherwise = (takeWhile (isDigit) $ dropWhile (not.isDigit) xs) : (extractDigits $ dropWhile (isDigit) $ dropWhile (not.isDigit) xs)

myid

2016-02-28 20:54:59 +08:00

@xiaolajiao 字符里有特殊字符呢？例如!@#$%^&*()"{}\|等。。。
@scarlex O(1)算法！妙。。。

xiaolajiao

2016-02-28 22:04:05 +08:00

之前版本有错误，这样就好了
@myid
import re
def maximum(string):
split_list = re.split('\D', string)
int_list = [int(s) for s in split_list if len(s) > 0]
return max(int_list)

scarlex

2016-02-28 22:24:01 +08:00

@myid 其实楼上很多直接取正则返回结果中的第一个值的做法，和我直接从索引取字符串没什么区别啊，都是作弊。

scarlex

2016-02-29 22:20:05 +08:00

@myid

Haskell

getNumbers [] = [[]]
getNumbers xs = [ys] ++ getNumbers zs'
____where (ys, ys') = span (\x -> x `elem` ['0'..'9']) xs
__________(zs, zs') = break (\x -> x `elem` ['0'..'9']) ys'

getLongest = (foldr f "") . getNumbers
____where f x y = if (length x > length y) then x else y

不用正则，只用预设函数写出来的版本~