九号球普通 2023年11月23日上午8:42

“`java

class Solution {
public int digitOneInNumber(int num) {
int res = 0;
//所有位上1的个数和为1出现的次数
int bit = 1;
int high = num/10;
int low = 0;
int cur = num%10;
while (high != 0 || cur != 0) {
if (cur 0) {
res += high * bit;
} else if (cur 1) {
res += high * bit + low + 1;
} else {
res += (high + 1) * bit;
}

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

}

0 赞同 0 条回复

招舟子普通 2023年9月7日下午4:14

class Solution {
public int countDigitOne(int n) {
long count=0;
long bit = 1;
while(bit<=n){
long cur = (n/bit)%10;
long high=n/bit/10;
long low =n%bit;
if(cur>1){
count+=(high+1)bit;
}else if(cur1){
count += (highbit)+(low+1);
}else{
count += highbit;
}
bit = bit10;
}
return (int)count;
}
}
时间复杂度O（logn）
空间为o（1）

0 赞同 0 条回复

mpweixin用户普通 2023年8月1日上午10:00

java
class Solution {
    public int countDigitOne(int n) {
        //思路：分别找到1-n的个位、十位、百位...的1的出现次数相加，即为1出现的总次数
        //分为三种情况，当当前位为0时，当前位为1时，当前位为2,3,4...9时的情况
        int digit = 1; //位因子，表示当前位
        int high = n / 10; //n的高位
        int low = 0;      //n的低位
        int cur = n % 10; //当前位
        int res = 0;    

        while(high != 0 || cur != 0) {
            if(cur == 0) {
                res += high * digit;
            } else if(cur == 1) {
                res = res + high * digit + low + 1;
            } else {
                res += (high + 1) * digit;
            }

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

空间复杂度O(N), 时间复杂度是n的位数，即log10N O(logN)

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:31

C++实现

“`C++
int countOnes(int n) {
int count = 0;
for (int i = 1; i <= n; i++) { int num = i; while (num > 0) {
if (num % 10 == 1) {
count++;
}
num /= 10;
}
}
return count;
}
“`

0 赞同 0 条回复

憨憨永久会员 2023年7月19日下午12:26

找规律

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;
    }
}

0 赞同 0 条回复

屠龙手段普通 2023年7月17日下午8:05

数位dp

class Solution {
public:
    int countDigitOne(int n) {
        if(n == 0) return 0;
        int digit = log10(n) + 1;
        vector<vector<long long>> dp(digit + 1, vector<long long>(2));
        dp[1][0] = n % 10 >= 1 ? 1:0; // 1至i位中1的个数
        dp[1][1] = 1;   // 最高位为9时0至i位中1的个数
        for(int i = 2; i <= digit; i++){
            int k = n / (int)pow(10, i - 1) % 10;
            dp[i][0] = k * dp[i-1][1] + dp[i-1][0]; // 当前位为0时
            if(k == 1) dp[i][0] += n % (int)pow(10, i - 1) + 1; // 当前位为1时
            else if (k > 1) dp[i][0] += (int)pow(10, i - 1); // 当前位大于1时
            dp[i][1] = 10 * dp[i-1][1] + (int)pow(10, i - 1);
        }
        return dp[digit][0];
    }
};

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月16日下午9:10

找规律

class Solution {
    public int countDigitOne(int n) {
        int digit=1,res=0;
        int high=n/10,cur=n%10,low=0;
        while(high!=0||cur!=0){
            if(cur==0)
                res+=high*digit;
            else if(cur==1)
                res+=high*digit+low+1;
            else
                res+=(high+1)*digit;
            low+=cur*digit;
            cur=high%10;
            high/=10;
            digit*=10;
        }
        return res;
    }
}

0 赞同 0 条回复

江畅普通 2023年7月16日上午10:59

// 1～n 整数中 1 出现的次数
// 时间复杂度 O(logN)
// 空间复杂度 O(1)
class Solution {
public:
    int countDigitOne(int n) {
        int       high  = n / 10;
        int       cur   = n % 10;
        int       low   = 0;
        long long res   = 0;
        long long digit = 1;

        while (high || cur) {
            if (cur == 0) {
                res += high * digit;
            }
            else if (cur == 1) {
                res += high * digit + low + 1;
            }
            else {
                res += (high + 1) * digit;
            }
            digit *= 10;
            cur = high % 10;
            high /= 10;
            low = n % digit;
        }
        return res;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月16日上午2:17

class Solution:
    def countDigitOne(self, n: int) -> int:
        bit = 1
        cntOne = 0

        while bit <= n:
            cur = n // bit % 10
            low = n % bit
            high = n // (bit * 10)

            if cur > 1:
                cntOne += (high + 1) * bit
            elif cur == 1:
                cntOne += high * bit + (low + 1)
            else:
                cntOne += high * bit

            bit *= 10

        return cntOne

分类讨论

0 赞同 0 条回复

BOZ 普通 2023年7月15日下午4:25

【思路】将一个数字的每一位拆分，分别去计算每一位的1的个数
【复杂度】时间复杂度O(logn)，空间O(1)

class Solution {
public:
    int countDigitOne(int n) {
        int n_ = n;
        int sum = 0, dsum = 0, dpow = 1;
        while (n) {
            char c = n % 10;
            sum += dsum * c;
            if (c) sum += (c == 1)? (n_ % dpow + 1): dpow;
            if (n / 10 == 0) break;
            dsum = dpow + dsum * 10; 
            dpow *= 10;
            n /= 10;
        };
        return sum;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月14日下午10:23

官解
时间：O(logn)
空间：O(1)

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

0 赞同 0 条回复

Dsjh 普通 2023年7月11日上午9:30

MY

每一位上的1相加

class Solution {
public:
    int countDigitOne(int n) {
        long b=1;      
        int ans=0;
        while(b<=n){
            int cur = n/b%10;
            if(cur>1)
                ans += (n/(b*10)+1) * b;
            else if(cur==1)
                ans += n/(b*10)*b+(1+n%b);
            else
                ans += n/(b*10)*b;
            b=b*10;
        }
        return ans;
    }
};

0 赞同 0 条回复

局外人普通 2023年7月10日下午9:34

思路：根据高低位和当前位的关系，计算每位对1出现的数量
时间复杂度：O(logn) 空间复杂度：O(1)

class Solution {
    public int countDigitOne(int n) {
        int dight=1, res=0;
        int high=n/10, cur=n%10, low=0;
        while(high!=0 || cur!=0){
            if(cur==0)  res += high*dight;
            if(cur==1)  res += high*dight + low + 1;
            if(cur>1)   res += high*dight + dight;

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

0 赞同 0 条回复

Vow the vow。普通 2023年7月10日上午11:13

竖向考虑每一位的情况。

public int countDigitOne(int n) {
        //当前数字为cur时，digit位出现为1的次数
        int high = n /10, cur = n % 10, low = 0;
        int digit = 1; // 从个位开始算
        int count = 0;
        while(high != 0 || cur != 0){
            if(cur == 0){ //高位:00-(high-1)，低位:0-(digit-1)
                count += high * digit;
            }else if(cur == 1){ //cur=0的情况 + (高位固定，cur=1，低位变化)
                count += ((high * digit) + (low + 1));
            }else{  // cur > 1时,就是cur = 0,以及cur=1时,低位0-(digit-1)
                count += ((high * digit) + digit);
            }
            low += cur * digit;
            cur = high %  10;
            high /= 10;
            digit *= 10;
        }
        return count;
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月9日下午9:03

public int countDigitOne(int n) {
        long count = 0;
        for(long i = 1;i <= n;i = i * 10){    //1 10 100 1000
            //依次遍历每一位
            long cur = (n / i) % 10;
            long high = n / i / 10;
            long low = n % i;

            if(cur == 0){
                count += high * i;
            }
            if(cur == 1){
                count += (high * i) + (1 + low);
            }
            if(cur > 1){
                count += (high + 1) * i;
            }

        }
        return (int)count;
    }

0 赞同 0 条回复

yxy 普通 2023年7月9日下午5:13

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

class Solution {
public:
    int countDigitOne(int n) {
        if(n==0) return 0;
        if(n<10) return 1;
        long c_00 = 1; // 若c在百位则为100，在千位则为100，初始为1
        int total=0;
        while(1)
        {
            int de = n%c_00;
            int abc = n/c_00;
            int c = abc%10;
            int ab = abc/10;
            //cout<<c_00<<" "<<ab<<" "<<c<<" "<<de<<endl;
            total+=ab*c_00;
            if(c==0) total+=0;
            else if(c==1) total+=de+1;
            else total+=c_00;
            c_00*=10; // 完成上述对ab，c，de提取后再将c_00扩大
            if(ab==0)
            {
                break;
            }
        }
        return total;
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月9日下午4:44

public int countDigitOne(int n) {
        // 几个公示 计算当前bit 1的个数
        // cur > 1 => (high + 1) * bit
        // cur == 1 =>  (high * bit) + (1 + low)
        // cur = 0 => high * bit
        int res = 0;
        int high = n / 10;
        int bit = 1; // 从个位开始
        int cur = n % 10; // 跟随bit位数
        int low = 0;    // 一开始low比个位小，所以是无
        while(bit <= n) {
            if(cur == 0) {
                res += high * bit;
            } else if(cur == 1) {
                res += (high * bit) + (1 + low);
            } else { // cur > 1情况
                res += high * bit + bit;
            }
            low += cur * bit;
            cur = high % 10;
            high = high / 10;
            bit = bit * 10;
        }
        return res;
    }

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

0 赞同 0 条回复

张开怀普通 2023年7月9日下午4:08

class Solution{
public:
       int countDigitOne(int n){
              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 +=(hign+1)*bit;
                     }else if(cur == 1){
                            sum += high *bit + low +1;
                     }else{
                            sum += high *bit;
                     }
                     bit *=10;
              }
              return sum;
       }
};

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

0 赞同 0 条回复

Yodl. 普通 2023年7月9日下午2:30

//法一 数位dp 时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
public:
    int countDigitOne(int n) {
        long base = 1;
        int res = 0;
        while (base <= n) {
            int low = n % base;
            int high = n / base;
            int cur = high % 10;
            high /= 10;
            // 此时数据按位构成high cur low三部分, 如例一中high = 3101, cur = 6, low = 92
            if (cur > 1) res += (high + 1) * base; // base就是举例中的100 1000 10000
            else if (cur == 1) res += (low + 1) + high * base;
            else res += high * base;
            base *= 10;
        }
        return res;
    }
};

//法二 暴力法超时
class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            count += countOne(i);
        }
        return count;
    }
    int countOne(int n) {
        int num = 0;
        while (n) {
            if (n % 10 == 1) {
                num++;
            }
            n /= 10;
        }
        return num;
    }
};

0 赞同 0 条回复

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

共以下 19 个回答

MY

# 回答此问题取消回复

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

共以下 19 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复