推荐学习书目
› 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
Leetcode 新题 number-of-digit-one 求解
plantparknet · 2015-07-07 23:10:42 +08:00 · 4157 次点击这是一个创建于 3425 天前的主题，其中的信息可能已经有所发展或是发生改变。
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
先转换成字符串，然后看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
 |
1
bengol 2015-07-07 23:31:27 +08:00
好像是编程之美上的题吧
|
 |
2
msg7086 2015-07-07 23:32:13 +08:00
花点时间想想更高效率的算法不行么？
|
 |
3
20015jjw 2015-07-07 23:42:28 +08:00
|
 |
6
yangqi 2015-07-08 00:02:29 +08:00
没看Hint说的是注意overflow么
|
|
8
msg7086 2015-07-08 00:36:10 +08:00
@20015jjw count_digit_one(2147483647) == 2971027783 你看看你是不是这结果。
|
|
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 |
 |
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; } |
 |
14
xhuuanniqege 2015-07-08 01:12:37 +08:00 via Android
数位dp
|
 |
15
IwfWcf 2015-07-08 01:17:00 +08:00  1
|
|
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 |
|
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 |
 |
20
plantparknet OP @20015jjw Great!
|
|
21
plantparknet OP |
 |
22
ChangxuBlack 2015-07-10 18:38:26 +08:00
@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="" /> |
Select Language