推荐学习书目
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 · Jul 7, 2015 · 4673 views
    This topic created in 3992 days ago, the information mentioned may be changed or developed.
    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 replies    2015-07-12 02:08:03 +08:00
    bengol
        1
    bengol  
       Jul 7, 2015
    好像是编程之美上的题吧
    msg7086
        2
    msg7086  
       Jul 7, 2015
    花点时间想想更高效率的算法不行么?
    20015jjw
        3
    20015jjw  
       Jul 7, 2015
    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  
       Jul 7, 2015
    @20015jjw 这个就是死算的办法...
    msg7086
        5
    msg7086  
       Jul 7, 2015
    @20015jjw 不是 1 if '1' in str(i),而是count。
    yangqi
        6
    yangqi  
       Jul 8, 2015
    没看Hint说的是注意overflow么
    20015jjw
        7
    20015jjw  
       Jul 8, 2015
    @msg7086 啥?这个结果跑出来是对的啊.. 就是超时..
    msg7086
        8
    msg7086  
       Jul 8, 2015
    @20015jjw count_digit_one(2147483647) == 2971027783 你看看你是不是这结果。
    20015jjw
        9
    20015jjw  
       Jul 8, 2015
    @msg7086 - - 目测是 但是要跑两年 因为这个办法是死算的 - - 你换个小于100k的数呢
    msg7086
        10
    msg7086  
       Jul 8, 2015   ❤️ 1
    @20015jjw count_digit_one(76543) == 41015
    20015jjw
        11
    20015jjw  
       Jul 8, 2015
    @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
    valuedlute
        12
    valuedlute  
       Jul 8, 2015
    递归,举个例子 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  
       Jul 8, 2015 via Android
    @20015jjw 楼主这个应该是爆内存了。随便就要吃掉2G内存。
    xhuuanniqege
        14
    xhuuanniqege  
       Jul 8, 2015 via Android
    数位dp
    IwfWcf
        15
    IwfWcf  
       Jul 8, 2015   ❤️ 1
    msg7086
        16
    msg7086  
       Jul 8, 2015   ❤️ 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  
       Jul 8, 2015
    @msg7086 下学期学DP... 请问这是DP嘛...
    msg7086
        18
    msg7086  
       Jul 8, 2015   ❤️ 1
    @20015jjw 我的代码并不是。
    20015jjw
        19
    20015jjw  
       Jul 9, 2015   ❤️ 1
    10 minutes ago Accepted 44 ms (submitted without the doctest) python

    https://gist.github.com/20015jjw/74ab03818741aaa0e7bb
    plantparknet
        20
    plantparknet  
    OP
       Jul 9, 2015
    @20015jjw Great!
    plantparknet
        21
    plantparknet  
    OP
       Jul 9, 2015
    @msg7086
    @IwfWcf
    谢谢~~
    ChangxuBlack
        22
    ChangxuBlack  
       Jul 10, 2015
    @20015jjw 我不知道你当时过了没,反正现在你的代码会超时
    20015jjw
        23
    20015jjw  
       Jul 12, 2015
    @ChangxuBlack

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

    <img src="http://s1.momo.moda/2015/07/12/1cc3633c579a90cfdd895e64021e2163.png" alt="" title="" />
    20015jjw
        24
    20015jjw  
       Jul 12, 2015
    @20015jjw 啊我不会发图 图中就是过了的截图...
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   5016 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 43ms · UTC 01:10 · PVG 09:10 · LAX 18:10 · JFK 21:10
    ♥ Do have faith in what you're doing.