【剑指Offer】T43 1~n整数中1出现的次数

求出 1~13 的整数中 1 出现的次数, 并算出 100~1300 的整数中 1 出现的次数?为此他特别数了一下 1~13 中包含 1 的数字有 1、10、11、12、13 因此共出现 6 次, 但是对于后面问题他就没辙了。ACMer 希望你们帮帮他, 并把问题更加普遍化, 可以很快的求出任意非负整数区间中 1 出现的次数(从 1 到 n 中 1 出现的次数)。

思路 1:遍历整个数组,并除 10 求余数。

int NumberOf1Between1AndN_Solution(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int sumOfOne = 0;
        int k = i;
        while(k){
            if(k % 10 == 1)
                sumOfOne++;
            k = k / 10;
        }
        sum+=sumOfOne;
    }
    return sum;
}

本文链接:https://ariser.cn/index.php/archives/392/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!