带你快速刷完67道剑指offer

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# No31、整数中1出现的次数( 从1 到 n 中1出现的次数 )

牛客网原题链接 (opens new window)

# 题目描述

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数?

为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。

ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

输入

13
1

返回值

6
1

# 1、经典方法吗,真的想不到这种方法,我服了

执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗:5.8 MB, 在所有 C++ 提交中击败了100.00%的用户

分两种情况,例如:1234和2234,high为最高位,pow为最高位权重 在每种情况下都将数分段处理,即0-999,1000-1999,...,剩余部分

case1:最高位是1,则最高位的1的次数为last+1(1000-1234) 每阶段即0-999的1的个数1*countDigitOne(pow-1) 剩余部分1的个数为countDigitOne(last)--最高位已单独计算了

case2:最高位不是1,则最高位的1的次数为pow(1000-1999) 每阶段除去最高位即0-999,1000-1999中1的次数为high*countDigitOne(pow-1) 剩余部分1的个数为countDigitOne(last) 发现两种情况仅差别在最高位的1的个数,因此单独计算最高位的1(cnt),合并处理两种情况

 int NumberOf1Between1AndN_Solution(int n)
    {
    if (n <= 0) return 0;
	if (n < 10) return 1;
	int high = n, pow = 1;// // 取出最高位 以及 最高位的权重
	while (high >= 10) {
		high /= 10;
		pow *= 10;
	}
	int last = n - high * pow;// 除最高位的数字
	int cnt = high == 1 ? last + 1 : pow;// high是否为1,最高位的1个数不同
	return cnt + high * NumberOf1Between1AndN_Solution(pow - 1) + NumberOf1Between1AndN_Solution(last);

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 二刷:

# 超级好的方法

运行时间:2ms 占用内存:376k

    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n <= 0) return 0;
        if(n < 10) return 1;
        int high = n,pow = 1;//首选求的最高位high和权重pow 10 还是100 还是 100 呢
        while(high>=10){
            high = high /10;
            pow = pow * 10;
        }
        int last = n - high*pow;
        int cut = (high == 1? last + 1:pow );
        return cut + high*NumberOf1Between1AndN_Solution(pow - 1) + NumberOf1Between1AndN_Solution(last);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

# 三刷:

    int NumberOf1Between1AndN_Solution(int n)
    {
        if(n <= 0) return 0;
        if(n< 10 ) return 1;
        if(n == 10) return 2;
        int pow = 1, high = n,last = 0;
        while(high >= 10){
            high = high/10;
            pow *=10;
        }
        last = n - high*pow;// 除去最高位的数字,还剩下多少 0-999 1000- 1999 2000-2999 3000 3345
        int cut = high == 1 ? last+1: pow;
        
        return cut + high*NumberOf1Between1AndN_Solution(pow-1) + NumberOf1Between1AndN_Solution(last);

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

力扣 (opens new window)上有类似的题目