【PAT甲级】Counting Ones

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/89045956

Problem Description：

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

解题思路：

我一开始的思路就是暴力破解，无脑将1~N转换成字符串，然后无脑for-each来数字符'1'出现的次数，果不其然?直接TLE！30分只得22分。

AC代码： TLE代码：

#include <bits/stdc++.h>
using namespace std;

int count1(int n)   //用来数从1到n出现了几个1
{
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        string temp = to_string(i);
        for(auto it : temp)
        {
            if(it == '1')
            {
                cnt++;
            }
        }
    }
    return cnt;
}

int main()
{
    int N;
    cin >> N;
    cout << count1(N) << endl;
    return 0;
}