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

[plantparknet]

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

[bengol]

好像是编程之美上的题吧

[msg7086]

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

[20015jjw]

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]

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

[msg7086]

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

[yangqi]

没看Hint说的是注意overflow么

[20015jjw]

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

[msg7086]

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

[20015jjw]

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

[msg7086]

@20015jjw count_digit_one(76543) == 41015

[20015jjw]

@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]

递归，举个例子 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]

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

[xhuuanniqege]

数位dp

[IwfWcf]

不谢

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

[msg7086]

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

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

[20015jjw]

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

[msg7086]

@20015jjw 我的代码并不是。

[20015jjw]

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

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

[plantparknet]

@20015jjw Great!