前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer | 面试题34:1~n 整数中 1 出现的次数

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

作者头像
千羽
发布2021-12-29 13:29:18
2490
发布2021-12-29 13:29:18
举报
文章被收录于专栏:程序员千羽程序员千羽

死磕算法系列文章

  1. 干货 | 手撕十大经典排序算法
  2. 剑指offer | 认识面试
  3. 剑指offer | 面试题2:实现Singleton模式
  4. 剑指offer | 面试题3:二维数组的查找
  5. 剑指offer | 面试题4:替换空格
  6. 剑指offer | 面试题5:从尾到头打印链表
  7. 剑指offer | 面试题6:重建二叉树
  8. 剑指offer | 面试题7:用两个栈实现队列
  9. 剑指offer | 面试题8:旋转数组的最小数字
  10. 剑指offer | 面试题9:斐波那契数列
  11. 剑指offer | 面试题10:青蛙跳台阶问题
  12. 剑指offer | 面试题11:矩阵覆盖
  13. 剑指offer | 面试题12:二进制中1的个数
  14. 剑指offer | 面试题13:数值的整数次方
  15. 剑指offer | 面试题14:打印从1到最大的n位数
  16. 剑指offer | 面试题15:删除链表的节点
  17. 剑指offer | 面试题16:将数组中的奇数放在偶数前
  18. 剑指offer | 面试题17:链表中倒数第k个节点
  19. 剑指offer | 面试题18:反转链表
  20. 剑指offer | 面试题19:合并两个有序链表
  21. 剑指offer | 面试题20:判断二叉树A中是否包含子树B
  22. 剑指offer | 面试题21:二叉树的镜像
  23. 剑指offer | 面试题22:顺时针打印矩阵
  24. 剑指offer | 面试题23:包含min函数的栈
  25. 剑指offer | 面试题24:栈的压入、弹出序列
  26. 剑指offer | 面试题25:从上到下打印二叉树
  27. 剑指offer | 面试题26:二叉搜索树的后序遍历序列
  28. 剑指offer | 面试题27:二叉树中和为某一值的路径
  29. 剑指offer | 面试题28:复杂链表的复制
  30. 剑指offer | 面试题29:二叉搜索树转换为双向链表
  31. 剑指offer | 面试题30:字符串的排列
  32. 剑指offer | 面试题31:数组中出现次数超过一半的数字
  33. 剑指offer | 面试题32:最小的k个数
  34. 剑指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:

代码语言:javascript
复制
输入:n = 12
输出:5

示例 2:

代码语言:javascript
复制
输入:n = 13
输出:6

读题->纸上钻研->半小时过去->打开题解->看到路飞->眼中泛光->阅读题解->发出感叹->"牛逼"

解题思路:

某位中1出现次数的计算方法: 根据当前位cur值的不同,分为以下三种情况:

  1. 当cur=0时:此位1的出现次数只由高位high决定,计算公式为: high x digit

“如下图所示,以 n = 2304 为例,求 digit = 10 (即十位)的 1 出现次数。

Picture1.png

cur = 1 时: 此位 1 的出现次数由高位 high和低位 low 决定,

high x digit + low+ 1

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

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

代码语言:javascript
复制
high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位

因此,从个位到最高位的变量递推公式为:

代码语言:javascript
复制
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): 几个变量使用常数大小的额外空间。
代码语言:javascript
复制
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);
        }
    }

}

参考文献:

  1. 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/
  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/
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-12-12,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 千羽的编程时光 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1~n 整数中 1 出现的次数
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档