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

2016-02-26 18:01:18 +08:00
 northisland
有这样的输入字符串
“ tt2012g2 ”


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

语言不限~: P
3090 次点击
所在节点    问与答
21 条回复
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
northisland
2016-02-26 18:47:51 +08:00
<script src="https://gist.github.com/anonymous/5885857ecfeef423be7a.js"></script>

好吧,原来 V2EX 的代码时这么贴的=_=




下午写代码遇到这个功能,
于是手痒做了一个递归算法版本的这个函数

大概写了 20 分钟写好,个人感觉递归函数很抽象,
请各位同志点评
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
ruby

/\d+/.match("tt2012g2")[0]
manfay
2016-02-27 00:31:51 +08:00
错了😂
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
@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 其实楼上很多直接取正则返回结果中的第一个值的做法,和我直接从索引取字符串没什么区别啊,都是作弊。

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/259360

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX