AcWing 56. 从1到n整数中1出现的次数
原题链接
困难
作者:
adamXu
,
2020-09-29 13:47:23
,
所有人可见
,
阅读 372
class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
if(n == 0) return n;
vector<int> numbers;
//eg 12345在numbers中存储为54321
while(n) numbers.push_back(n % 10),n /= 10;
int ans = 0;
for(int i = numbers.size() - 1;i >= 0;--i){
int left = 0,right = 0,t = 1; //分别记录当前选定数左边,右边的元素
for(int j = numbers.size() - 1;j > i;--j) left = left * 10 + numbers[j];
for(int j = i - 1;j >= 0;--j) right = right * 10 + numbers[j],t *= 10;
ans += left * t;
if(numbers[i] == 1) ans += right + 1;
else if(numbers[i] > 1) ans += t;
}
return ans;
}
};