面试时遇到的一道算法题

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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

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

提取

字符

整数

算法

39 条回复 • 2018-03-22 23:51:25 +08:00

sean10

2018-03-18 22:19:36 +08:00 via Android

这块转换不太懂，stringstream 转换的可以吗？

seaswalker

2018-03-18 22:27:46 +08:00 via iPhone

倒序遍历字符串，判断 ASCII 码，如果是数字，减去字符 0，乘以 10/00/1000 等等，相加？

JRyan

2018-03-18 22:29:53 +08:00

@seaswalker 这样是不是有隐式类型转换？

abusizhishen

2018-03-18 22:37:06 +08:00 via Android

@seaswalker 思路可以

abusizhishen

2018-03-18 22:41:41 +08:00 via Android

@seaswalker 判断 ASC 太麻烦，还有没有简单点的？

MinonHeart

2018-03-18 23:51:13 +08:00 via iPhone

正则+显示转换

deepjia

2018-03-19 00:15:25 +08:00 via iPhone

直接每个字符哈希表映射一下完事

lance6716276

2018-03-19 00:30:35 +08:00 via Android

延伸 4 适配给定编码的不同编码的字符串（我没想出自己的这个问题在 C 下要怎么弄

abusizhishen

2018-03-19 01:13:31 +08:00 via Android

@deepjia 6

abusizhishen

2018-03-19 07:33:25 +08:00 via Android

@deepjia 接近了

lhx2008

2018-03-19 07:45:25 +08:00 via Android

怎么样算隐式和显示啊，parseInt 算显示还是隐式？

lhx2008

2018-03-19 07:52:18 +08:00 via Android

感觉还是 3 楼的思路，直接减'0'比 map 简单吧，倒序遍历，减出来如果小于 10 就加进 sum，然后 sum * 10，下一个循环。然后每次检查是不是比 123 大。

lhx2008

2018-03-19 07:54:32 +08:00 via Android

但是 char 减 char 最后还是先转了 int，如果这样也算隐式的话就只能用 map 了

abusizhishen

2018-03-19 08:00:57 +08:00 via Android

@lhx2008 不能用 paseint，必须自己写程序识别

blless

2018-03-19 08:05:18 +08:00 via Android

我写过类似的直接用 unicodedata.numeric 判断的 unicode 自带符号数字大小写之类的判断理论上没有进行类型转换只是字符编码区间的归类

blless

2018-03-19 08:08:08 +08:00 via Android

理论上我觉得用自带的归类判断应该是最优的正则底层其实还是用字符归类做的

abusizhishen

2018-03-19 08:15:51 +08:00 via Android

@lhx2008 不能直接拿来减，这不还是隐式转换么，另外不能直接和 123 比较，因为如果加起来的值大于了系统存储的最大值 123，就已经出错了

pkookp8

2018-03-19 08:16:32 +08:00 via Android

for i in strings:
if i > '0' and i < '9'
sum = sum * 10 + i
这样？

abusizhishen

2018-03-19 08:23:29 +08:00 via Android

@blless 看起来可以

geelaw

2018-03-19 08:24:47 +08:00

/* assume C, therefore character literals are ints. */
unsigned asDigit(int ch)
{
if (ch >= '0' && ch <= '0' + 10) return ch - '0';
return -1u;
}
int parseAsUInt(char const *input, unsigned upperBound, unsigned *presult)
{
unsigned result = 0;
unsigned const threshold10 = upperBound / 10, threshold1 = upperBound % 10;
unsigned current;
if (!input) return 0;
for (; (int)*input; ++input)
{
if ((current = asDigit((int)*input)) == -1u) continue;
if (result > threshold10) return 0;
if (result == threshold10 && current > threshold1) return 0;
result = result * 10u + current;
}
if (presult)
*presult = result;
return 1;
}

脑补的

abusizhishen

2018-03-19 08:27:34 +08:00 via Android

@pkookp8 隐式转换哦

geelaw

2018-03-19 08:29:18 +08:00

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

MeteorCat

2018-03-19 08:33:57 +08:00 via Android

ASCII 判断一下就行了

MeteorCat

2018-03-19 08:38:36 +08:00 via Android

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

abusizhishen

2018-03-19 08:39:09 +08:00 via Android

@geelaw 没看懂😂

abusizhishen

2018-03-19 08:39:23 +08:00 via Android

@MeteorCat 对

abusizhishen

2018-03-19 08:41:43 +08:00 via Android

预定义一个数组

abusizhishen

2018-03-19 08:46:02 +08:00 via Android

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

markx

2018-03-19 08:47:08 +08:00

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

binux

2018-03-19 08:52:37 +08:00 via Android

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

lhx2008

2018-03-19 08:55:14 +08:00 via Android

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

ctro15547

2018-03-19 09:12:02 +08:00

#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

2018-03-19 10:09:56 +08:00

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

i_have_to_pee

2018-03-19 13:36:48 +08:00

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

Bryan0Z

2018-03-19 13:44:33 +08:00 via Android

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

SourceMan

2018-03-19 13:51:04 +08:00

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

Kisesy

2018-03-19 13:53:25 +08:00

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

snowonion

2018-03-22 23:49:01 +08:00

-- 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

2018-03-22 23:51:25 +08:00

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