面试时遇到的一道算法题

[abusizhishen]

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

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

[sean10]

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

[seaswalker]

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

[JRyan]

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

[abusizhishen]

@seaswalker 思路可以

[abusizhishen]

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

[MinonHeart]

正则+显示转换

[deepjia]

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

[lance6716276]

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

[abusizhishen]

@deepjia 6

[abusizhishen]

@deepjia 接近了

[lhx2008]

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

[lhx2008]

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

[lhx2008]

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

[abusizhishen]

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

[blless]

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

[blless]

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

[abusizhishen]

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

[pkookp8]

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

[abusizhishen]

@blless 看起来可以

[geelaw]

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

脑补的