面试时遇到的一道算法题

[abusizhishen]

写算法实现从字符串中提取整数。
如 'a1b2c3d4'需要提取为 1234，这里的 1234 是整数不是字符串 要求：
1.不能有隐式类型转换。
2.尽可能优化。

3.延伸思考，如果提取出的数字超过最大值怎么办？如最大为 123，超过这个数时如何处理？

[abusizhishen]

@pkookp8 隐式转换哦

[geelaw]

@geelaw 呃……显然我的意思是 if (ch >= '0' && ch < '0' + 10) 才对

[MeteorCat]

ASCII 判断一下就行了

[MeteorCat]

muduo 库里面有个字符串转数字的方法，你看下是不是这样
https://github.com/chenshuo/muduo/blob/master/muduo/base/LogStream.cc

[abusizhishen]

@geelaw 没看懂😂

[abusizhishen]

@MeteorCat 对

[abusizhishen]

预定义一个数组

[abusizhishen]

$arr=["0"=>0，"1"=>1,"2"=>2,...]
array_key_exists()

[markx]

不能隐式类型转换， 可以显式转换？

[binux]

@abusizhishen 这不叫算法题，这叫猜猜看我想什么。

[lhx2008]

@binux 脱了裤子放屁哈哈，增加空间复杂度时间复杂度

[ctro15547]

#python
s = 'a1a2a3a4'
i = int(''.join(filter(lambda k: k.isdigit(),list(s))))
print i
#1234

延伸 3，如果只比 123 小就输出的话，写个判断 大于 123 的 除以 100，即 12.34 ，19.37 这种

还可以先排个序，输出：范围内最大或最小的数，43.21 ，97.31

是我理解错了吗，总感觉前面讨论的我都听不懂。。。

[bzw875]

'a1b2c3d4'.replace(/[^\d]/g, '')

[i_have_to_pee]

楼主这么萌，你们不要欺负他。

[Bryan0Z]

讲道理，两个 for 循环搞定啊…像我大一时候做的题目

[SourceMan]

这不是算法题
这叫：茴香豆的茴有几种写法

[Kisesy]

看起来简单的问题，实际上非常难，因为限制了隐式类型转换，而不少语言，从字符串里取元素时，会隐式转成整数，所以连字符串遍历都不能写，就别说实现了(滑稽

[snowonion]

-- Haskell (GHC 8.2.2)
-- 使用了尽量初级的语言特性……

extractInt :: String -> Int
extractInt str = strToInt (filter isDigit str)

strToInt :: String -> Int
strToInt str = sum ( zipWith (*) (map (10^) [0..]) (reverse (strToDigits str) ) )

strToDigits :: String -> [Int]
strToDigits str = map (subtract (fromEnum '0') . fromEnum) str

isDigit :: Char -> Bool
isDigit ch = fromEnum '0' <= ascii && ascii <= fromEnum '9' where
ascii = fromEnum ch

>> 如果提取出的数字超过最大值怎么办？如最大为 123，超过这个数时如何处理？

你想处理成什么样？
（注意不是“你想怎么处理”）

[snowonion]

Oi，为什么程序员聚居的 V2EX 吃缩进这么熟练啊！ Try：
```
isDigit :: Char -> Bool
isDigit ch = fromEnum '0' <= ascii && ascii <= fromEnum '9' where
ascii = fromEnum ch
```
这里有两个空格缩进 ascii = fromEnum ch