【PAT甲级 - C++题解】1049 Counting Ones

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1049 Counting Ones (pintia.cn)
🔑中文翻译：1 的个数
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

1049 Counting Ones

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³⁰).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:

12
1

Sample Output:

5
1

题意

给定一个数字 N ，请你计算 1∼N 中一共出现了多少个数字 1 。

例如，N=12 时，一共出现了 5 个数字 1 ，分别出现在 1,10,11,12 中。

思路

具体思路在剑指offer中有详细讲解，传送门放在这里啦：

剑指offer 44. 从1到n整数中1出现的次数

代码

#include
using namespace std;

int cal(int n)
{
    //将数字中每一位存入数组中
    vector<int> nums;
    while (n)    nums.push_back(n % 10), n /= 10;

    //从最高位往最低位遍历
    int res = 0;
    for (int i = nums.size() - 1; i >= 0; i--)
    {
        int left = 0, right = 0, power = 1;
        //获取当前位置左边的数字
        for (int j = nums.size(); j > i; j--)  left = left * 10 + nums[j];
        //获取当前位置右边的数字以及当前所在位数
        for (int j = i - 1; j >= 0; j--)
        {
            right = right * 10 + nums[j];
            power *= 10;
        }

        //根据当前位置的数字计算答案
        if (nums[i] == 0)  res += left * power;
        else if (nums[i] == 1) res += left * power + right + 1;
        else    res += (left + 1) * power;
    }

    return res;
}

int main()
{
    int n;
    cin >> n;

    cout << cal(n) << endl;

    return 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