【PAT甲級】Counting Ones

• 2019 年 11 月 8 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 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;  }