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

lQl 永久会员 2024年12月17日上午12:03

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

class Solution {
    public int digitOneInNumber(int num) {
        int high = num / 10;// 高位
        int low = 0;// 低位
        int cur = num % 10;// 现位
        int bit = 1;// 个位
        int ans = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                ans += high * bit;
            } else if (cur == 1) {
                ans += high * bit + low + 1;
            } else {
                ans += (high + 1) * bit;
            }

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

    }
}

0 赞同 0 条回复

陆狗陆狗普通 2024年12月15日下午10:46

解题思路
– 每个位置的1要单独计算，比如11要算2次，所以在每个位置单独考虑即可，不用担心数字重复只能算作一份
– 关键是总结第i位出现1的时候会有多少种可能，规律是什么，直接参考题解，https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/229751/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
– 难点是在于如何获取高位，当前位，低位的在每一次循环时的数据（用n=32104举例）

high
cur
low
digit
当前cur是从右到左第i位对应的10^i
公式
high=high/10
（第一次high=n/10）
cur=high%10
（第一次high=n%10）
low =low +cur*digit

digit =digit *10
第1次循环
32104
32104
0
1
第2次循环
32104
32104
4
10
第3次循环
32104
32104
4
100
第4次循环
32104
32104
104
1000
第5次循环
0
32104
2104
10000
【题解1】

class Solution {
    public int digitOneInNumber(int num) {
        // 首先，理解题意，比如13，会出现1,10,11,12,13 （其中11要算作2个），所以最终有6个
        // 结论，每个位置的1要单独计算
        // 规律，2304，倒数第2位=0时，可能倒数第2位出现1的范围（2219~0010）=(229~000)=(22+1)*10=230=高位*10
        // 2314，倒数第2位=1时，可能倒数第2位出现1的范围（2314~0010）=(234~000)=23*10+(4-0+1)=235=高位*10+(低位+1)
        // 2324,倒数第2位不为0和1时，可能倒数第2位出现1的范围（2319~0010）=(239~000)=(23+1)*10=240=(高位+1)*10

        // 当前cur是从右到左第i位对应的10^i
        int digit = 1;
        // 左边：高位的数字是哪些
        int high = num / 10;
        // 中间：当前的数字是什么？
        int cur = num % 10;
        // 右边：低位的数字是哪些
        int low = 0;
        // 结果
        int result = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) {
                // 【错误点1】没有high * digit，而是用的high*10
                // 【错误点2】result =result+ xx,没有去累加result
                result = result + high * digit;
            } else if (cur == 1) {
                result = result + (high * digit + (low + 1));
            } else {
                result = result + (high + 1) * digit;
            }
            // 迭代
            low = low + digit * cur;
            cur = high % 10;
            high = high / 10;
            digit = digit * 10;
        }
        return result;

    }
}

错误点1：没有high * digit，而是用的high*10
错误点2：result =result+ xx,没有去累加result

0 赞同 0 条回复

Xiang. 永久会员 2024年12月13日下午7:56

class Solution {
    //思路：根据当前位cur的数值，分三种情况，逐个求出cur上1出现的次数
    public int digitOneInNumber(int num) {
        int digit=1;
        int res=0;
        int high=num/10;
        int cur=num%10;
        int low=0;
        while(high!=0||cur!=0){
            if(cur==0)  res+=(high*digit);    //当 cur=0 时： 此位 1 的出现次数只由高位 high 决定
            else if(cur==1) res+=(high*digit+low+1);   //当 cur=1 时： 此位 1 的出现次数由高位 high 和低位 low 决定
            else res+=(high+1)*digit;   //此位 1 的出现次数只由高位 high 决定
            low+=cur*digit;
            cur=high%10;
            high/=10;
            digit*=10;
        }
        return res;
    }
}
时间复杂度：o（logn）
空间复杂度：o（1）

0 赞同 0 条回复

迢迢星野普通 2024年12月12日下午8:56

class Solution {
    /**
     * 给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。
     * 
     * 题意解读：
     *      例如：nums = 13
     *          所有小于等于 num 种数字 1 出现的个数：1 10 11 12 13，   6 个
     *      1-9： 1
     *      10-99：91 81 71 61 51 41 31 21 11 19 18 17 16 15 14 13 12 10 
     *      将 1~n 的个位、十位、百位、... 的 1 的出现次数相加，就是 1 出现的总次数。
     *      设数字 n 的一个 x 位数，记 n 的第 i 位是 ni，可以将 n 写成 nx...n2n1，
     *          ni 被称为当前位，cur
     *          ni-1ni-2...n2n1 记为低位，low
     *          nxnx-1...ni+2ni+1 记为高位，high
     *          将 10^i 称为位因子，记为 digit；
     *      某位中 1 出现次数的计算方法：
     *          根据 cur 值的不同，分为以下三种情况：
     *              cur = 0：此位 1 的出现次数只由高位 high 决定，计算公式：high * digit
     *                  例如：n = 2304，求十位位置上 1 出现的次数.
     *                      出现 1 的数字范围：0010 ~ 2219
     *                      只看高低位：000 ~ 229
     *                      计算 1 出现次数：229 - 0 + 1 = 230
     *                  那么当 cur = 0，1 出现次数为 high * digit
     *             cur = 1，此位的 1 是由高位和低位共同决定的，计算公式：high * digit + low + 1
     *                  例如：n = 2314，求十位位置上 1 出现的次数。
     *                      出现 1 的数字范围：0010 ~ 2219
     *                      只看高低位：000 ~ 234
     *                      计算 1 出现次数：234 - 0 + 1 = 235
     *                  那么当 cur = 1，1 出现次数为 high * digit + low + 1
     *             cur = 2,3,4,5,6,7,8,9，此位 1 的出现次数只由高位 high 决定，计算公式为：(high + 1) * digit
     *                   例如：n = 2324，求十位位置上 1 出现的次数。
     *                      出现 1 的数字范围：0010 ~ 2319
     *                      只看高低位：000 ~ 239
     *                      计算 1 出现次数：239 - 0 + 1 = 240
     *      high = n / 10, cur = n % 10, low = 0, digit = 10;
     *      
     *      low = low + cur * digit;
     *      cur = high % 10;
     *      high = n / 10;
     *      digit *= 10;
     * @param num
     * @return
     */
    public int digitOneInNumber(int num) {
        int low = 0, high = num / 10, cur = num % 10, digit = 1;
        int res = 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 = low + cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
}

思路：数学推导，按照一个数字的每一位统计 1 的次数。
时间复杂度：O(logn)
空间复杂度：O(logn)

0 赞同 0 条回复

Aatorx 永久会员 2024年12月12日下午3:04

class Solution {
public:
    int digitOneInNumber(int num) {
        int high = num / 10;
        int cur = num % 10;
        int low = 0;
        long digit = 1;
        int res = 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 + low;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
};

分别计算各位上1的数量，然后求和得到结果。
时间复杂度O(Logn)，空间复杂度O(1)。

0 赞同 0 条回复

Kisara 普通 2024年12月12日下午2:33

逐位计算，分三种情况

class Solution {
    public int digitOneInNumber(int num) {
        //cur=n/bit%10
        //cur=0   count+=high*low
        //cur=1    count+=high*low+1+low
        //cur=2-9   count=(high+1)*low

        long bit=1;
        int sum=0;
        while(bit<=num){
            long cur=(num/bit)%10;
            long high=num/bit/10;
            long low=num%bit;
            if(cur==0) sum+=high*bit;
            else if(cur==1) sum+=high*bit+low+1;
            else sum+=(high+1)*bit;

            bit*=10;
        }
        return sum;
    }
}

Ologn o1

0 赞同 0 条回复

晓宇普通 2024年12月12日上午11:20

class Solution {
public:
    int digitOneInNumber(int num) {
        if(num < 1) return 0;
        int cnt = 0;
        long factor = 1;
        while(factor <= num){
            int high = num / factor / 10;
            int curr = num / factor % 10;
            int low = num % factor;

            if(curr == 0){
                cnt += high *factor;  // 1 来源于高位 

            }else if(curr ==  1){
                cnt += high * factor + low + 1; // 0 ~ high-1 * factor + 0~low|high

            }else{
                cnt += (high + 1) * factor;  // 0~high * factor
            }
            factor *= 10;


        }
        return cnt;

    }
};
// o (log n)  o(1)

0 赞同 0 条回复

jaron 普通 2024年12月11日下午7:54

class Solution {
    public int digitOneInNumber(int num) {
        // 排列组合问题
        long bit = 1, low = 0, high = 0, cur = 0, ans = 0;
        while (bit <= num) {
            cur = (num / bit) % 10;
            low = num % bit;
            high = num / bit / 10;
            if (cur > 1) {
                // 右边可以取满
                ans += (high + 1) * bit;
            } else if (cur == 1) {
                // 左边是high的时候，右边只能取到low
                ans += high * bit + 1 + low;
            } else {
                // 左边是high的时候，右边不能取
                ans += high * bit;
            }
            bit *= 10;
        }
        return (int) ans;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年12月11日下午7:43

//方法1 暴力解（超出时间限制）

class Solution {
public int digitOneInNumber(int num) {
int result = 0;
for (int i = num; i >= 0; i–) {
result+=one_numlen(i);
}
return result;
}

public static int one_numlen(int num) {
    int result = 0;
    int main_result = num;
    int single_num;
    while(main_result != 0) {
        single_num = main_result % 10;
        main_result = main_result / 10;
        if (single_num == 1) {
            result++;
        }
    }
    return result;
}

}

//方法2
class Solution {
public int digitOneInNumber(int num) {
int result = 0;
long factor = 1; // 使用 long 类型防止溢出

    while (factor <= num) {
        long lower = num % factor;               // 当前位以下的数
        long current = (num / factor) % 10;      // 当前位的数字
        long higher = num / (factor * 10);       // 当前位以上的数

        if (current == 0) {
            result += higher * factor;
        } else if (current == 1) {
            result += higher * factor + lower + 1;
        } else {
            result += (higher + 1) * factor;
        }

        factor *= 10; // 转到下一位
    }

    return result;
}

}

0 赞同 0 条回复

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

共以下 9 个回答

# 回答此问题取消回复

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

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复