每日一题 - 剑指 Offer 43. 1～n整数中1出现的次数

每日一题 - 剑指 Offer 43. 1～n整数中1出现的次数

题目信息

时间： 2019-07-01

题目链接：Leetcode

tag： 整除 取余 规律 递归

难易程度：中等

题目描述：

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例1:

输入：n = 12 输出：5

示例2:

输入：n = 13 输出：6

提示

1. 1 <= n < 2^31

解题思路

本题难点

数字 n 是个 x 位数，记 n 的第 i 位为 n i ，则可将 n 写为 nx nx−1⋯n2 n1，n的位数都可能为1。

具体思路

将 1 ~ n 的个位、十位、百位、…的 1 出现次数相加，即为 1 出现的总次数。

某位中 11出现次数的计算方法：

根据当前位 cur 值的不同，分为以下三种情况：

cur = 0：此位 1的出现次数只由高位 high决定，high×digitcur=1： 此位 1的出现次数只由高位 high和地位low决定，high×digit+low+1cur !=1：此位 1的出现次数只由高位 high决定，(high+1)×digit

代码

class Solution { public int countDigitOne(int n) { //设计按照 “个位、十位、...” 的顺序计算 int digit = 1,res = 0; int high = n / 10 ,cur = n% 10,low = 0; //当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出 while(high != 0 || cur != 0){ if(cur == 0){ res += high * digit; }else if(cur == 1){ res += high * digit + low + 1; }else{ res += (high + 1) * digit; } //将 cur 加入 low ，组成下轮 low low += cur * digit; //下轮 cur 是本轮 high 的最低位 cur = high % 10; //将本轮 high 最低位删除，得到下轮 high high /= 10; //位因子每轮 × 10 digit *= 10; } return res; } }

复杂度分析：

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

其他优秀解答

解题思路

f(n))函数的意思是1～n这n个整数的十进制表示中1出现的次数，将n拆分为两部分，最高一位的数字high和其他位的数字last，分别判断情况后将结果相加。

示例1:

例子如n=1234，high=1, pow=1000, last=234 可以将数字范围分成两部分1~999和1000~1234 1~999这个范围1的个数是f(pow-1) 1000~1234这个范围1的个数需要分为两部分： 千分位是1的个数：千分位为1的个数刚好就是234+1(last+1)，注意，这儿只看千分位，不看其他位 其他位是1的个数：即是234中出现1的个数，为f(last) 所以全部加起来是f(pow-1) + last + 1 + f(last);

示例2:

例子如3234，high=3, pow=1000, last=234 可以将数字范围分成两部分1~999，1000~1999，2000~2999和3000~3234 1~999这个范围1的个数是f(pow-1) 1000~1999这个范围1的个数需要分为两部分： 千分位是1的个数：千分位为1的个数刚好就是pow，注意，这儿只看千分位，不看其他位 其他位是1的个数：即是999中出现1的个数，为f(pow-1) 2000~2999这个范围1的个数是f(pow-1) 3000~3234这个范围1的个数是f(last) 所以全部加起来是pow + high*f(pow-1) + f(last);

代码

class Solution { public int countDigitOne(int n) { return f(n); } private int f(int n ) { if (n <= 0) return 0; String s = String.valueOf(n); int high = s.charAt(0) - '0'; int pow = (int) Math.pow(10, s.length()-1); int last = n - high*pow; if (high == 1) { return f(pow-1) + last + 1 + f(last); } else { return pow + high*f(pow-1) + f(last); } } }