V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
YadongZhang
V2EX  ›  职场话题

一道怀疑人生的算法题,就这?

  •  
  •   YadongZhang · 2020-07-20 19:39:14 +08:00 · 4130 次点击
    这是一个创建于 1586 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1234567890 -> '1,234,567,890'

    P.S. 考虑兼容性和性能问题

    我写的代码:

    function numToStr(num) {
    	// STEP 1: type conversion
    	
    	let tempStr = String(num)
    
    	// STEP 2: modular -> 3
    	
    	let m = tempStr.length % 3
    
    	// STEP 3: slice -> '1 | 234567890'
    	
    	let part1 = `${tempStr.slice(0, m)},`
    	let tempPart2 = tempStr.slice(m), part2 = ''
    
    	// STEP 4: split -> '234,567,890'
    	
    	for (let i = 0; i < tempPart2.length; i++) {
    		if (i > 0 && i % 3 === 0) {
    			part2 += ','
    		}
    		part2 += tempPart2.charAt(i)
    	}
    
    	// STEP 5: combine -> '1,234,567,890'
    	
    	let str = part1 + part2
    
    	return str
    }
    
    const number = 1234567890
    numToStr(number) // '1,234,567,890'
    

    专业程序员的解法

    function numberWithCommas(x) {
        return x.toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",");
    }
    
    24 条回复    2020-07-21 20:32:00 +08:00
    seki
        1
    seki  
       2020-07-20 19:43:46 +08:00   ❤️ 4
    这种题不用想太多,差不多和茴的几种写法一样,见过的用过的就能想到。不过反正至少你也学到了,不亏
    zhouyg
        2
    zhouyg  
       2020-07-20 20:14:37 +08:00
    常规操作
    JeffGe
        3
    JeffGe  
       2020-07-20 20:18:41 +08:00
    function numberWithCommas(x) {
    return x.toString().split('')
    .map((s, i, arr) => (arr.length - i - 3) % 3 == 1 ? s + ',' : s)
    .join('');
    }

    会正则还是厉害
    yuzo555
        4
    yuzo555  
       2020-07-20 20:26:28 +08:00   ❤️ 2
    number_format(1234567890)

    这时候就体现出 PHP 的开发效率了
    Kaciras
        5
    Kaciras  
       2020-07-20 20:28:17 +08:00
    这种题你不知道环视肯定只能循环。

    其实很多正则教程都把这题当例子讲的。
    rabbbit
        6
    rabbbit  
       2020-07-20 20:28:31 +08:00   ❤️ 6
    console.log((1234567890).toLocaleString());
    yhxx
        7
    yhxx  
       2020-07-20 20:31:15 +08:00
    让你更怀疑人生的:

    const num = 1234567890;
    console.log(num.toLocaleString());
    YadongZhang
        8
    YadongZhang  
    OP
       2020-07-20 20:57:34 +08:00
    @seki #1 算法考的都是没见过的才能体现出水平,哈哈

    @JeffGe #3 强,学到了

    @Kaciras #5 正则基本不会

    @rabbbit #6
    @yhxx #7 注意兼容性和性能问题,不过我是真没想到
    seki
        9
    seki  
       2020-07-20 23:14:22 +08:00   ❤️ 1
    @YadongZhang 这题目其实都也谈不到什么算法技巧,正式算法题都不靠这种「啊哈哈能用正则来一行搞定」的东西来体现水平的
    YadongZhang
        10
    YadongZhang  
    OP
       2020-07-20 23:34:32 +08:00 via Android
    @seki 可能面试官根据我的水平出的。。。
    baka
        11
    baka  
       2020-07-21 01:05:45 +08:00   ❤️ 3
    毕竟是算法题,本来正经 O(n)就能解决。正则 NFA 匹配需要 O(nm),DFA 构造需要 O(2^n)。
    xiadong1994
        12
    xiadong1994  
       2020-07-21 01:24:09 +08:00 via iPhone
    用正则还叫考虑性能?
    billlee
        13
    billlee  
       2020-07-21 01:28:46 +08:00
    我怎么怀疑这个正则性能可能比手写的还差
    also24
        14
    also24  
       2020-07-21 01:42:23 +08:00   ❤️ 2
    @rabbbit #6
    @yhxx #7
    你们这个方法就需要考虑兼容性问题了,最好加个 locales 参数指定一下语言(格式),不然容易出现其它结果。
    参见: https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Number/toLocaleString


    顺便说一句,4 楼 @yuzo555 用 php 的内置的 number_format 就没问题,因为那个方法不论什么区域,都是按照 千分位,加 "," 来处理的,不过需要注意的是默认是不管小数部分的。
    参见: https://www.php.net/manual/en/function.number-format.php
    seki
        15
    seki  
       2020-07-21 03:05:45 +08:00
    @YadongZhang 我倒没有这个意思。就是提醒你刷算法题的话不用太纠结于这种类型的题,把那些基本题型掌握好更重要。水平之类的想法也不用太多,说不定面试官就是正好题库里面有这么一道题。

    当然这种题就算是不用正则的写法,也是有很多种解答的,这个是可以自己琢磨,改进代码风格的
    yanguango
        16
    yanguango  
       2020-07-21 06:50:36 +08:00
    不用考虑国际化的吗,有些国家就不是用逗号的。如果是 JS 就用 toLocaleString
    cmqwan
        17
    cmqwan  
       2020-07-21 08:34:26 +08:00 via iPhone
    要写正则时,一般对着百度百科里面到底语法写
    ytmsdy
        18
    ytmsdy  
       2020-07-21 09:03:34 +08:00 via iPhone
    大兄弟,这不叫算法题。
    在 acm 里面这玩意儿叫模拟题,基本上属于白送的类型!
    ZehaiZhang
        19
    ZehaiZhang  
       2020-07-21 10:12:13 +08:00
    对着谷歌写正则+1
    另外这题目也不算是算法
    zy445566
        20
    zy445566  
       2020-07-21 11:04:05 +08:00
    正则性能未必就有手写得好,leetcode 就有很多正则过不去,手写妥妥的题
    zoeliu
        21
    zoeliu  
       2020-07-21 11:07:16 +08:00
    正则表达式性能很差,这两种也不算什么是否专业的差距。
    可以专门学一下正则,但不需要全部记住,用的时候能查能用即可。
    YadongZhang
        22
    YadongZhang  
    OP
       2020-07-21 11:12:29 +08:00
    @baka #11 大佬大佬,KMP 里看到 DFA 完全不懂,羡慕对算法掌握这么深的
    @seki #15 自己菜咱得承认,其实很少有人说真话的,听点真话进步快
    @ytmsdy #18 我这智商跟 ACM 无缘,能做个模拟题已经很成功了
    Messiahhh
        23
    Messiahhh  
       2020-07-21 20:14:16 +08:00
    零宽断言表示一个位置,over
    YadongZhang
        24
    YadongZhang  
    OP
       2020-07-21 20:32:00 +08:00 via Android
    @Messiahhh #23 听都没听过,over
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2502 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 15:29 · PVG 23:29 · LAX 07:29 · JFK 10:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.