欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

程序员面试金典 - 面试题 17.06. 2出现的次数(找递推规律)

程序员文章站 2024-03-04 09:42:11
...

1. 题目

编写一个方法,计算从 0 到 n (含 n) 中数字 2 出现的次数。

示例:
输入: 25
输出: 9
解释: (2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)

提示:
n <= 10^9

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-2s-in-range-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

同题:剑指Offer - 面试题43. 1~n整数中1出现的次数(找规律+公式)
按位遍历每个位,例如521
程序员面试金典 - 面试题 17.06. 2出现的次数(找递推规律)

class Solution {
public:
    int numberOf2sInRange(int n) {
        long i = 1, count = 0, high, cur, low;
    	while(n/i)//遍历每个位
    	{
    		high = n/(10*i);//高位
    		cur = (n/i)%10;//当前位
    		low = n-(n/i)*i;//低位
    		if(cur < 2)
    			count += high*i;
    		else if(cur == 2)
    			count += high*i+low+1;
    		else
    			count += (high+1)*i;
    		i *= 10;
    	}
    	return count;
    }
};

0 ms 5.9 MB