V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
plantparknet
V2EX  ›  Python

Leetcode 新题 number-of-digit-one 求解

  •  
  •   plantparknet · 2015-07-07 23:10:42 +08:00 · 4148 次点击
    这是一个创建于 3416 天前的主题,其中的信息可能已经有所发展或是发生改变。
    https://leetcode.com/problems/number-of-digit-one/

    先转换成字符串,然后看1出现的次数。。。好愚蠢的办法。。。结果提示Runtime Err

    class Solution:
    # @param {integer} n
    # @return {integer}
    def countDigitOne(self, n):
    numStr = ""
    for i in range(1,n+1):
    numStr = numStr + str(i)
    result = 0
    for n in numStr:
    if n == "1":
    result = result + 1
    return result
    24 条回复    2015-07-12 02:08:03 +08:00
    bengol
        1
    bengol  
       2015-07-07 23:31:27 +08:00
    好像是编程之美上的题吧
    msg7086
        2
    msg7086  
       2015-07-07 23:32:13 +08:00
    花点时间想想更高效率的算法不行么?
    20015jjw
        3
    20015jjw  
       2015-07-07 23:42:28 +08:00
    class Solution:
    # @param {integer} n
    # @return {integer}
    def countDigitOne(self, n):
    return sum((1 for i in range(n+1) if '1' in str(i)))

    如果用lz的办法死算,是会超时的...
    20015jjw
        4
    20015jjw  
       2015-07-07 23:42:47 +08:00
    @20015jjw 这个就是死算的办法...
    msg7086
        5
    msg7086  
       2015-07-07 23:45:47 +08:00
    @20015jjw 不是 1 if '1' in str(i),而是count。
    yangqi
        6
    yangqi  
       2015-07-08 00:02:29 +08:00
    没看Hint说的是注意overflow么
    20015jjw
        7
    20015jjw  
       2015-07-08 00:05:45 +08:00
    @msg7086 啥?这个结果跑出来是对的啊.. 就是超时..
    msg7086
        8
    msg7086  
       2015-07-08 00:36:10 +08:00
    @20015jjw count_digit_one(2147483647) == 2971027783 你看看你是不是这结果。
    20015jjw
        9
    20015jjw  
       2015-07-08 00:46:38 +08:00
    @msg7086 - - 目测是 但是要跑两年 因为这个办法是死算的 - - 你换个小于100k的数呢
    msg7086
        10
    msg7086  
       2015-07-08 00:53:34 +08:00   ❤️ 1
    @20015jjw count_digit_one(76543) == 41015
    20015jjw
        11
    20015jjw  
       2015-07-08 00:57:01 +08:00
    @msg7086 啊哈懂了 xD 看错题了xDDDDD 谢谢!
    >>> sum((1 for i in range(76543+1) if '1' in str(i)))
    33179
    >>> sum((str(i).count('1') for i in range(76543+1) if '1' in str(i)))
    41015
    mickeyandkaka
        12
    mickeyandkaka  
       2015-07-08 00:57:02 +08:00
    递归,举个例子 51234 = 50000 + 1000+ 200+ 30 + 4
    低位可以对高位做贡献,复杂度log(n)

    数位dp很容易做出来。部分代码
    long long dfs(int pos, bool bound)
    {
    if(pos == -1) return 0;
    if(!bound && ~dp[pos]) return dp[pos];

    int end = bound ? dig[pos]-'0' : 9;
    long long ret = 0;
    for(int i=0; i<=end; i++)
    {
    ret += dfs(pos-1, bound && i == end);
    if(i == 1)
    {
    if(bound && i == end) ret += q[pos] + 1;
    else ret += p[pos];
    }
    }
    if (!bound) dp[pos] = ret;
    return ret;
    }
    msg7086
        13
    msg7086  
       2015-07-08 01:09:40 +08:00 via Android
    @20015jjw 楼主这个应该是爆内存了。随便就要吃掉2G内存。
    xhuuanniqege
        14
    xhuuanniqege  
       2015-07-08 01:12:37 +08:00 via Android
    数位dp
    IwfWcf
        15
    IwfWcf  
       2015-07-08 01:17:00 +08:00   ❤️ 1
    msg7086
        16
    msg7086  
       2015-07-08 01:47:03 +08:00   ❤️ 1
    40 / 40 test cases passed.
    Status: Accepted
    Runtime: 72 ms
    Submitted: 1 hour, 3 minutes ago

    https://gist.github.com/msg7086/4477fb824f1d7968178c
    20015jjw
        17
    20015jjw  
       2015-07-08 06:06:28 +08:00
    @msg7086 下学期学DP... 请问这是DP嘛...
    msg7086
        18
    msg7086  
       2015-07-08 07:38:34 +08:00   ❤️ 1
    @20015jjw 我的代码并不是。
    20015jjw
        19
    20015jjw  
       2015-07-09 05:33:42 +08:00   ❤️ 1
    10 minutes ago Accepted 44 ms (submitted without the doctest) python

    https://gist.github.com/20015jjw/74ab03818741aaa0e7bb
    plantparknet
        20
    plantparknet  
    OP
       2015-07-09 12:44:39 +08:00
    @20015jjw Great!
    plantparknet
        21
    plantparknet  
    OP
       2015-07-09 12:45:01 +08:00
    @msg7086
    @IwfWcf
    谢谢~~
    ChangxuBlack
        22
    ChangxuBlack  
       2015-07-10 18:38:26 +08:00
    @20015jjw 我不知道你当时过了没,反正现在你的代码会超时
    20015jjw
        23
    20015jjw  
       2015-07-12 02:07:25 +08:00
    @ChangxuBlack

    并没有啊.... 你看我gist里的代码啊.... 顺便去掉doctest提交..... (虽然就算带了doctest也会过啊.....

    <img src="http://s1.momo.moda/2015/07/12/1cc3633c579a90cfdd895e64021e2163.png" alt="" title="" />
    20015jjw
        24
    20015jjw  
       2015-07-12 02:08:03 +08:00
    @20015jjw 啊我不会发图 图中就是过了的截图...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1057 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 20:05 · PVG 04:05 · LAX 12:05 · JFK 15:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.