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

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

numstr

integer

result

24 条回复 • 2015-07-12 02:08:03 +08:00

bengol

2015-07-07 23:31:27 +08:00

好像是编程之美上的题吧

msg7086

2015-07-07 23:32:13 +08:00

花点时间想想更高效率的算法不行么？

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

2015-07-07 23:42:47 +08:00

@20015jjw 这个就是死算的办法...

msg7086

2015-07-07 23:45:47 +08:00

@20015jjw 不是 1 if '1' in str(i)，而是count。

yangqi

2015-07-08 00:02:29 +08:00

没看Hint说的是注意overflow么

20015jjw

2015-07-08 00:05:45 +08:00

@msg7086 啥？这个结果跑出来是对的啊.. 就是超时..

msg7086

2015-07-08 00:36:10 +08:00

@20015jjw count_digit_one(2147483647) == 2971027783 你看看你是不是这结果。

20015jjw

2015-07-08 00:46:38 +08:00

@msg7086 - - 目测是但是要跑两年因为这个办法是死算的 - - 你换个小于100k的数呢

msg7086

2015-07-08 00:53:34 +08:00

@20015jjw count_digit_one(76543) == 41015

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

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

2015-07-08 01:09:40 +08:00 via Android

@20015jjw 楼主这个应该是爆内存了。随便就要吃掉2G内存。

xhuuanniqege

2015-07-08 01:12:37 +08:00 via Android

数位dp

IwfWcf

2015-07-08 01:17:00 +08:00

不谢

https://gist.github.com/IwfWcf/cb01043159b359cf0f72

msg7086

2015-07-08 01:47:03 +08:00

40 / 40 test cases passed.
Status: Accepted
Runtime: 72 ms
Submitted: 1 hour, 3 minutes ago

https://gist.github.com/msg7086/4477fb824f1d7968178c

20015jjw

2015-07-08 06:06:28 +08:00

@msg7086 下学期学DP... 请问这是DP嘛...

msg7086

2015-07-08 07:38:34 +08:00

@20015jjw 我的代码并不是。

20015jjw

2015-07-09 05:33:42 +08:00

10 minutes ago Accepted 44 ms (submitted without the doctest) python

https://gist.github.com/20015jjw/74ab03818741aaa0e7bb

plantparknet

2015-07-09 12:44:39 +08:00

@20015jjw Great!

plantparknet

2015-07-09 12:45:01 +08:00

@msg7086
@IwfWcf
谢谢~~

ChangxuBlack

2015-07-10 18:38:26 +08:00

@20015jjw 我不知道你当时过了没，反正现在你的代码会超时

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

2015-07-12 02:08:03 +08:00

@20015jjw 啊我不会发图图中就是过了的截图...