面试题整理3

Posted on Edited on In

继续整理《Cracking the Coding Interview》。

18.4 2的个数

请编写一个方法，输出0到n(包括n)中数字2出现了几次。

给定一个正整数n，请返回0到n的数字中2出现了几次。

也是Leetcode原题，面试的时候很喜欢出这种题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Count2 
{
public:
	int countNumberOf2s(int n) 
	{
		int flag = 1;
		int high = 0;
		int low = 0;
		int cur = 0;
		int res = 0;
		while (n / flag)
		{
			low = n - (n / flag)*flag;
			cur = (n / flag) % 10;
			high = n / (flag * 10);
			if (cur < 2)
			{
				res += flag*high;
			}
			else if (cur == 2)
			{
				res += flag*high + low + 1;
			}
			else if (cur > 2)
			{
				res += flag*(high + 1);
			}
			flag *= 10;
		}
		return res;
	}
};

按每一位考虑，1-9都可以按照上面写出来，0有些特殊，但思路一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
ll countNumberOfxs(ll n,ll x) 
{
	ll flag = 1;
	ll high = 0;
	ll low = 0;
	ll cur = 0;
	ll res = 0;
	while (n / flag)
	{
		low = n - (n / flag)*flag;
		cur = (n / flag) % 10;
		high = n / (flag * 10);
		if (cur < x)
		{
			res += flag*high;
		}
		else if (cur == x)
		{
			res += flag*high + low + 1;
		}
		else if (cur > x)
		{
			res += flag*(high + 1);
		}
		flag *= 10;
	}
	return res;
}

ll countNumberOf0(ll n)
{
	ll flag = 1;
	ll high = 0;
	ll low = 0;
	ll cur = 0;
	ll res = 0;
	while (n / (flag*10))
	{
		low = n - (n / flag)*flag;
		cur = (n / flag) % 10;
		high = n / (flag * 10);
		if (cur == 0)
		{
			res += flag*(high - 1) + low + 1;
		}
		else 
		{
			res += flag*high;
		}
		flag *= 10;
	}
	return res;
}