专栏首页健程之道剑指offer 43——1~n整数中1出现的次数

剑指offer 43——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 <= n < 2^31

原题url:https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/

解题

暴力法

一开始我的想法是计算出从 1 到 n 中,每一个数中包含的1个数,累加在一起,求得结果:

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }

        // 存储从1到上一个数的总结果,初始是从1到1的总结果
        int before = 1;
        int temp, count;
        for (int i = 2; i <= n; i++) {
            temp = i;
            count = 0;
            while (temp != 0) {
                // 计算当前数字的个位数是否等于1
                if (temp % 10 == 1) {
                    count++;
                }
                temp /= 10;
            }

            before += count;
        }
        return before;
    }
}

提示我超出时间限制

接下来我想到的是,当给我们一个数 x 时,如果我知道 (x / 10) 对应的 1 的个数,那么再加上最高位 1 的个数,就得出了当前数字对应的 1 的个数。

用一个数组,记录每一个数字对应的1的个数。由此可以写出代码:

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }
        // 存储数字原本含有的1的数量
        int[] countOne = new int[n + 1];
        // 存储从1到上一个数的总结果,初始是从1到1的总结果
        int before = 0;
        int temp, count;
        for (int i = 1; i <= n; i++) {
            countOne[i] = (i % 10 == 1 ? 1 : 0) + countOne[i / 10];
            before += countOne[i];
        }
        return before;
    }
}

提示我超出内存限制

看来暴力求解不可取,让我们换一种思路。

找规律

由上面的暴力法,我们可以得知:

  1. 这道题肯定不能从 1 开始慢慢算出每一个数所对应的 1 的个数,因为这样会超时。
  2. 也不可以借用 n 个额外空间,因为这样会超出内存限制。

那么正确的思路就应该是,给你一个数 n ,你直接计算出从 1 到 n 的数中,所有 1 的总个数。

假设给你一个数 3210,你会如何求解呢?

我们可以把这个数进行拆分:

3210 = 3000 + 200 + 10 + 0
          = 3 * 1000 + 2 * 100 + 1 * 10 + 0 * 1

似乎没有看出什么规律,那么我们再试着求出每一位,对应的 1 的个数。

从千位 3 开始,针对 1000 ~ 1999 这 1000 个数字,千位上都是 1,因此这里有 1000 个。
百位 2,针对 100 ~ 199 这 100 个数字,百位上都是 1。一共出现了 3 组,分别是 100 ~ 199、1100 ~ 1199、2100 ~ 2199、3100 ~ 3199,一共 (4 * 100 = 400) 个。
十位 1,针对 10 ~ 19 这 10 个数字,十位上都是 1。一共出现了 32 组,但是再加上 3210 本身十位上也是 1,因此一共有 ( 32 * 10 + 1 = 321) 个。
个位 0,针对 1、11、21、...、101、111、121、...、1001、1011、1021、...、3201,每 10 个数都会出现 1 个,因此一共有 (321 * 1 = 321)个。
一共 2042 个。

我用力扣本身的测试用例进行了校验,结果是一致的。

我们总结一下上面的过程:

我们将数字 n,按照位,从低到高进行遍历。
我们假设当前位的数字为 cur,高位为 high,低位为 low,位数为 digit。比如 3210 这个数,针对百位而言,cur 是 2,high 是 3,low 是 10,digit 是 100。
针对 cur,有 3 种情况:
1、大于 1,那么此位 1 的个数就是:(high + 1) * digit
2、等于 1,那么此位 1 的个数就是:high * digit + low + 1
3、小于 1(也就是等于 0 ),那么此位 1 的个数就是:high * digit

接下来我们看看代码:

class Solution {
    public int countDigitOne(int n) {
        if (n < 1) {
            return 0;
        }

        // 高位
        int temp = n;
        // 低位
        int low = 0;
        // 1出现的总次数
        int total = 0;
        // 当前位数,比如个位时为1,十位时为10,百位时为100
        int pow = 1;
        while (temp != 0) {
            // 当前位上的数字
            int num = temp % 10;
            // 剩下的高位
            temp = temp / 10;
            // 如果当前位上的数字是0
            if (num == 0) {
                // 只加上高位对应
                total += temp * pow;
            }
            // 如果当前位上的数字是1
            else if (num == 1) {
                // 加上高位对应的数字,和低位的所有,再加1(它本身)。
                // 比如10,虽然低位是0,但本身还有1
                total += temp * pow + low + 1;
            }
            // 如果当前位上的数字大于1
            else {
                // 那么高位+1
                total += (temp + 1) * pow;
            }

            // 低位
            low += num * pow;
            // 进入下一位
            pow = pow * 10;
        }

        return total;
    }
}

提交OK。

我们来分析一下复杂度:

  • 时间复杂度 O(log N) :循环内的计算操作使用 O(1) 时间,循环次数为数字 n 的位数,即 log 以10为底 n,因此总时间为 O(log N)
  • 空间复杂度 O(1) :只有几个变量使用常数大小的额外空间。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。本题主要在于找规律,从一个例子开始,总结出其中的规律。

有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。

https://death00.github.io/

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java面试-动态规划与组合数

    最近在刷力扣上的题目,刷到了65不同路径,当初上大学的时候,曾在hihocoder上刷到过这道题目,但是现在已经几乎全忘光了,大概的知识点是动态规划,如今就让我...

    健程之道
  • 力扣289——生命游戏

    根据 百度百科 ,生命游戏,简称为生命,是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

    健程之道
  • 力扣739——每日温度

    根据每日气温列表,请重新生成一个列表,对应位置的输入是你需要再等待多久,温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

    健程之道
  • 杭电5178 (二分练习!)

    pairs John has n points on the X axis, and their coordinates are (x[i],0),(i=0,...

    用户7727433
  • 编写程序交换两个数字而不使用第三个变量?

    用户4645519
  • 算法训练营-第一周-数组链表

    栈是一种线性逻辑结构,栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底,最后进入的元素存放的位置叫栈顶。

    编程之心
  • 每日一题[LeetCode 315]计算右侧小于当前元素的个数

    给定一个整数数组nums,按要求返回一个新数组counts。数组counts有该性质:counts[i]的值是nums[i]右侧小于nums[i]的元素的数量。

    godweiyang
  • Java的基础程序设计结构(Java学习-1)

    注释就是方便自己或者别人阅读代码,绝大多数的程序语言都有注释这个功能,大部分的注释命令都是相同的或者想通的,

    营琪
  • 219. Contains Duplicate II

    Given an array of integers and an integer k, find out whether there are two dist...

    luozhiyun
  • andriod游戏音效

    同学们在玩游戏的时候应该都会发现游戏中会有两种形式来播放音乐 ,一般设置选项中会明确标明 设置游戏音乐 与设置游戏音效。 客观的分析一下这两种形式的音乐,游戏背...

    xiangzhihong

扫码关注云+社区

领取腾讯云代金券