题目
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12 输出：5
示例 2：
输入：n = 13 输出：6
解题
方法一：暴力（超时）
class Solution { private: int countOne(int n){ string str=to_string(n); int res=0; for(char c:str){ if(c=='1') res++; } return res; } public: int countDigitOne(int n) { int res=0; for(int i=1;i<=n;i++){ res+=countOne(i); } return res; } };
方法二：
class Solution { public: int countDigitOne(int n) { int high=n;//高位 int low=0;//低位 int cur=0;//当前所在位的值 int count=0;//1出现得次数 long num=1;//当前位的位因子(num*=10用int会溢出) while(high||cur){ cur=high%10; high/=10; if(cur==0) count+=high*num; else if(cur==1) count+=high*num+low+1; else count+=high*num+num; low=cur*num+low; num*=10; } return count; } };
