LeetCode Q233: Number of Digit One (hard*)

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.

// 我的解法的基本思想就是考虑把某一个位数上的数字设成1后，看其他位置有多少种选择。然后把每个数字位取1而有的选择都加起来就可以了。比如，假设输入为392， 那么把个位设置成1之后，十位和百位的选择就有00~39共40种，所以个位上可以有40个1。然后把十位设置成1之后，百位和个位有 00 ~39共40中选择，注意这儿并不是32或者33种，因为当10位上的数设成1之后，319也是小于392的，所以个位可以取所有的0~9。然后百位设成1后，十位和个位有00~99，共100种选择。

所以加起来就是： 40 + 40 + 100 = 180 种可能性，也就是180 个 1。

// A number is divided into three parts, front, curDigit and rear. For example, if input is 123456789, when we are considering the situation if we set the digit 5 to 1, then:

front = 1234, curDigit = 5, rear = 6789, rearSize = 1000