剑指offer-43 1~n整数中1出现的次数
微信搜索【程序员画工师】关注更多Java编程技术、数据结构与算法、面试题相关内容。
题目
输入一个整数n,求1~ n这n个整数的十进制表示中1出现的次数。例如输入12,包含1的数字有1、10、11、12,一共出现了5次。
思路1
依次遍历每个数,判断每个数里面是否包含1。
上代码
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n == 0){
return 0;
}
int countSum = 0;
int count = 0;
for(int i = 1;i <= n;i++){
count = numberOf1(i);
countSum += count;
}
return countSum;
}
public int numberOf1(int n){
int count = 0;
while(n>=1){
if(n % 10 ==1){
count ++;
}
n = n /10;
}
return count;
}
}
这样的话,就需要对每个数字都要做除法和求余运算,以求出该数字中1出现的次数。如果输入数字n,n有O(nlogn)位,就需要判断每一位是不是1,时间复杂度为O(nlogn)。
思路2-分析数字规律
牛客网的讨论区里有个很好也便于理解的思路:分析数字的规律来找到解法。
例如n=abcde五位数,我们分析百位的c,主要有以下三种情况:
1)当c == 0的时候,比如13013,此时百位出现1的是:00 100 ~ 00 199, 01 10001 199,……,11 100 11 199,1210012199共1300个,显然这个由高位数字决定,并且受当前位数影响,结果为:(高位数字)乘以(当前位数);
2)当c == 1的时候,比如13113,此时百位出现1的肯定包括c=0的情况,另外还需要考虑低位的情况即:00100 ~ 00113共114个,结果为:(高位数字)乘以(当前位数)+(低位数字)+1;
3)当c >= 2的时候,比如13213,此时百位出现1的是:00 100 ~ 00 199, 01 10001 199,……,11 100~ 11 199,12 100 ~ 12 199,13100~13199,共1400个,这个仅由高位数字决定,结果为:(高位数字+1)乘以当前位数。
上代码
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int res = 0;
int cur = 0, before = 0, after = 0;
for (int i = 1; i <= n; i *= 10) {
before = n/(i*10);
cur = (n/i)%10;
after = n - n/i*i;
if(cur == 0){
// 如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
res += before * i;
}else if(cur == 1){
// 如果为1, 出现1的次数由高位和低位决定,高位*当前位+低位+1
res += before * i + after + 1;
}else{
// 如果大于1, 出现1的次数由高位决定,(高位数字+1)* 当前位数
res += (before + 1) * i;
}
}
return res;
}
}
思路3-剑指
剑指offer中也提供了一种基于数字规律入手的解法,也很新颖和独到,但是可能不是很容易想到,有兴趣的读者可以参考。
References
[1] 《剑指offer(第二版)》 何海涛著
程序员画工师公众号,获取更多详细Java、Python、C、前端、小程序、产品相关学习资料,欢迎交流