当前位置：首页 > news >正文

LeetCode题练习与总结：数字 1 的个数--233

news 2024/9/21 10:22:32

一、题目描述

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

0 <= n <= 10^9

二、解题思路

我们可以通过计算每一位上1出现的次数来解决这个问题。具体来说，我们可以使用以下步骤：

遍历每一位（从个位开始），对于每一位，我们可以计算出以下三个部分：
- 当前位之前的数字（prefix）
- 当前位的数字（current）
- 当前位之后的数字（suffix）
对于每一位，我们可以计算出以下几种情况：
- 如果当前位是0，那么1出现的次数就是prefix * digit。
- 如果当前位是1，那么1出现的次数就是prefix * digit + suffix + 1。
- 如果当前位大于1，那么1出现的次数就是(prefix + 1) * digit。
把每一位上1出现的次数累加起来就是最终的结果。

三、具体代码

class Solution {public int countDigitOne(int n) {int count = 0; // 用于存储1出现的次数int i = 1; // 表示当前位的权重，如个位是1，十位是10，百位是100等while (n / i > 0) {int prefix = n / (i * 10); // 当前位之前的数字int current = (n / i) % 10; // 当前位的数字int suffix = n - (n / i) * i; // 当前位之后的数字if (current == 0) {count += prefix * i;} else if (current == 1) {count += prefix * i + suffix + 1;} else {count += (prefix + 1) * i;}i *= 10;}return count;}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

代码中有一个while循环，循环的条件是n / i > 0。在这个循环中，每次迭代都会将i乘以10，即i *= 10。
在最坏的情况下，i会一直增长直到i大于等于n。因为i每次迭代都会乘以10，所以i的增长速度是指数级的。
假设n有d位（d是n的位数），那么循环将执行d次。因为每次i乘以10，所以循环体将执行大约log10(n)次。
循环体内的操作都是常数时间的操作，所以总的时间复杂度是O(log10(n))。

2. 空间复杂度

代码中使用了固定数量的变量：count、i、prefix、current和suffix。这些变量不依赖于输入n的大小，因此它们占用的空间是常数级的。
代码中没有使用任何额外的数据结构，如数组、列表或递归栈等，所以额外的空间使用是O(1)。
因此，总的空间复杂度是O(1)。

五、总结知识点

基础编程概念：
- 变量的声明与初始化：int count = 0; 和 int i = 1;。
- 循环结构：使用while循环来重复执行代码块，直到满足某个条件。
数学运算：
- 整数除法：n / i用于获取数字的某一位。
- 取余运算：(n / i) % 10用于获取当前位的数字。
- 乘法运算：i *= 10用于更新位权重。
逻辑判断：
- 条件语句：if-else用于根据当前位的值选择不同的计算方式。
位操作与数学结合：
- 分割数字：将数字n分割为prefix（前缀）、current（当前位）和suffix（后缀）三部分，以便于分别处理。
- 计算当前位1的出现次数：根据当前位是0、1还是大于1，来计算当前位上1出现的次数。
算法思想：
- 数位动态规划：通过逐位分析数字，计算每一位上1出现的次数，并累加得到最终结果。