天天看点

剑指offer(43 1~n整数中1出现的次数) 题解剑指offer-43 1~n整数中1出现的次数

剑指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、前端、小程序、产品相关学习资料,欢迎交流

剑指offer(43 1~n整数中1出现的次数) 题解剑指offer-43 1~n整数中1出现的次数