43.1~n整数中1出现的次数

raylan.chen大约 1 分钟

class Solution {
    public int digitOneInNumber(int num) {
        int digit = 1, res = 0;
        int high = num / 10, cur = num % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/229751/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解的个人理解思路：

数学题

注：题目求解的是小于等于 num 的非负整数中1的个数，101 ==> 算 2个

拿 120 举例，

考虑个位数为1的情况，

120 --> 111 --> xx 1
00 1，01 1，02 1，03 1，04 1，...，10 1，11 1
res = 12（这里只记录整数的个数，111 ==> 算1个）
high = 12， cur = 0， low = 0， digit = 1
res = high * digit

考虑十位数为1的情况，

120 --> 119 --> x 1 x
0 1 0，0 1 1，0 1 2，0 1 3，0 1 4，...，1 1 8，1 1 9
res = 20
high = 1，cur = 2， low = 0， digit = 10
res = (high + 1) * digit

考虑百位数为1的情况，

120 --> 120 --> 1 xx
1 00，1 01，1 02，1 03，...，1 19，1 20
res = 21
high = 0， cur = 1， low = 20， digit = 100
res = high * digit + low + 1

43.1~n整数中1出现的次数

43.1~n整数中1出现的次数

参考链接

优秀题解