剑指offer|整数中1出现的次数（从1到n整数中1出现的次数）

待我称王封你为后i 2022-01-28 05:21 278阅读 0赞

【题目描述】  
求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

时间限制：1秒 空间限制：32768K 热度指数：178594

【解题思路】

**法一：** 将范围内的所有数字拼接成一个字符串，数字符串里的1的个数

程序如下，可以看到运行时间比较久。

public class Solution {
        
        // 59ms 11736 O(n)
        public int NumberOf1Between1AndN_Solution(int n) {
        
            StringBuilder sb = new StringBuilder();
            for(int i = 1; i <= n; i++){
        
                sb.append(i);
            }
            String str = sb.toString();
            int count = 0;
            for(int i = 0; i < str.length(); i++){
        
                if(str.charAt(i) == '1')
                    count++;
            }
            return count;
        }
    }

**法二：** 找寻规律  
依次考虑个位、十位、百位、千位……可能出现1的次数，他们满足一个共同的规律。依据此编程即可。规律来自：[https://www.cnblogs.com/xuanxufeng/p/6854105.html][https_www.cnblogs.com_xuanxufeng_p_6854105.html]

我们从一个5位的数字讲起，以考虑**百位为1**的情况为例。分3种情况讨论：

**1. 百位数字>=2 example: 31256** 当其百位为>=时，有以下这些情况满足(为方便起见，计312为a，56为b)：

0100 ~ 0199

1100 ~ 1199

…

31100 ~ 31199

余下的都不满足！

因此，百位>=2的5位数字，其百位为1的情况有（a/10+1）\*100 个数字 （a/10+1）=>对应于 0 ~ 31，且每一个数字，对应范围是100个数（末尾0-99）

**2. 百位数字 ==1 example: 31156** 当其百位为1时，有以下这些情况满足：

0100 ~ 0199

1100 ~ 1199

…

30100 ~ 30199

31100 ~ 311 56

因此，百位为1的5位数字，共有（a/10）\*100+(b+1)

**3. 百位数字 ==0 example: 31056** 当其百位为0时，有以下这些情况满足：

0100 ~ 0199

1100 ~ 1199

…

30100 ~ 30199

其余都不满足

因此，百位数为0的5位数字，共有 (a/10)\*100 个数字满足要求

我们可以进一步统一以下表达方式，即当百位>=2或=0时，有\[(a+8)/10\]\*100，当百位=1时，有\[(a+8)/10\]\*100+(b+1)。用代码表示就是：  \[(a+8)/10\]\*100+(a%10==1)?(b+1):0；

为什么要加8呢？因为只**有大于2的时候才会产生进位等价于（a/10+1）**，当**等于0和1时就等价于(a/10)**。另外，等于1时要单独加上(b+1)，这里我们用**a对10取余是否等于1**的方式判断该百位是否为1。

以下是这个非常优秀的解法的代码：

public class Solution {
        
        // 17ms 9464K
        public int NumberOf1Between1AndN_Solution(int n) {
        
            int ones = 0;
            for(long m = 1; m <= n; m *= 10){
        
                ones += ((n/m)+8)/10*m+((n/m%10) == 1 ? (n%m+1) : 0);
            }
            return ones;
        }
    }

【反思】  
自己尝试去考虑了个位为1的情况，大概验证，是符合这个规律的。拿到这个题指出笔者就猜想这是一道需要找规律的题，尝试着找规律，但未进行分类，导致越分析越乱。规律是有迹可循的，是要依据一定的分类方式，这个解法简单易懂，比《剑指offer》里的长篇累牍清晰多了。可以看出在这个过程中运用了分类的思想、提取共性的思想。难是不难，但自己就是无法独自分析出来，以后一定要头脑冷静，加强锻炼这方的能力。

[https_www.cnblogs.com_xuanxufeng_p_6854105.html]: https://www.cnblogs.com/xuanxufeng/p/6854105.html