【数学专题】剑指 Offer 43. 1～n 整数中 1 出现的次数-跟着帅地玩副业，开拓第二曲线PlayOffer

Sheng 永久会员 2023年9月15日上午12:51

按照个十百千万计算，每一位和1比较，计算对应的值。首先搞清楚0-9 0-99 0-999 0-9999-中1的个数的规律。

        long res = 0;
        //我觉得个位数需要特殊处理
        if(n % 10 >= 1) {
            res = 1;
        }

        //大于10的数
        long a = 0;//某一位的数字
        long ten = 10;//每次乘以10
        long tmp = 0;//临时结果保存
        //r(0~9) = 1
        //r(0~99) = r(10~99) + r(0~9) = r(0~9)*9  (10~99中个位共这么多1) 
        //                          + 10(10~19中十位共10个1) + r(0~9)
        //                            = r(0~9)*10 + 10
        long cal = 1;//记录(0~9  0~99  0~999 0~9999)中1的个数
        while (n / ten != 0) {
            a = n / ten % 10;
            if(a > 1) {
                tmp = a * cal + ten;
            }
            else if(a == 1) {
                tmp = n % ten + cal + 1; //
            }
            else {
                tmp = 0;
            }
            res += tmp;
            cal = cal * 10 + ten;//r(0~9  0~99  0~999)
            ten = ten * 10;
        }
        return (int)res;

0 赞同 0 条回复

sc_Yang 普通 2023年9月10日下午11:07

// 数学结论，每多一个1000，则百位为1的次数多100次。
// 若数字比1000小时，分情况讨论，小于100，大于等于100小于200，大于200小于1000时
// 小于100时，百位出现1的次数为0
// 大于等于100小于200时，百位出现1的次数为n - 100 + 1
// 大于200小于1000时，百位出现1的次数为固定为100
// 上面规律可用自变量代替1000，从而得出各位置的规律公式
class Solution {
public:
    int countDigitOne(int n) {
        long long mulk = 1;
        int res = 0;
        for(int i=0; n>=mulk; i++){
            res = res + (n/(mulk*10))*mulk + min(max(n%(mulk*10)-mulk+1, 0LL), mulk);
            mulk *= 10;
        }
        return res;
    }
};

0 赞同 0 条回复

小肸永久会员 2023年9月7日下午6:45

class Solution {
    //对于1234，统计百位上的1的个数，其中[000,999]中[100~199]正好有100个1
    //所以对于一个数字，有几个1000，百位上至少就有几个*100个1
    //对于234而言，即对于1000取余的余数x而言
    //x<100，+0
    //100<=x<200, +(x - 100 + 1)
    //x>=200, +100
    //时间复杂度O(logN),空间复杂度O(1)
    public int countDigitOne(int n) {
        int baseVal = 10;
        long tmp = 1;
        int res = 0;
        while (tmp <= n) {
            res += (n / (tmp * 10) * tmp);
            long remainder = n % (tmp * 10);
            if (remainder < tmp) {
                res += 0;
            } else if (remainder >= tmp && remainder < tmp * 2){
                res += (remainder - tmp + 1);
            } else {
                res += tmp;
            }
            tmp *= 10;
        }
        return res;
    }
}

0 赞同 0 条回复

c 普通 2023年9月3日下午8:14

题解学习

class Solution {
    public int countDigitOne(int n) {
        long m = 1;
        int res = 0;
        for(int i = 0;n>=m;i++){
            res+=(n/(m*10))*m+Math.min(Math.max((n%(m*10)-m+1),0),m);
            m*=10;
        }
        return res;
    }
}

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月3日下午1:57

class Solution {
    public int countDigitOne(int n) {
        //个位数出现1的次数+百位数出现1的次数+...+n位数出现1的次数
        long bit = 1;
        long sum = 0;
        while(bit <= n) {
            long cur = (n/bit) % 10; // 第bit位上的数字
            long low = n % bit;
            long high = n / bit / 10;

            if (cur > 1) {
                sum += (high + 1) * bit;
            } else if (cur == 1) {
                sum += (high * bit) + (1 + low);
            } else {
                sum += high * bit;
            }
            bit = bit * 10;
        }
        return (int)sum;
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月3日上午9:57

1、暴力法（超时了）

class Solution {
    public int countDigitOne(int n) {
        int res = 0;
        for(int i=1; i<=n; i++){
            for(int j=i; j>0; j=j/10){
                if(j%10 == 1){
                    res++;
                }
            }
        }
        return res;
    }
}

2、

class Solution {
    public int countDigitOne(int n) {
        int res = 0;
        long pow = 1;
        while(pow <= n){
            int high =  (int)(n / pow);
            int low = (int)(n % pow);
            int cur = high % 10;
            high = high /10;
            if(cur > 1){
                res += ((high + 1) * pow);
            }else if(cur == 1){
                res += (high*pow + low + 1);
            }else {
                res += high*pow;
            }
            pow *= 10;
        }
        return res;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月1日下午8:39

// 个位出现1的次数，十位出现1的次数，一直到n的位数
class Solution {
public:
    int countDigitOne(int n) {
        long long sum = 0,bit = 1;
        while(bit<=n)
        {
            int low = n%bit;
            int hight = n/bit/10;
            int cur = (n/bit)%10;
            if(cur==0)
                sum+=hight*bit;
            else if(cur == 1)
                 sum+=hight*bit + low + 1;

            else sum+=(hight+1)*bit;
            bit*=10;
        }

        return sum;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年9月1日下午3:16

时间复杂度O(logN), 空间复杂度O(1)

class Solution {
public:
    int countDigitOne(int n) {

        long bit = 1;
        long result = 0;
        while (bit <= n) {
            int cur = (n / bit) % 10;
            int high = (n / bit) / 10;
            int low = n % bit;

            if (cur > 1) {
                result += (high + 1) * bit;
            } else if (cur == 1) {
                result += high * bit + low + 1;
            } else {
                result += high * bit;
            }
            bit *= 10;
        }
        return int(result);
    }
};

0 赞同 0 条回复

【数学专题】剑指 Offer 43. 1～n 整数中 1 出现的次数

共以下 8 个回答

# 回答此问题取消回复

【数学专题】剑指 Offer 43. 1～n 整数中 1 出现的次数

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复