算法1

(暴力枚举) $O(n^2)$

• 1 ~ n 每一个数的包含1的个数

C++ 代码

class Solution {
    int numof1(int n){
         int num=0;
         while(n){
             if(n%10==1)
                 num++;
             n/=10;
         }
         return num;
     }
 public:
     int numberOf1Between1AndN_Solution(int n)
     {
         //方法１　直接求余数
         int num=0;
         for(int i=1;i<=n;i++){
             num+=numof1(i);
         }
         return num;


     }
};

算法2

(分段考虑)

参考：https://www.acwing.com/solution/acwing/content/1424/

C++ 代码

class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        int count = 0;
        for (int i = 1; i <= n; i *= 10) {
            int a = n / i,b = n % i;
            count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0);
        }
        return count;
    }