【剑指offer】-1～n整数中1出现的次数-31/67

拼搏现实的明天。 2023-02-21 06:58 6阅读 0赞

# 1. 题目描述 #

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

# 2. 题目分析 #

1.  最常见做法和想到的就是从1~n依次遍历，然后遍历每一个数字的每一位数，判断其是不是等于1，累加return
2.  这是介绍一种新的解法，类似找规律的样子
3.

![在这里插入图片描述][2020062918340855.png]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]

# 3. 题目代码 #

public static int NumberOf1Between1AndN_Solution(int n) {
        
    		int sum = 0;
    		int hight = n / 10;
    		int low = 0;
    		int cur = n % 10;
    		int dight = 1;
    		// 4356
    		while (hight != 0 || cur != 0) {
        
    			if (cur == 0) {
        
    				sum += dight * hight;
    			} else if (cur == 1) {
        
    				sum += dight * hight + low + 1;
    			} else if (cur >= 2) {
        
    				sum = sum + dight * (hight + 1);
    			}
    			low = low + cur * dight;
    			cur = hight % 10; // 5
    			dight = dight * 10; // 10
    			hight = hight / 10; // 43
    		}
    		return sum;
    	}

[2020062918340855.png]: https://img-blog.csdnimg.cn/2020062918340855.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200629183333520.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5,size_16,color_FFFFFF,t_70