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

面试时遇到的一道算法题

  •  
  •   abusizhishen · 153 天前 · 2184 次点击
    这是一个创建于 153 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    39 回复  |  直到 2018-03-22 23:51:25 +08:00
        1
    sean10   152 天前 via Android
    这块转换不太懂,stringstream 转换的可以吗?
        2
    seaswalker   152 天前 via iPhone
    倒序遍历字符串,判断 ASCII 码,如果是数字,减去字符 0,乘以 10/00/1000 等等,相加?
        3
    JRyan   152 天前
    @seaswalker 这样是不是有隐式类型转换?
        4
    abusizhishen   152 天前 via Android
    @seaswalker 思路可以
        5
    abusizhishen   152 天前 via Android
    @seaswalker 判断 ASC 太麻烦,还有没有简单点的?
        6
    MinonHeart   152 天前 via iPhone
    正则+显示转换
        7
    deepjia   152 天前 via iPhone
    直接每个字符哈希表映射一下完事
        8
    lance6716276   152 天前 via Android
    延伸 4 适配给定编码的不同编码的字符串(我没想出自己的这个问题在 C 下要怎么弄
        9
    abusizhishen   152 天前 via Android
        10
    abusizhishen   152 天前 via Android
    @deepjia 接近了
        11
    lhx2008   152 天前 via Android
    怎么样算隐式和显示啊,parseInt 算显示还是隐式?
        12
    lhx2008   152 天前 via Android
    感觉还是 3 楼的思路,直接减'0'比 map 简单吧,倒序遍历,减出来如果小于 10 就加进 sum,然后 sum * 10,下一个循环。然后每次检查是不是比 123 大。
        13
    lhx2008   152 天前 via Android   ♥ 1
    但是 char 减 char 最后还是先转了 int,如果这样也算隐式的话就只能用 map 了
        14
    abusizhishen   152 天前 via Android
    @lhx2008 不能用 paseint,必须自己写程序识别
        15
    blless   152 天前 via Android
    我写过类似的 直接用 unicodedata.numeric 判断的 unicode 自带符号 数字 大小写之类的判断 理论上没有进行类型转换 只是字符编码区间的归类
        16
    blless   152 天前 via Android
    理论上我觉得用自带的归类判断应该是最优的 正则底层其实还是用字符归类做的
        17
    abusizhishen   152 天前 via Android
    @lhx2008 不能直接拿来减,这不还是隐式转换么,另外不能直接和 123 比较,因为如果加起来的值大于了系统存储的最大值 123,就已经出错了
        18
    pkookp8   152 天前 via Android
    for i in strings:
    if i > '0' and i < '9'
    sum = sum * 10 + i
    这样?
        19
    abusizhishen   152 天前 via Android
    @blless 看起来可以
        20
    geelaw   152 天前
    /* 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   152 天前 via Android
    @pkookp8 隐式转换哦
        22
    geelaw   152 天前
    @geelaw 呃……显然我的意思是 if (ch >= '0' && ch < '0' + 10) 才对
        23
    MeteorCat   152 天前 via Android
    ASCII 判断一下就行了
        24
    MeteorCat   152 天前 via Android
    muduo 库里面有个字符串转数字的方法,你看下是不是这样
    https://github.com/chenshuo/muduo/blob/master/muduo/base/LogStream.cc
        25
    abusizhishen   152 天前 via Android
    @geelaw 没看懂😂
        26
    abusizhishen   152 天前 via Android
        27
    abusizhishen   152 天前 via Android
    预定义一个数组
        28
    abusizhishen   152 天前 via Android
    $arr=["0"=>0,"1"=>1,"2"=>2,...]
    array_key_exists()
        29
    markx   152 天前
    不能隐式类型转换, 可以显式转换?
        30
    binux   152 天前 via Android   ♥ 3
    @abusizhishen 这不叫算法题,这叫猜猜看我想什么。
        31
    lhx2008   152 天前 via Android
    @binux 脱了裤子放屁哈哈,增加空间复杂度时间复杂度
        32
    ctro15547   152 天前
    #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   152 天前
    'a1b2c3d4'.replace(/[^\d]/g, '')
        34
    i_have_to_pee   152 天前
    楼主这么萌,你们不要欺负他。
        35
    Bryan0Z   152 天前 via Android
    讲道理,两个 for 循环搞定啊…像我大一时候做的题目
        36
    SourceMan   152 天前   ♥ 1
    这不是算法题
    这叫:茴香豆的茴有几种写法
        37
    Kisesy   152 天前
    看起来简单的问题,实际上非常难,因为限制了隐式类型转换,而不少语言,从字符串里取元素时,会隐式转成整数,所以连字符串遍历都不能写,就别说实现了(滑稽
        38
    snowonion   148 天前
    -- 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   148 天前
    Oi,为什么程序员聚居的 V2EX 吃缩进这么熟练啊! Try:
    ```
    isDigit :: Char -> Bool
    isDigit ch = fromEnum '0' <= ascii && ascii <= fromEnum '9' where
    ascii = fromEnum ch
    ```
    这里有两个空格缩进 ascii = fromEnum ch
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   实用小工具   ·   1894 人在线   最高记录 3762   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 32ms · UTC 14:15 · PVG 22:15 · LAX 07:15 · JFK 10:15
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1