Yanyg - SAN Software Engineer

Code - Lintcode Digit Counts问题成绩排名第一

领扣刷题,Digit Counts成绩排名第一,记录下。具体算法说明后补。

class Solution {
public:
    /**
     * @param k: An integer
     * @param n: An integer
     * @return: An integer denote the count of digit k in 1..n
     */
    int digitCounts(int k, int n) {
        // write your code here
        int xd, xbase, dbase = 1, div = 10, c = 0, k0penalty = 0;

        if (n%10 >= k)
                c += 1;

        while(div <= n) {
                xd = n%(div*10);
                xd /= div;
                xbase = div/10*dbase;

                c += xd*xbase;
                if (xd > k)
                        c += div;
                else if (xd == k)
                        c += (n%div) + 1;

                k0penalty += div;
                div *= 10;
                ++dbase;
        }

        if (k == 0)
                c -= k0penalty;

        return c;
    }
};

C实现和测试:

#include <stdio.h>

int countk(int n, int k)
{
        int i, v, c = 0;

        for (i = 0; i <= n; ++i) {
                v = i;
                do {
                        if (v%10 == k)
                                ++c;
                        v /= 10;
                } while (v);
        }

        return c;
}

int countk2(int n, int k)
{
        int xd, xbase, dbase = 1, div = 10, c = 0, k0penalty = 0;

        /*
         * Algorithms Description:
         */

        /* units digit (lowest digit) */
        if (n%10 >= k)
                c += 1;

        while(div <= n) {
                /* xd is the x's digits. e.g.: units, tens, hundreds, ... */
                xd = n%(div*10);
                xd /= div;
                xbase = div/10*dbase;

                c += xd*xbase;
                if (xd > k)
                        c += div;
                else if (xd == k)
                        c += (n%div) + 1;

                k0penalty += div; /* just used if @k == 0 */
                div *= 10;
                ++dbase;
        }

        if (k == 0)
                c -= k0penalty;

        return c;
}

int main(int argc, char *argv[argc])
{
        int i, j, k, c, c2 = countk2(12, 1);
        int ta[] = {0, 5, 10, 48, 94, 100, 102, 108, 110, 111, 115};
        int ka[] = {2, 0};

        if (c2 != 5) {
                fprintf(stderr, "countk(12, 1) expects 5, calc is %d\n", c2);
                return 1;
        }

        for (i = 0; i < 100000; ++i) {
                for (k = 0; k <= 9; ++k) {
                        c = countk2(i, k);
                        c2 = countk2(i, k);
                        if (c != c2) {
                                fprintf(stderr,
                                        "error: n(%d) k(%d) c(%d) c2(%d)\n",
                                        i, k, c, c2);
                                return 1;
                        }
                }
        }

        c = countk2(224, 2);
        fprintf(stdout, "countk(224, 2) is %d\n", c);

        return 0;
}