题目描述 牛客网

• 输入一个整数 n，求 1 ~ n 这 n 个整数的十进制表示中 1 出现的次数
• 例如， 输入 12， 1 ~ 12 这些整数中包含 1 的数字有 1， 10， 11，12； 1 共计出现了 5 次

题目解读

• 剑指Offer 221
• 思路一，常规方法，不考虑时间效率
• 思路二，看牛客讨论区的方法，很优秀，点我

代码

• 思路一，常规方法，不考虑时间效率

#include<iostream>
using namespace std;

class Solution {
public:
    int numberof1(int x){
        int len = 0;

        while(x != 0){
            if(x%10 == 1){
                len ++;
            }
            x /= 10;
        }
        return len;
    }

    int NumberOf1Between1AndN_Solution(int n)
    {
        int numof1 = 0;
        for(int i=1; i <= n; i++){
            numof1 += numberof1(i);
        } 
        return numof1;   
    }
};

int main(){
    Solution ss;
    
    cout<<ss.NumberOf1Between1AndN_Solution(12)<<endl;
}

• 思路二，看牛客讨论区的方法，很优秀，点我

主要思路：设定整数点（如1、10、100、1000、等10的倍数）作为位置点 i（对应n的个位、十位、百位、千位等），分别对每个数位上有多少包含1的点进行分析。根据设定的整数位置，对n进行分割，分为两部分，高位 a = n/i，低位 b = n%i. 下面是三个实例。
1、当 i 表示百位，且百位对应的数字>=2时，如 n=31456，i=100，则 a = 314, b = 56，此时百位为1的次数有 a/10 + 1= 314/10 + 1 = 32（最高两位0~31），每一次都包含100个连续的点，即共有( a / 10 + 1 ) * 100 个点的百位为 1

2、当 i 表示百位，且百位对应的数字为 1 时，如 n=31156，i=100，则 a=311, b=56，此时百位对应的就是1，则共有 a / 10 (最高两位0-30)次包含 100 个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共 ( a / 10 ) * 100 + (b + 1)，这些点百位对应为1

3、当i表示百位，且百位对应的数为0, 如n = 31056, i = 100，则a=310, b=56，此时百位为1的次数有a/10=31（最高两位0~30）， 所有点加起来共 ( a / 10 ) * 100

综合上述三种情况，我们就可以知道 百位为 1 的时候共有多少个数字了，，其他位的情况类似可得

#include<iostream>
using namespace std;

class Solution {
public:

    int NumberOf1Between1AndN_Solution(int n)
    {
        int ones = 0;
        for(int i=1; i <= n; i*=10){
            int a= n / i;
            int b= n % i;

            if(a% 10 == 0){
                ones += (a / 10) * i;
            }
            else if(a% 10 == 1){
                ones += (a / 10) * i + ( b + 1);
            }
            else{
                ones += ((a / 10) + 1) * i;
            }
        }
        return ones;
    }
};

int main(){
    Solution ss;
    cout<<ss.NumberOf1Between1AndN_Solution(12)<<endl;
}

总结展望

• 讲道理，第二种方法应该比第一种要快的，但是牛客运行时间竟然一样，真是服气，应该是牛客测试数据量小吧.