讨论一道所有人做的都不好的lintcode题目

http://www.mitbbs.com/article_t/JobHunting/33094833.html

发信人: SpringMVC (Tutorial), 信区: JobHunting
标  题: 讨论一道所有人做的都不好的lintcode题目
发信站: BBS 未名空间站 (Mon Nov 16 01:04:21 2015, 美东)

一道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 countDigitOne(int n) {
        int res = 0;
        for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
            long left = n / powerOf10, right = n % powerOf10;
            res += (left + 8) / 10 * powerOf10;
            if (left % 10 == 1)
                res += right + 1;
        }
        return res;
    }




career cup上是8.4 Write a method to count the number of 2s between 0 and n
最优解是
    public int countDigitTwo(int n) {
        int res = 0;
        for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
            long left = n / powerOf10, right = n % powerOf10;
            res += (left + 7) / 10 * powerOf10;
            if(left % 10 == 2)
                res += right + 1;
        }
        return res;
    }




lintcode上的变种是
Digit Counts
Count the number of k's between 0 and n. k can be 0 - 9.
Example: if n=12, in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have
FIVE 1's (1, 10, 11, 12)
http://lintcode.com/en/problem/digit-counts/

用同样的方法能通过绝大部分test case，但当k=0时答案错误
public int digitCounts(int k, int n) {
        int res = 0;
        for (long powerOf10 = 1; powerOf10 <= n; powerOf10 *= 10) {
            long left = n / powerOf10, right = n % powerOf10;
            res += (left + 9 - k) / 10 * powerOf10;
            if(left % 10 == k && k > 0)
                res += right + 1;
        }
        return res;
    }

这答案该怎么改？