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 (≤230).
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 。
例如，N=12 时，一共出现了 5 个数字 1 ，分别出现在 1,10,11,12 中。
思路
具体思路在剑指offer中有详细讲解，传送门放在这里啦：
代码
#include<bits/stdc++.h> 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; }
