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

一、题目描述

给定一个整数 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出现的次数，并累加得到最终结果。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

原文地址：https://blog.csdn.net/weixin_62860386/article/details/142407298

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！