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

宁永久会员 2023年3月16日下午8:22

class Solution {
    public int countDigitOne(int n) {
        //每一位每一位地统计
        long sum = 0;
        long bit = 1;
        while(bit <= n){
            long low = n % bit;
            long cur = (n / bit) % 10;
            long high = n / bit / 10;
            if(cur == 1){
                sum += (high * bit + low + 1);
            } else if(cur < 1){
                sum += high * bit;
            } else{
                sum += (high + 1) * bit;
            }
            bit *= 10;
        }
        return (int)sum;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月12日下午2:29

def countDigitOne(n):
    # bit代表位数
    bit = 1
    # cur代表当前位的数值
    cur = 0
    # cur后的值
    low = 0
    # cur前的值
    hight = 0
    res = 0
    while bit < n:
        # 更新当前位、前、后的值
        cur = (n // bit) % 10
        low = n % bit
        high= n // bit // 10

        if cur > 1:
            res = res + (high + 1) * bit
        elif cur == 1:
            res += (high * bit + (1 + low))
        elif cur == 0:
            res += (high * bit)

        bit = bit * 10
    return res

0 赞同 0 条回复

lucca 普通 2023年1月9日下午12:04

求每一位的1的个数

时间复杂度 O(len(N))
空间复杂度 O(1)

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

0 赞同 0 条回复

symbol 普通 2022年12月2日下午9:20

func countDigitOne(n int) (ans int) {
    for k, mulk := 0, 1; n >= mulk; k++ {//循环遍历
        ans += (n/(mulk*10))*mulk + min(max(n%(mulk*10)-mulk+1, 0), mulk)
        mulk *= 10
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

0 赞同 0 条回复

xye 普通 2022年11月27日下午9:20

func countDigitOne(n int) int {
    cur := n % 10
    high := n / 10
    low := 0
    digit := 1
    res := 0
    for cur != 0 || high != 0 {
        if cur == 0 {
            res += digit * high
        }else if cur == 1 {
            res += digit * high + low + 1
        }else{
            res += (high + 1) * digit
        }
        low += cur * digit
        cur = high % 10
        high /= 10
        digit *= 10
    }
    return res
}

时间O(lgN) 空间O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年11月25日上午10:09

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

class Solution:
    def countDigitOne(self, n: int) -> int:
        # 分别计算每个位置上为1的个数再相加
        base = 1
        sum = 0
        while base <= n:
            a = n // base // 10
            b = n % base
            cur = n // base % 10
            if cur > 1:
                sum += (a + 1) * base
            elif cur == 1:
                sum += a * base + b + 1
            else:
                sum += a * base
            base *= 10
        return sum

0 赞同 0 条回复

lobort 普通 2022年11月18日下午8:25

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 == 0){
                sum += high * bit;
            }else if(cur == 1){
                sum += high * bit + low + 1;
            }else{
                sum += (high + 1) * bit;
            }
            bit = bit * 10;
        }
        return (int)sum;
    }
}

没见过一点思路没有

0 赞同 0 条回复

小肸永久会员 2022年11月18日下午6:20

思路一：找规律。都是按位将数分为高部分和低部分，计算出该位上是1的数有多少个，然后对各位上进行类似计算，统计出1的个数。时间复杂度O(logN)，空间复杂度O(1)。

class Solution {
    public int countDigitOne(int n) {
        int res = 0, bit = 1;
        int high =  n / 10, cur = n % 10, low = 0;
        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);
            bit *= 10;
            cur = (high % 10);
            high /= 10;
        }
        return res;
    }
}

class Solution {
    public int countDigitOne(int n) {
        int res = 0;
        long multiple = 1;
        while (multiple <= n) {
            res += (n / (multiple * 10)) * multiple;
            long modNum = n % (multiple * 10);
            if (modNum < multiple) {
                res += 0;
            } else if (modNum >= multiple && modNum < 2 * multiple) {
                res += (modNum - multiple + 1);
            } else if (modNum >= 2 * multiple) {
                res += multiple;
            }
            multiple *= 10;
        } 
        return res;
    }
}

思路二：数位dp。也是按位的思想。

0 赞同 0 条回复

你有点可爱喔普通 2022年11月17日下午3:05

时间O(logn) 空间O(1）

class Solution {
    public int countDigitOne(int n) {
        long bit = 1;
        int 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 条回复

y 普通 2022年11月16日下午11:10

var countDigitOne = function(n) {
  let mulk = 1;
  let ans = 0;
  for (let k = 0; n >= mulk; ++k) {
      ans += (Math.floor(n / (mulk * 10))) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
      mulk *= 10;
  }
  return ans;
};

看的官方题解

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月16日下午1:10

时间复杂度为O（lgn），空间复杂度为O（1）。

class Solution {
    public int countDigitOne(int n) {
        long bit = 1;
        long sum = 0;
        while(bit <= n){
            long high = n / (bit * 10);
            long low = n % bit;
            long cur = (n/bit) % 10;
            if(cur > 1){
                sum += (high + 1) * bit;
            }else if(cur < 1){
                sum += high * bit;
            }else{
                sum += high * bit + low + 1;
            }
            //bit很有可能越界，需要转化为long类型
            bit *=10;
        }
        return (int)sum;
    }
}

0 赞同 0 条回复

just 普通 2022年11月16日上午11:31

//模拟
class Solution {
public:
int countDigitOne(int n) {
long long res=0,digit=1;
long long high=n/10,cur=n%10,low=0;
while(high!=0||cur!=0){
if(cur0) res+=highdigit;
else if(cur1){
res+=(highdigit+low+1);
}
else{
res+=(high+1)digit;
}
low+=curdigit;
digit*=10;
cur=high%10;
high/=10;
}
return res;
}
};

0 赞同 0 条回复

大宝子冲永久会员 2022年11月14日下午11:34

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）
整不明白markdown了，就这样提交了

0 赞同 0 条回复

天然普通 2022年11月14日下午11:15

题解的第一个方法，思路懂了，写不出来，第二种用动态规划做，明白了，一次一次细分去做

class Solution:
    def countDigitOne(self, n: int) -> int:
        dp,res,temp,i = [0,1],0,1,0
        for k in range(2,10):
            dp.append(int(math.pow(10,k-1))*k)
        while temp<=n:
            a,b = n%temp,(n%(temp*10))//temp
            if b>1:res+=(b)*dp[i]+temp
            elif b==1: res += a+dp[i]+1
            i += 1
            temp *= 10


        return res

0 赞同 0 条回复

庄重普通 2022年11月14日上午9:33

// 思路：
//     几个变量计算：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
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{// cur == 0
                sum += high * bit;
            }
            bit *= 10;
        }

        return sum;
    }
};
//时间复杂度O(n)
//空间复杂度O(1)

0 赞同 0 条回复

So 普通 2022年11月13日下午7:45

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 *= 10;
        }
        return (int) sum;
    }
}

时间：O(1)，空间：O(1)

0 赞同 0 条回复

黎昕普通 2022年11月12日下午10:00

class Solution:
    def countDigitOne(self, n: int) -> int:
        # 思路：这是一道数学题，通过找规律统计出一个公式，以此求解
        # 具体还是官方题解写的很清楚
        k=0
        powk=1
        ans=0
        while n>=powk:
            powk=pow(10,k)
            powkk=powk*10
            ans+=(n//powkk)*powk+min(max(n%powkk-powk+1,0),powk)
            k+=1
        return ans

0 赞同 0 条回复

派大星普通 2022年11月12日下午9:36

class Solution {
//时间复杂度O(logn)
//空间复杂度O(1)
    public int countDigitOne(int n) {
        //从个位自下而上的遍历1的个数
        //遍历的位置
        long index = 1;
        int sum = 0;
        while (index <= n) {
            long cur = (n / index) % 10;
            long left = n / index / 10;
            long right = n % index;
            if(cur == 1){
               sum += (left * index + right + 1);  
            } else if (cur > 1) {
               sum += (left + 1) * index; 
            }else {
               sum += left * index; 
            }
            index *= 10;

        }
        return sum;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月12日下午9:03

将 1 ~ n 的个位、十位、百位、…的 1 出现次数相加，即为 1 出现的总次数。

某位中 1 出现次数的计算方法：

根据当前位 cur 值的不同，分为以下三种情况：

cur=0，此位1的出现次数只有高位high决定，计算公式为high*digit

如下图所示，以 n = 2304 为例，求 digit = 10（即十位）的 1 出现次数。

” alt=”Picture1.png” />

cur=1，此位1的出现次数由高位high和低位low决定，计算公式为high*digit + low + 1

” alt=”Picture2.png” />

cur=2,3,…9，此位1的出现次数由高位high决定，计算公式为(high+1)*digit

” alt=”Picture3.png” />

/**
时间复杂度O(logn)：因为循环次数为10^x=n->x = lgn
空间复杂度O(1)
*/
class Solution {
    public int countDigitOne(int n) {
        int res = 0,digit = 1;//个位
        int high = n / 10,cur = n % 10,low = 0;
        while(high != 0 || cur != 0){
            if(cur == 0){
                //对应cur为0的计算方式
                res += high * digit;            
            }else if(cur == 1){
                res += high * digit + low + 1;
            }else{
                res += (high + 1) * digit;
            }
            low += cur * digit;//将cur加入low，组成下轮low
            cur = high % 10;//下轮cur是本轮high的最低位
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年11月12日上午10:43

这题开始做没看n范围，做完发现超时了，还是换了个办法
时间O(logn)
空间O(1)

class Solution {
    public int countDigitOne(int n) {
        // 个位，后面依次*10
        long bit = 1;
        // 结果
        long res = 0;
        while(bit <= n){
            // 将数划分为两部分
            long cur = (n / bit) % 10;
            long low = n % bit;
            long high = n / bit / 10;  //高位
            // cur>1的时候，把cur固定为1，低位就是0-bit-1，有bit个，高位就是0-高位数，有高位数+1个，所以是bit * （高位数+1）
            if(cur>1){
                res += (high + 1) * bit;
            }else if(cur == 1){     //cur == 1的时候，两种情况，给高位数取：0-高位-1，低位取0-bit-1，再加上 0 - 低位数；
                res += (high * bit) + (1 + low);
            }else{                  //cur == 0的时候，直接让高位数* bit就行
                res += high * bit;
            }
            // bit逐步递增
            bit = bit * 10;
        }
        // 前面定义是long,所以强转一下
        return (int)res;
    }
}

1 赞同 0 条回复

青木普通 2022年11月11日下午11:05

/**
    将数分为 高，中（此刻遍历的点），低
    当cur为0， 则cur为1的情况为high*digit
    当cur为1， 则cur为1的情况为high*digit + low + 1
    当cur大于1， 则cur为1的情况为（high+1）*digit

    时间O(logn)
    空间O(1)
 */

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

0 赞同 0 条回复

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

共以下 21 个回答

求每一位的1的个数

# 回答此问题取消回复

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

共以下 21 个回答

求每一位的1的个数

# 回答此问题 取消回复

# 回答此问题取消回复