PAT-ADVANCED1049——Counting Ones

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805430595731456

题目描述：

题目翻译：

1049 计算1的个数

任务很简单：给定任何正整数N，你应该计算从1到N的整数的十进制形式的1的总数。例如，给定N为12，在1, 10, 11, 12中有5个1。

输入格式：

每个输入文件包含用一个测试用例。该测试用例给出了一个正整数N(<= 2 ^ 30)。

输出格式：

对每个测试用例，在一行中输出1的个数。

输入样例：

输出样例：

知识点：数学

思路：统计每一位在1 ~ N的过程中可能出现1的次数

如果通过从1数到n一个个枚举来算1的个数，测试点4和测试点6会超时。

这个思路很巧妙，是分别统计每一位在1 ~ N的过程中可能出现的次数，再累加即得1的个数总和。以输入数据为30710来举例说明整个过程。

（1）以字符串的形式接收数据，遍历该字符串的每一位。

（2）对于字符串的首位（首位不可能是0），首位的左边没有数字，首位右边的数字是right。

a：如果首位是1，为了不超过N，对于右边的数字我们可以取0 ~ right，总共有right + 1种情况。

b：如果首位不是1，对于30710来说，1后面的数字可以取0 ~ 9999，共10000种情况。

（3）对于字符串的末位，末位的右边没有数字，末位左边的数字是left。

a：如果末位是0，则其左边可以取的范围是0 ~ left - 1，共left种情况，对于30710来说，末位0前面可以取0 ~ 3070。

b：如果末位不是0，则其左边可以取的范围是0 ~ left，共left + 1种情况。

（4）对于既不是字符串首位也不是字符串末位的情况，其左边的数字是left，右边的数字是right。

a：如果当前位的是0，则其左边可以取的范围是0 ~ left - 1，对于30710的中间的0来说，右边可以取的范围是0 ~ 999。共left * 1000种情况。

b：如果当前位的是1，对于30710的中间的1来说，当左边取0 ~ 306时，右边可以取0 ~ 9；当左边取307时，右边只能取0。

c：如果当前位既不是0也不是1，对于30710的中间的7来说，左边可以取0 ~ 30，右边可以取0 ~ 99。

时间复杂度是O(n ^ 2)，其中n为N的位数。空间复杂度是O(1)。

C++代码：

#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main() {
	string input;
	cin >> input;
	int result = 0;
	for(int i = 0; i < input.length(); i++) {
		if(i == 0) {
			if(input[i] == '1') {
				int right = 0;
				for(int j = 1; j < input.length(); j++) {
					right = right * 10 + input[j] - '0';
				}
				result += right + 1;
			} else {
				result += (int)pow(10, input.length() - 1);
			}
		} else if(i == input.length() - 1) {
			int left = 0;
			for(int j = 0; j < input.length() - 1; j++) {
				left = left * 10 + input[j] - '0';
			}
			result += left + 1;
			if(input[i] == '0') {
				result--;
			}
		} else {
			int left = 0, right = 0;
			for(int j = 0; j < i; j++){
				left = left * 10 + input[j] - '0';
			}
			for(int j = i + 1; j < input.length(); j++){
				right = right * 10 + input[j] - '0';
			}
			if(input[i] == '0'){
				result += left * (int)pow(10, input.length() - i - 1);
			}else if(input[i] == '1'){
				result += left * (int)pow(10, input.length() - i - 1) + right + 1;
			}else{
				result += (left + 1) * (int)pow(10, input.length() - i - 1);
			}
		}
	}
	printf("%d\n", result);
	return 0;
}

C++解题报告：

PAT-ADVANCED1049——Counting Ones

PAT-ADVANCED1049——Counting Ones

思路：统计每一位在1 ~ N的过程中可能出现1的次数

相关推荐