剑指43：1~n整数中1出现的次数

传送门

nowcoder
leetcode

题目描述

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数。
例如， 1~13 中包含 1 的数字有 1、10、11、12、13，共出现 6 次。

C++ 代码 - nowcoder

/*
    根据最高位是否为 1，分两种情况处理。
    每种情况下分段处理，即 0-999, 1000-1999, ..., 剩余部分。
    high 为最高位，pow 为最高位权重。
    
    1. 若最高位是 1，则最高位的 1 的个数为 last + 1（1000-1234）
    除去最高位，即 0-999 中 1 的个数为 1 * countDigitOne(pow-1)
    剩余部分 1 的个数为 countDigitOne(last)
    2. 若最高位不是 1，则最高位的 1 的个数为 pow（1000-1999）
    除去最高位，即 0-999，1000-1999 中 1 的个数为 high * countDigitOne(pow-1)
    剩余部分 1 的个数为 countDigitOne(last)

    差别仅在最高位 1 的个数，合并处理两种情况。
*/
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if (n <= 0) return 0;
        if (n < 10) return 1;
        if (n == 10) return 2;

        int pow = 1, high = n;
        while (high >= 10) {
            high = high / 10;
            pow *= 10;
        }
        int last = n - high * pow; // 除去最高位的数字
        int cnt = high == 1 ? last + 1 : pow;
        return cnt + high * NumberOf1Between1AndN_Solution(pow - 1) +
            NumberOf1Between1AndN_Solution(last);
    }
};

C++ 代码 - leetcode

/*
    根据最高位是否为 1，分两种情况处理。
    每种情况下分段处理，即 0-999, 1000-1999, ..., 剩余部分。
*/
class Solution {
public:
    int digitOneInNumber(int n) {
        if (n <= 0) return 0;
        else if (n < 10) return 1;
        else if (n == 10) return 2;

        int pow = 1, high = n;
        while (high >= 10) {
            high = high / 10;
            pow *= 10;
        }

        int last = n - high * pow; // 除去最高位的数字
        int cnt = high == 1 ? last + 1 : pow;
        return cnt + high * digitOneInNumber(pow - 1) +
            digitOneInNumber(last);
    }
};