本文主要是介绍43. 1 ~ n 整数中 1 出现的次数【难】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9843.%201%EF%BD%9En%E6%95%B4%E6%95%B0%E4%B8%AD1%E5%87%BA%E7%8E%B0%E7%9A%84%E6%AC%A1%E6%95%B0/README.md
面试题 43. 1 ~ n 整数中 1 出现的次数
题目描述
输入一个整数 n
,求1~n这n个整数的十进制表示中1出现的次数。
例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。
示例 1:
输入:n = 12 输出:5
示例 2:
输入:n = 13 输出:6
限制:
1 <= n < 2^31
注意:本题与主站 233 题相同:https://leetcode.cn/problems/number-of-digit-one/
解法
【LeetCode力扣刷题 | 剑指Offer题解合集 | 画解算法思路Python3或C++代码实现】 https://www.bilibili.com/video/BV1CK411c7gx/?p=38&share_source=copy_web&vd_source=ed4a51d52f6e5c9a2cb7def6fa64ad6a 【讲的很清晰】
时间复杂度 O ( log n ) O(\log n) O(logn)。
Python3
class Solution:def countDigitOne(self, n: int) -> int:def count_digit_one(n):base = 1res = 0while base <= n:b = n // basea = n // (base * 10)cur = (n // base) % 10if cur > 1:res += (a + 1) * baseelif cur == 1:res += a * base + (n % base) + 1else:res += a * basebase *= 10return res
这篇关于43. 1 ~ n 整数中 1 出现的次数【难】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!