由买买提看人间百态

topics

全部话题 - 话题: powerof10
(共0页)
S*******C
发帖数: 822
1
一道career cup、leetcode的原题变种,也是lintcode原题,但目前没有发现无bug的
最优解,所有中国人都做错了,或者明显是非最优解
leetcode上是
Number of Digit One My Submissions Question
Total Accepted: 12345 Total Submissions: 55909 Difficulty: Medium
Given an integer n, count the total number of digit 1 appearing in all non-
negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12,
13.
https://leetcode.com/problems/number-of-digit-one/
最精简最优解是
public int co... 阅读全帖
S*******C
发帖数: 822
2
想出来了
最优解是
public int digitCounts(int k, int n) {
int res = k == 0 ? 1 : 0;
for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
long left = n / powerOf10, right = n % powerOf10;
if (k != 0)
res += (left + 9 - k) / 10 * powerOf10;
else
res += left / 10 * powerOf10;
if (left % 10 == k && k > 0)
res += right + 1;
}
return res;
}
你可以用Brute force的解法来测试
public int ... 阅读全帖
(共0页)