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

北辰普通 2023年8月4日上午8:57

class Solution {
    public int countDigitOne(int n) {
            int bit = 1;
            int sum = 0;
            for(int i=weishu-1;i>=0;i--) {
                int low = n%bit;
                int high = n/bit;
                int cur = high%10;
                high /= 10;
                if(cur >1) {
                    sum+=(high+1)*bit;
                }else if(cur ==1){
                    sum+=high*bit+(low+1);
                }else {
                    sum+=high*bit;
                }
                bit = 10*bit;
            }
            return sum;
    }
}

时间复杂度：O（logn）
空间复杂度：O（1）

0 赞同 0 条回复

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

c++ 运用数论解题
class Solution {
public:
int cuttingRope(int n)
{
if(n1||n2)
return 1;
if(n3)
return 2;
int s=1;
while(n>4)
s=3,n-=3;
return sn;

};

0 赞同 0 条回复

#00456B 普通 2023年8月2日下午10:38

class Solution {
public:
    int countDigitOne(int n) {
        //从个位开始逐个向前统计1的个数
        long base = 1;//从个位开始，且这里要用long，因为可能n==INT_MAX，base还要进一位
        int sum = 0;
        while(base <= n){
            //以3101592为例，假设现在的base为100，即在百位上统计1的个数
            //将数字拆为[a...][cur][b...]
            int a = n/base/10;
            int cur = n/base%10;
            int b = n%base;
            if(cur > 1){
                //  [3101]  5  [92]
                // [0-3101] 1 [0-99]
                //   (a+1) * (base)
                sum += (a+1)*base;
            }
            else if(cur == 1){
                //两种情况
                //   [310] 1 [592]
                //1. 0-309 1 0-999
                //   a * base
                //2.  310  1 0-592
                //   1 * (b+1)
                sum += a*base + (b+1);
            }
            else{// cur == 0
                //[31] 0 [1592]
                //[0-30] 1 [0-9999]
                // a * base
                sum += a*base;
            }
            base*=10;//进位
        }
        return sum;
    }
};

0 赞同 0 条回复

Marshan 普通 2023年8月1日下午9:12

如果没看过,感觉很难想到(只想到暴力解)

class Solution {
public:
    int countDigitOne(int n) {
        // cur = (n / bit) % 10
        // low = n % bit
        // high = n / bit / 10
        // cur > 1 : (high + 1) * bit
        // cur == 1 : (high * bit) * (low + 1)
        // cur == 0 : high * bit

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

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

0 赞同 0 条回复

Mby 普通 2023年7月31日下午11:31

class Solution {
    public int countDigitOne(int n) {
        long bit = 1;
        long sum = 0;
        while(bit <= n){
            long cur = (n/bit)%10;
            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;
//
    }
}

时间复杂度：O(logn)
额外空间复杂度：O(1)

0 赞同 0 条回复

NullPointerException 普通 2023年7月31日下午5:58

class Solution {
public int countDigitOne(int n) {
// 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
// 几个公示
// cur > 1 => (high + 1) * bit
// cur 1 => (high * bit) + (1 + low)
// cur = 0 => high * bit

    long bit = 1;
    long sum = 0;
    while(bit <= n){
        long cur = (n/bit)%10;
        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年7月28日下午10:11

7.28
Day19：下面是代码

class Solution {
    public int countDigitOne(int n) {
        //计算数字1——countDigitOne
        //研究数学规律。
        int high = n / 10, cur = n % 10, low = 0, digit = 1, res = 0;
        while(high != 0 || cur != 0){
            if(cur == 0) res += digit * high;
            else if(cur == 1) res += digit * high + low + 1;
            else res += digit * (high + 1);

            low += cur * digit;
            cur = high % 10;
            high /= 10; 
            digit *= 10;
        }
        return res;
    }
}

0 赞同 0 条回复

CKX 普通 2023年7月28日下午3:20

func countDigitOne(n int) int {
    //三种情况
    //1. cur > 1 ==> (high + 1) * bit
    //2. cur = 1 ==> (high*bit) + (1+low)
    //3. cur = 0 ==>  high * bit

    //算数位
    var bit int64 = 1
    //个数
    var sum int64 = 0
    for bit <= int64(n) {
        //当前位的值
        cur := (int64(n) / bit) % 10
        low := int64(n) % bit
        high := int64(n) / (bit * 10)

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

0 赞同 0 条回复

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

共以下 8 个回答

# 回答此问题取消回复

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

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复