剑指offer | 面试题34：1～n 整数中 1 出现的次数

死磕算法系列文章

干货 | 手撕十大经典排序算法

剑指offer | 认识面试

剑指offer | 面试题2：实现Singleton模式

剑指offer | 面试题3：二维数组的查找

剑指offer | 面试题4：替换空格

剑指offer | 面试题5：从尾到头打印链表

剑指offer | 面试题6：重建二叉树

剑指offer | 面试题7：用两个栈实现队列

剑指offer | 面试题8：旋转数组的最小数字

剑指offer | 面试题9：斐波那契数列

剑指offer | 面试题10：青蛙跳台阶问题

剑指offer | 面试题11：矩阵覆盖

剑指offer | 面试题12：二进制中1的个数

剑指offer | 面试题13：数值的整数次方

剑指offer | 面试题14：打印从1到最大的n位数

剑指offer | 面试题15：删除链表的节点

剑指offer | 面试题16：将数组中的奇数放在偶数前

剑指offer | 面试题17：链表中倒数第k个节点

剑指offer | 面试题18：反转链表

剑指offer | 面试题19：合并两个有序链表

剑指offer | 面试题20：判断二叉树A中是否包含子树B

剑指offer | 面试题21：二叉树的镜像

剑指offer | 面试题22：顺时针打印矩阵

剑指offer | 面试题23：包含min函数的栈

剑指offer | 面试题24：栈的压入、弹出序列

剑指offer | 面试题25：从上到下打印二叉树

剑指offer | 面试题26：二叉搜索树的后序遍历序列

剑指offer | 面试题27：二叉树中和为某一值的路径

剑指offer | 面试题28：复杂链表的复制

剑指offer | 面试题29：二叉搜索树转换为双向链表

剑指offer | 面试题30：字符串的排列

剑指offer | 面试题31：数组中出现次数超过一半的数字

剑指offer | 面试题32：最小的k个数

剑指offer | 面试题33：连续子数组的最大和

欢迎关注千羽的公众号

程序员千羽
“Leetcode : https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_34_countDigitOne/Solution.java
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出现次数的计算方法: 根据当前位cur值的不同，分为以下三种情况:

当cur=0时:此位1的出现次数只由高位high决定，计算公式为: high x digit
“如下图所示，以 n = 2304 为例，求 digit = 10 （即十位）的 1 出现次数。

Picture1.png
当 cur = 1 时： 此位 1 的出现次数由高位 high和低位 low 决定，

high x digit + low+ 1

当cur=2,3,… ,9时:此位1的出现次数只由高位high决定，计算公式为: (high+ 1) x digit . 如下图所示，以n= 2324为例，求digit= 10 (即十位) 的1出现次数。

变量递推公式: . 设计按照“个位、十位、.. 的顺序计算,则high/cur/low/digit应初始化为: .

high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位
因此，从个位到最高位的变量递推公式为：

while high != 0 or cur != 0: # 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
low += cur * digit # 将 cur 加入 low ，组成下轮 low
cur = high % 10 # 下轮 cur 是本轮 high 的最低位
high //= 10 # 将本轮 high 最低位删除，得到下轮 high
digit *= 10 # 位因子每轮 × 10
复杂度分析:

时间复杂度O(logn) :循环内的计算操作使用O(1)时间;循环次数为数字n的位数，即log10n,因 此循环使用O(log n)时间。
空间复杂度0(1): 几个变量使用常数大小的额外空间。

package com.nateshao.sword_offer.topic_34_countDigitOne;

/**

• @date Created by 邵桐杰 on 2021/12/11 11:00
• @微信公众号 程序员千羽
• @个人网站 www.nateshao.cn
• @博客 https://nateshao.gitee.io
• @GitHub https://github.com/nateshao
• @Gitee https://gitee.com/nateshao
• Description: 剑指 Offer 43. 1～n 整数中 1 出现的次数
• https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
  */
  public class Solution {
  public static void main(String[] args) {
  int n = 12;
  System.out.println(“countDigitOne1(n) = ” + countDigitOne1(n));// countDigitOne1(n) = 5
  System.out.println(“countDigitOne2(n) = ” + countDigitOne2(n));// countDigitOne2(n) = 5
  System.out.println(“countDigitOne3(n) = ” + countDigitOne3(n));// countDigitOne3(n) = 5
  } /**
  • 方法一：计算高低位
    *
  • @param n
  • @return
    */
    public static int countDigitOne1(int n) {
    int count = 0;
    int i = 1;
    int current = 0, after = 0, before = 0;
    while ((n / i != 0)) {
    before = n / (i * 10);// 高位
    current = (n / i % 10);// 当前位
    after = n – (n / i) * i;// 低位
    // 如果为 0,出现 1 的次数由高位决定,等于高位数字 * 当前位数
    if (current == 0) count = count + before * i;
    // 如果为 1,出现 1 的次数由高位和低位决定,高位*当前位+低位+1
    else if (current == 1) count = count + before * i + after + 1;
    // 如果大于 1,出现 1 的次数由高位决定,（高位数字+1）* 当前位数
    else if (current > 1) count = count + (before + 1) * i;
    // 前移一位
    i = i * 10;
    }
    return count;
    }
  /**
  • 方法二：公式法
    *
  • @param n
  • @return
    */
    public static int countDigitOne2(int n) {
    // mulk 表示 10^k
    // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
    // 但为了让代码看起来更加直观，这里保留了 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;
    }
  /**
  • 方法三: 递归
  • @param n
  • @return
    */
    public static int countDigitOne3(int n) {
    return f(n);
    }
  //下面我们都用 1234 和 2345 来举例
  private static int f(int n){
  // 上一级递归 n = 20、10之类的整十整百之类的情况；以及n=0的情况
  if(n== 0) return 0;
  // n < 10 即为个位，这样子只有一个1
  if(n < 10) return 1;
• String s = String.valueOf(n); //长度：按例子来说是4位 int length = s.length(); //这个base是解题速度100%的关键，本例中的是999中1的个数：300 // 99的话就是20 ; 9的话就是1 ；9999就是4000 这里大家应该发现规律了吧。 int base = (length-1)*(int)Math.pow(10,length-2); //high就是最高位的数字 int high = s.charAt(0) - '0'; //cur就是当前所数量级，即1000 int cur = (int)Math.pow(10,length -1); if(high == 1){ //最高位为1，1+n-cur就是1000~1234中由千位数提供的1的个数，剩下的f函数就是求1000~1234中由234产生的1的个数 return base + 1 + n - cur + f(n - high * cur); }else{ //这个自己思考 return base * high + cur + f(n- high * cur); } }

}
参考文献：

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/1n-zheng-shu-zhong-1-chu-xian-de-ci-shu-umaj8/