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

=.= 普通 2024年4月5日下午11:23

class Solution {
public int digitOneInNumber(int num) {

    long bit = 1;
    long sum = 0;

    while(bit <= num){
        long cur = num / bit % 10;
        long low = num % bit;
        long high = num / bit / 10;

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

        bit *= 10;
    }

    return (int)sum;
}

}

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

0 赞同 0 条回复

NULL 普通 2024年3月29日下午10:39

class Solution {
public int digitOneInNumber(int num) {
// 如果输入的数字为0，则直接返回0
if (num 0) return 0;

    // 初始化结果变量
    long res = 0;
    // 初始化基数
    long base = 1;

    // 从个位开始，逐位遍历数字
    while (base <= num) {
        // 获取当前位的数字
        long cur = num / base % 10; // 当前位
        // 获取当前位的高位数字
        long high = num / (base * 10); // 高位
        // 获取当前位的低位数字
        long low = num % base; // 低位

        // 根据当前位的数字分情况计算数字1出现的次数并累加到结果中
        if (cur > 1) {
            // 如果当前位数字大于1，则当前位为1的情况为：[0, high] * base
            res += (high + 1) * base;
        } else if (cur == 1) {
            // 如果当前位数字等于1，则当前位为1的情况为：[0, high-1] * base + (low + 1)
            res += (high * base) + (low + 1);
        } else {
            // 如果当前位数字小于1，则当前位为1的情况为：[0, high-1] * base
            res += high * base;
        }
        // 更新基数，移动到下一位
        base *= 10;
    }
    // 将 long 类型的结果转换为 int 类型并返回
    return (int)res;
}

}

0 赞同 0 条回复

言之命至普通 2024年3月24日下午8:36

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; //bit移一位
        }

        return (int)sum;

    }
}

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

0 赞同 0 条回复

神经蛙普通 2024年3月23日下午10:24

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

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月23日下午9:36

class Solution {
    public int digitOneInNumber(int num) {
        long bit=1;
        long sum=0;
        int n=num;

        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 条回复

方铎码农普通 2024年3月23日下午5:53

class Solution {
    public int countDigitOne(int n) {
        //mulk = 10^k
        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;
    }
}

时间复杂度$O(\log{n})$，空间复杂度$O(1)$

0 赞同 0 条回复

Jimmy 普通 2024年3月23日下午4:41

当某位为1，统计其高位和低位的情况

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月23日下午3:01

感觉这道题好难

“`C++
class Solution {
public:
int digitOneInNumber(int num) {
// 几个变量计算：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 high = num/10, cur = num%10, low = 0, res = 0;
while(high != 0 || cur != 0)
{
cur = (num/bit)%10;
low = num%bit;
high = num/bit/10;
if(cur == 0)
{
res += high * bit;
}
else if(cur == 1)
{
res += high * bit + low + 1;
}
else
{
res += (high + 1) * bit;
}
bit *= 10;
}
return res;
}
};
“`

0 赞同 0 条回复

云无深雁影普通 2024年3月22日下午3:55

class Solution {
public int digitOneInNumber(int num) {
if(num 0) return 0;
int count = 0;
int digit = 10;
int high;
int low;
count += (num%100) ? num / 10 : num / 10 + 1;//个位数为1

    while(num / digit / 10 != 0){//中间位
        low = num % digit;
        high = num / digit /10;
        int cur = num / digit % 10;
        if(cur == 0) count += high * digit ;
        else if(cur == 1) count += high * digit + low + 1;
        else count += (high + 1) * digit;
        digit *= 10;
    }
    int headDigit = num / digit;//末位为1
    if(headDigit == 1)
        count += num % digit + 1;
    else if(headDigit > 1)
        count += digit;
    return count; 
}

}

0 赞同 0 条回复

紫芝普通 2024年3月22日下午1:51

打卡

func digitOneInNumber(num int) int {
    ans, digit := 0, 1
    high, cur, low := num/10, num%10, 0
    for high != 0 || cur != 0 {
        switch cur {
            case 0:
                ans += high * digit
            case 1:
                ans += high * digit + low + 1
            default:
                ans += (high+1) * digit
        }
        low += cur * digit
        cur = high % 10
        high /= 10
        digit *= 10
    }
    return ans
}

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月22日上午8:43

打卡

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

0 赞同 0 条回复

MARS 普通 2024年3月22日上午12:10

/**
 * @param {number} num
 * @return {number}
 */
var digitOneInNumber = function (num) {
    let high = num //高位
    let low = 0  //低位
    let cur = 0 //当前位
    let count = 0;
    let y=1
    while (high != 0 || cur != 0) {
        cur = high % 10;  //余数
        high = Math.floor(high / 10)
        //这里我们可以提出 high * num 因为我们发现无论为几，都含有它
        if (cur == 0) count += high * y;
        else if (cur == 1) count += high * y + 1 + low;
        else count += (high + 1) * y;

        low = cur * y + low
        y *= 10
    }
    return count
};

0 赞同 0 条回复

王位詮釋普通 2024年3月21日下午11:14

帅地规律法：
class Solution {
    public int digitOneInNumber(int num) {
        long bit = 1;
        long sum = 0;//sum可能会超过int表示范围
        while(bit<=num){//循环计算每一位上的1的个数然后相加
            long cur = (num/bit)%10;
            long high = num/bit/10;
            long low = num%bit;
            if(cur>1){
                sum+=(high+1)*bit;
            }else if(cur==1){
                sum+=high*bit+(low+1);
            }else{
                sum+=high*bit;
            }
            bit = bit*10;
        }
        return (int) sum;
    } 
}

然后自己没找到规律，想着是暴力解，但是把每次获取过1个数的数字保存在map集合里，但是最后几个大数的时候超时了：
class Solution {
    public int digitOneInNumber(int num) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 1;i<=num;i++){
            if(map.containsKey(i)){
                count+=map.get(i);
            }else{
                count+=getCount(i);
                map.put(i,getCount(i));
            }
        }
        return count;
    }
    public int getCount(int num){
        int count = 0;
        while(num!=0){
            int mod = num%10;
            num/=10;
            if(mod==1){
                count++;
            }
        }
        return count;
    }
}

0 赞同 0 条回复

heathhou 普通 2024年3月21日下午7:34

class Solution {
public:
    int digitOneInNumber(int num) {
        // 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
        long long bit = 1;
        long long sum = 0;
        while(bit <= num){
            long long cur = (num / bit) % 10;
            long long high = num / bit / 10;
            long long low = num % bit;
            // 判断cur取值为1的情况
            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 条回复

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

共以下 14 个回答

# 回答此问题取消回复

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

共以下 14 个回答

# 回答此问题 取消回复

# 回答此问题取消回复