面试时遇到的一道算法题

abusizhishen · 2018-03-18T13:26:59Z

写算法实现从字符串中提取整数。如 'a1b2c3d4'需要提取为 1234，这里的 1234 是整数不是字符串要求： 1.不能有隐式类型转换。 2.尽可能优化。 3.延伸思考，如果提取出的数字超过最大值怎么办？如最大为 123，超过这个数时如何处理？

提取

字符

整数

算法

39 replies • 2018-03-22 23:51:25 +08:00

1

sean10

Mar 18, 2018 via Android

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

2

seaswalker

Mar 18, 2018 via iPhone

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

3

JRyan

Mar 18, 2018

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

4

abusizhishen

OP

Mar 18, 2018 via Android

@seaswalker 思路可以

5

abusizhishen

OP

Mar 18, 2018 via Android

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

6

MinonHeart

Mar 18, 2018 via iPhone

正则+显示转换

7

deepjia

Mar 19, 2018 via iPhone

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

8

lance6716276

Mar 19, 2018 via Android

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

9

abusizhishen

OP

Mar 19, 2018 via Android

@deepjia 6

10

abusizhishen

OP

Mar 19, 2018 via Android

@deepjia 接近了

11

lhx2008

Mar 19, 2018 via Android

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

12

lhx2008

Mar 19, 2018 via Android

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

13

lhx2008

Mar 19, 2018 via Android

1

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

14

abusizhishen

OP

Mar 19, 2018 via Android

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

15

blless

Mar 19, 2018 via Android

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

16

blless

Mar 19, 2018 via Android

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

17

abusizhishen

OP

Mar 19, 2018 via Android

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

18

pkookp8

Mar 19, 2018 via Android

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

19

abusizhishen

OP

Mar 19, 2018 via Android

@blless 看起来可以

20

geelaw

Mar 19, 2018

/* 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;
}

脑补的

21

abusizhishen

OP

Mar 19, 2018 via Android

@pkookp8 隐式转换哦

22

geelaw

Mar 19, 2018

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

23

MeteorCat

Mar 19, 2018 via Android

ASCII 判断一下就行了

24

MeteorCat

Mar 19, 2018 via Android

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

25

abusizhishen

OP

Mar 19, 2018 via Android

@geelaw 没看懂😂

26

abusizhishen

OP

Mar 19, 2018 via Android

@MeteorCat 对

27

abusizhishen

OP

Mar 19, 2018 via Android

预定义一个数组

28

abusizhishen

OP

Mar 19, 2018 via Android

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

29

markx

Mar 19, 2018

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

30

binux

Mar 19, 2018 via Android

3

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

31

lhx2008

Mar 19, 2018 via Android

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

32

ctro15547

Mar 19, 2018

#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

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

33

bzw875

Mar 19, 2018

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

34

i_have_to_pee

Mar 19, 2018

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

35

Bryan0Z

Mar 19, 2018 via Android

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

36

SourceMan

Mar 19, 2018

1

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

37

Kisesy

Mar 19, 2018

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

38

snowonion

Mar 22, 2018

-- 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，超过这个数时如何处理？

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

39

snowonion

Mar 22, 2018

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