题目
233. 数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
- 示例 1：
输入：
n = 13
输出：6
- 示例 2：
输入：
n = 0
输出：0
- 提示：
0 <= n <= 10^9
解法1：
- 这种题其实就是找规律，类似于数学归纳法，找出一个计算通式可以在给出任意值时计算到目标结果
- 这道题我选择从高位往低位统计
- 首先找规律，得出不同位数1出现的次数：0位0次，1位（0-9）1次，2位（0-99）20次…
- 然后从高位开始，例如123从高位开始，依次处理 100、20、3。
- 100包含了0-99，有20个1，20包含了12个1，3包含了1个1
- 而123后面的23又为百位上的1多加了24个1，即100-123百位上共24个1，这个也要统计
class Solution {
public:int countDigitOne(int n) {if(!n) return 0;vector<int> count(10, 0);for(int i=1; i<=9; ++i){//统计不同位数的1出现的次数，0位0次，1位（0-9）1次，2位（0-99）20次...count[i]=i*pow(10, i-1);}// for(auto &ele:count) cout << ele << endl;int numDigits = (int)log10(n) + 1; // 获取数字的位数cout << numDigits << endl;int ans=0;for (int i = numDigits-1; i >= 0; i--) {//从高位开始统计int powerOf10 = (int)pow(10, i);int digit = n / powerOf10; // 获取当前位的数字if(digit==0) continue; //处理类似102这种情况中间的0ans+=digit*count[i];n %= powerOf10; // 移除当前位//如123，23让1多出现了24次（100-123）,而423是百位上的1固定出现了100次（101-199）digit<=1 ? ans=ans+n+1 : ans+=powerOf10; }return ans;}
};
解法2：
- 另一种解法是统计当前位上，1出现了多少次
- 当当前位上为0时，其出现1的次数由高位确定，如1203，十位上1出现的次数由十位以上确定，此处出现了12*10=120次
- 当当前位上为1时，其出现1的次数为高位+低位共同确定，如1213，出现了12*10+3+1=124次
- 当当前位上位2-9时，其出现1的次数也只由高位确定，如1243，十位上1出现次数为 (12+1)*10=130次
class Solution {
public:int countDigitOne(int n) {long currentDigit = 1; // 当前位的权值，最低位开始int high = n / 10, cur = n % 10, low = 0, count = 0; // 初始化高位、当前位、低位、结果个数while (high != 0 || cur != 0) {if (cur == 0) {// 当前位为0时，结果由高位决定count += high * currentDigit;} else if (cur == 1) {// 当前位为1时，结果由高位和低位共同决定count += high * currentDigit + low + 1;} else {// 当前位大于1时，结果由高位决定count += (high + 1) * currentDigit;}// 更新低位并跳到下一位low += cur * currentDigit;cur = high % 10;high /= 10;currentDigit *= 10; // 更新位数权值}return count;}
};
