题解 | #整数中1出现的次数#
整数中1出现的次数（从1到n整数中1出现的次数）
https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6
前言
看了前行者一些大佬以及官方的数学推导方法，人麻了，自己推导了一番没找出来规律，但是，也还能能过，就就非常意外，菜鸡下面可以看看我这个代码简单，思路也简单的解题方法，他们数学推导的时间复杂度能够优化到O（log n），我这个是也能解决问题，但是O（n）的。
思路
要判断1-n中所有的数中1的个数，那就把这些数遍历一遍吧，写个函数isOne计算这个数中1的个数，因为题目最大也就30000所以每次计算最多也就5次，最后把所有的数计算的结果加起来就OK，是不是很简单！
当然，还可以优化一点，比如，每次循环的2-9这部分可以跳过不算。
在20-30，30-40...这些数之间每次必然只有一次1；
在120-130，130-140...这些数之间每次必然只有一次1加上本身自带的10次，也就是11次1；
在1200-1300，1300-1400..这些数之间...
....
当时是这样想的优化，每次转角比如11，111的部分当然也有规律，但是，算法菜鸡得CPU已经麻木了，能O（n）过就没继续弄了也没优化...，如果有大佬能指点一下，欢迎评论优化的方法！
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n) {
int ans=0;
for(int i=1;i<=n;i++){
ans+=isOne(i);
}
return ans;
}
int isOne(int n){
int ans=0;
while(n>0){
if(n%10 ==1) ans++;
n=n/10;
}
return ans;
}
};
投递华为等公司10个岗位 >