Count Digits
给定一个非负整数 n，返回它用十进制表示且不带前导零时的位数。零写作一个 0，所以它有一位。
函数
- ninteger
- 要测量的非负整数
- 返回值integer
- n 中小数位数
约束条件
0 ≤ n ≤ 231-1
示例
- 输入
- n = 4096
- 输出
- 4
- 解释
- 除以 10 的整除运算会将
4096依次变为409、40和4：去掉了三位数字，还剩一位，所以答案是4。
- 输入
- n = 0
- 输出
- 1
- 解释
0用一位数字表示。当数字大于 0 时才计数的循环在这里不会运行，因此返回的是0，而不是1。
- 输入
- n = 100
- 输出
- 3
- 解释
- 0 也是数字：
100写作1、0、0，所以答案是3。
进阶
你能不能不使用每个数字都运行一次的循环来统计位数，例如对 10 的幂进行二分查找？
提示
逐个打开提示，每个都会多透露一点。
一个数除以 10 并舍去余数后，位数会发生什么变化？
每次除以 10 取整，都会恰好去掉末尾的一位数字。数一数需要除几次，才能得到一位数。
从 1 开始计数，当数字大于或等于 10 时，将它除以 10，并且每次加 1。从 1 开始也能为
0得出正确答案。
题解
每次除以 10 取整都会去掉一位数字。数一数要除几次才能只剩一位，然后再为这一位加 1。边界情况容易出 bug：0 有一位数字，而对 0 以及略小于较大 10 的幂的数，取对数的公式会失效。
把数字写成文本，并统计字符数
思路
你的语言本身就用十进制表示 n。获取这个字符串并统计其中的字符数：4096 会变成 "4096"，共 4 个字符；0 会变成 "0"，因此零不需要特殊处理。
转换时每个数字都要做一次除法，因此时间和额外内存的复杂度都是 O(log n)，这里最多有 10 个字符。
算法
- 使用一个不会切换为科学计数法的函数，将
n转换为十进制字符串。 - 统计字符串中的字符数。
- 返回该字符数。对于
0，字符串是"0"，因此答案是1，无需额外检查。
def countDigits(n):
return len(str(n))不断除以 10，直到只剩一位数字
思路
从 1 开始计数，当 n ≥ 10 时不断除以 10，每除一次就加 1。从 1 开始，表示每个数字至少有一位，这正是 0 的规则，因此不需要单独检查。
对于 2147483647，循环最多运行 9 次，时间复杂度为 O(log n)。它只使用一个计数器，并修改 n 的副本，因此额外空间复杂度为 O(1)。
算法
- 将
count = 1，用于表示始终存在的那一位数字。 - 当
n ≥ 10时，用整数除法将n除以 10，并将count加 1。 - 剩下一位数字时，返回
count。
def countDigits(n):
count = 1 # every number, 0 included, has at least one digit
while n >= 10:
n //= 10
count += 1
return count
易错点和边界情况
- 当
n > 0时从 0 开始计数。对于n = 0，它会返回0。 - 使用
floor(log10(n)) + 1。当n为0时会失败，因为对数为负无穷；当n为10^15-1时也会失败，因为双精度会将对数舍入为恰好 15，公式会得出 16 位数。 - 在 JavaScript、Lua、PHP 或 R 中进行实数除法时，
/会保留小数部分。因此，当n > 0时，循环会对4096运行 328 次。请使用Math.floor、math.floor、intdiv或%/%。 - 字符串版本中的科学计数法。R 会将
as.character(1e5)写成"1e+05"；请使用sprintf("%.0f", n)。在 Lua 5.3 及更高版本中，tostring(4096.0)会保留.0；请使用string.format("%d", n)。
常见问题3
计算数字位数的时间复杂度是多少？
一个数字有 floor(log10(n)) + 1 位，循环每位执行一次除法，因此运行时间为 O(log n)，空间复杂度为 O(1)。对于 32 位整数，最多需要 10 步。
你能用 log10 计算一个数的位数吗？
对于正数 n，位数是 floor(log10(n)) + 1，但对数是用浮点数计算的。对于 0，对数没有定义；当数值接近 10 的幂时，结果可能会舍入错误：在双精度下，log10(10^15-1) 的结果恰好是 15。整数除法始终精确。
如何统计负数的位数？
先取绝对值，然后照常计数。String(-42) 有 3 个字符，因为减号不是数字。对于最小的 32 位整数，要在 64 位类型中取绝对值，因为它无法放入 32 位类型。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def countDigits(n):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
n = 4096
预期输出
4