【LeetCode & 剑指offer刷题】特殊数题1：43 1~n整数中1出现的次数 (233. Number of Digit One )...
【LeetCode & 剑指offer刷题】特殊数题1：43 1~n整数中1出现的次数 (233. Number of Digit One )
【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
233. Number of Digit One
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example:
Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
思路：
/*
比如1在十位数时
->100 10 个
->200 20 个
...
->1600 160个 （最后两位小于10时）
->161x 160 + x + 1个 （10 ≤ 最后两位 < 20）
->1650 160 + 10 个 （≥ 20）
*/
class Solution
{
public:
int countDigitOne(int n)
{
int counter = 0;
for(long i = 1; i<=n; i*=10) //i为1所在位数比如上例中的10，divider为除数，比如上例中的100，remainder为n除以divider的余数，比如上例中的后两位数
{
long divider = i * 10; //防止n过大导致i*10溢出
int remainder = n%divider;
if(remainder >= 2*i) counter += (n/divider) * i + i;
else if(remainder >= i && remainder < 2*i) counter += (n/divider) * i + (n%divider) - i + 1;
else counter += (n/divider)*i;
}
return counter;
}
};