PAT甲级1049

原题

The task is simple: given any positive integer N, you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1’s in 1, 10, 11, and 12.
Input Specification:
Each input file contains one test case which gives the positive N (≤2​30​​).
Output Specification:
For each test case, print the number of 1’s in one line.
Sample Input:
12

Sample Output:
5

大体翻译

输入整数N，求1到N的整数中1的个数
例如10：1的个数为1个
例如11：1的个数为2个
题中的例子12：从1到12，有1的整数为1、10、11、12，这些整数的1的总数为5
输出总数

整体思路

因为int类型的范围为 -2³¹ ~ (2³¹-1) ， 此题的范围为2³⁰ ， 在范围之内，所以直接定义整数N即可
从1开始遍历到N：
编写函数get_one得到单个整数中1的个数，并返回
将每次遍历的sum相加
输出遍历完成后的sum

第一次编写

代码如下：

#include <iostream>
using namespace std;
int get_one(int n) 
{
	int a, sum = 0;
	while (n > 0)
	{
		a = n % 10;
  		if (a == 1)
   		sum++;
  		n = n / 10;
 	}
 	return sum;
}
int main() {
 	int N;
 	cin >> N;
 	int sum = 0;
 	for (int i = 1;i <= N;i++) {
  		sum += get_one(i);
 	}
 	cout << sum;
 	return 0;
}

结果：
此时的时间复杂度为 O(N*logN)
判断单个整数的每一位需要的时间为 logN

第二次编写

因此需要更直接的解法，查询百度后得出来直接的解法，直接得出整数N以内1的个数：
factor代表当前位，个位为1，十位为10，以此类推
对于每一位(cur)而言
低位(low)是低于当前位的所有位，例如：12345，百位的低位是45
高位(high)同理，例如：12345，百位的高位是12
当cur为0的时候，等于：高位对应的位数（例如：百位就是100，十位就是10）
sum+=high x factor;
当这位为1的时候，等于：高位对应的位数+（低位+1）
sum+=high x factor+low+1;
当这位为大于1的时候，等于（高位+1）*对应的位数
sum+=(high+1) x factor;

代码如下：

#include <iostream>
using namespace std;
//对于每一位而言
//低位是低于当前位的所有位，例如：12345，百位的低位是45
//高位同理，例如：12345，百位的高位是12
//当这位为0的时候，等于：高位*对应的位数（例如：百位就是*100，十位就是*10）
//当这位为1的时候，等于：高位*对应的位数+（低位+1）
//当这位为大于1的时候，等于（高位+1）*对应的位数
int get_one(int n) 
{
 int factor = 1;//从最低位开始
 int cur = 0, low = 0, high = 0;//当前位，低于当前位的值，高于当前位的值
 int sum = 0;//1的总数
 while (n / factor) //循环位数次/例：123，循环3次
 {
  cur = (n / factor) % 10;
  high = n / (factor * 10);
  low = n % factor;
  //cout << low << " " << cur << " " << high << endl;
  switch (cur)
  {
  case 0:sum += high * factor;break;
  case 1:sum += high * factor + low + 1;break;
  default:sum += (high + 1)*factor;break;
  }
  factor *= 10;//前一位
 }
 return sum;
}

int main() {
 int n;
 cin >> n;
 cout<<get_one(n);
 return 0;
}

结果：