薯队长
通过率70%
题目描述
薯队长在平时工作中需要经常跟数字打交道，某一天薯队长收到了一个满是数字的表格，薯队长注意到这些数字里边很多数字都包含1，比如101里边包含两个1，616里包含一个1。
请你设计一个程序帮薯队长计算任意一个正整数n(0
输入描述:
正整数n(0
输出描述:
从1到n（包括n）的所有整数数字里含有多少个1
示例
输入
13
输出
复制
6
说明
从1到13（包括13）有13个数字，其中包含1的数字有1，10，11，12，13，这些数字里分别有1，1，2，1，1个1，所以从1到13（包括13）的整数数字中一共有1+1+2+1+1=6个1
基本思路
计算出每一个数中含有1的个数，然后不断叠加。
代码如下
#include <stdio.h> #include <string.h> #define MAX 1000 int GetValue(int a); int CountBit(int a); int Count1Function(int a, int bits); int main() { int number; int i,j,databit; int data[MAX] = {0}; scanf("%d",&number); //不断叠加 for(i = 0; i <= number; i++){ databit = CountBit(i); data[0] += Count1Function(i,databit); for(j = 0; j < MAX; j++){ //不断的累积，将所有的1相加 if(data[j] >= 10){ data[j] = data[j]%10; data[j+1]++; } } } //反向打印 for(i = MAX - 1; data[i] == 0; i--); for(; i >= 0; i--){ printf("%d",data[i]); } return 0; } //判断当前数有几位 int CountBit(int a) { int i = 0; while(a){ a = a/10; i++; } return i; } //得到需要相减的差值大小 int GetValue(int a) { int i = 1; while(a-1){ i = i*10; a--; } return i; } //判断当前数有几个1 int Count1Function(int a, int bits) { int i=0,value,dvalue; while(bits){ dvalue = GetValue(bits); value = a / dvalue; if(value == 1){ i++; } a = a % dvalue; bits--; } return i; }
不过由于不能完全通过，应该是时间复杂度太高。
参考以下是100%通过代码
#include<iostream> using namespace std; int main() { long long res = 0,n; long long left=0, right = 0, base = 1; cin>>n; if(n<=0) cout<<0<<endl; else{ while (n>=base) { left = n/base; right = n%base; if((left%10)>1) res+= (left/10+1)*base; else if((left%10)==1) res+=(left/10)*base+(right+1); else res+=(left/10)*base; base *=10; } cout<<res<<endl; } return 0; }
