首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Coding
V2EX  ›  算法

面试时遇到的一道算法题

  •  
  •   abusizhishen · 2018-03-18 21:26:59 +08:00 · 2915 次点击
    这是一个创建于 637 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    39 回复  |  直到 2018-03-22 23:51:25 +08:00
        1
    sean10   2018-03-18 22:19:36 +08:00 via Android
    这块转换不太懂,stringstream 转换的可以吗?
        2
    seaswalker   2018-03-18 22:27:46 +08:00 via iPhone
    倒序遍历字符串,判断 ASCII 码,如果是数字,减去字符 0,乘以 10/00/1000 等等,相加?
        3
    JRyan   2018-03-18 22:29:53 +08:00
    @seaswalker 这样是不是有隐式类型转换?
        4
    abusizhishen   2018-03-18 22:37:06 +08:00 via Android
    @seaswalker 思路可以
        5
    abusizhishen   2018-03-18 22:41:41 +08:00 via Android
    @seaswalker 判断 ASC 太麻烦,还有没有简单点的?
        6
    MinonHeart   2018-03-18 23:51:13 +08:00 via iPhone
    正则+显示转换
        7
    deepjia   2018-03-19 00:15:25 +08:00 via iPhone
    直接每个字符哈希表映射一下完事
        8
    lance6716276   2018-03-19 00:30:35 +08:00 via Android
    延伸 4 适配给定编码的不同编码的字符串(我没想出自己的这个问题在 C 下要怎么弄
        9
    abusizhishen   2018-03-19 01:13:31 +08:00 via Android
        10
    abusizhishen   2018-03-19 07:33:25 +08:00 via Android
    @deepjia 接近了
        11
    lhx2008   2018-03-19 07:45:25 +08:00 via Android
    怎么样算隐式和显示啊,parseInt 算显示还是隐式?
        12
    lhx2008   2018-03-19 07:52:18 +08:00 via Android
    感觉还是 3 楼的思路,直接减'0'比 map 简单吧,倒序遍历,减出来如果小于 10 就加进 sum,然后 sum * 10,下一个循环。然后每次检查是不是比 123 大。
        13
    lhx2008   2018-03-19 07:54:32 +08:00 via Android   ♥ 1
    但是 char 减 char 最后还是先转了 int,如果这样也算隐式的话就只能用 map 了
        14
    abusizhishen   2018-03-19 08:00:57 +08:00 via Android
    @lhx2008 不能用 paseint,必须自己写程序识别
        15
    blless   2018-03-19 08:05:18 +08:00 via Android
    我写过类似的 直接用 unicodedata.numeric 判断的 unicode 自带符号 数字 大小写之类的判断 理论上没有进行类型转换 只是字符编码区间的归类
        16
    blless   2018-03-19 08:08:08 +08:00 via Android
    理论上我觉得用自带的归类判断应该是最优的 正则底层其实还是用字符归类做的
        17
    abusizhishen   2018-03-19 08:15:51 +08:00 via Android
    @lhx2008 不能直接拿来减,这不还是隐式转换么,另外不能直接和 123 比较,因为如果加起来的值大于了系统存储的最大值 123,就已经出错了
        18
    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
    这样?
        19
    abusizhishen   2018-03-19 08:23:29 +08:00 via Android
    @blless 看起来可以
        20
    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;
    }

    脑补的
        21
    abusizhishen   2018-03-19 08:27:34 +08:00 via Android
    @pkookp8 隐式转换哦
        22
    geelaw   2018-03-19 08:29:18 +08:00
    @geelaw 呃……显然我的意思是 if (ch >= '0' && ch < '0' + 10) 才对
        23
    MeteorCat   2018-03-19 08:33:57 +08:00 via Android
    ASCII 判断一下就行了
        24
    MeteorCat   2018-03-19 08:38:36 +08:00 via Android
    muduo 库里面有个字符串转数字的方法,你看下是不是这样
    https://github.com/chenshuo/muduo/blob/master/muduo/base/LogStream.cc
        25
    abusizhishen   2018-03-19 08:39:09 +08:00 via Android
    @geelaw 没看懂😂
        26
    abusizhishen   2018-03-19 08:39:23 +08:00 via Android
        27
    abusizhishen   2018-03-19 08:41:43 +08:00 via Android
    预定义一个数组
        28
    abusizhishen   2018-03-19 08:46:02 +08:00 via Android
    $arr=["0"=>0,"1"=>1,"2"=>2,...]
    array_key_exists()
        29
    markx   2018-03-19 08:47:08 +08:00
    不能隐式类型转换, 可以显式转换?
        30
    binux   2018-03-19 08:52:37 +08:00 via Android   ♥ 3
    @abusizhishen 这不叫算法题,这叫猜猜看我想什么。
        31
    lhx2008   2018-03-19 08:55:14 +08:00 via Android
    @binux 脱了裤子放屁哈哈,增加空间复杂度时间复杂度
        32
    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

    是我理解错了吗,总感觉前面讨论的我都听不懂。。。
        33
    bzw875   2018-03-19 10:09:56 +08:00
    'a1b2c3d4'.replace(/[^\d]/g, '')
        34
    i_have_to_pee   2018-03-19 13:36:48 +08:00
    楼主这么萌,你们不要欺负他。
        35
    Bryan0Z   2018-03-19 13:44:33 +08:00 via Android
    讲道理,两个 for 循环搞定啊…像我大一时候做的题目
        36
    SourceMan   2018-03-19 13:51:04 +08:00   ♥ 1
    这不是算法题
    这叫:茴香豆的茴有几种写法
        37
    Kisesy   2018-03-19 13:53:25 +08:00
    看起来简单的问题,实际上非常难,因为限制了隐式类型转换,而不少语言,从字符串里取元素时,会隐式转成整数,所以连字符串遍历都不能写,就别说实现了(滑稽
        38
    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,超过这个数时如何处理?

    你想处理成什么样?
    (注意不是“你想怎么处理”)
        39
    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
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1050 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 26ms · UTC 18:05 · PVG 02:05 · LAX 10:05 · JFK 13:05
    ♥ Do have faith in what you're doing.