刚刚做的一道原创算法题，题目简单，做起来难，大家看看有什么想法

[lhx2008]

输入：n (1 < n < 10^9)

从 1 开始到 n，转成字符串，然后拼接在一起

输出：这个字符串的长度

---

比如：

输入 13

拼接：12345678910111213

输出 17

---

特别注意：

时间限制 0.01s 一个数，也就是说不能真的做字符串拼接

[lhx2008]

我是花了 40 分钟才做出来，时间复杂度 O(length(n))

[njlcazl]

看着像数位 dp 的题

[orangeade]

对每个数按位数分类，然后统计？

[orangeade]

13：9 ＊ 1 ＋ 4 ＊ 2，
看下 n 的位数，如果是 n=123，就是 9 ＊ 1 ＋ 90 ＊ 2 ＋(123 － 100 ＋ 1)＊ 3
找下规律就行

[Biggoldfish]

今天美团的笔试题吧，就是楼上的思路。AC 代码：
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int T;
cin >> T;
int n = 0, digits = 0;
long long ans = 0;
long long pow10 = 0;
while(T--){
cin >> n;
digits = (int)log10(n);
pow10 = rint(pow(10,digits));
ans = digits * pow10 + (1 - pow10) / 9;
ans += (n - pow10 + 1) * (digits + 1);
cout << ans << endl;
}
return 0;
}

[casparchen]

有公式啊，O(1)

```
from math import floor, log10
solve = lambda n: (n+1)*floor(log10(10*n)) - (10**floor(log10(10*n))-1)/9
```

[tautcony]

数数题嘛。设数字为 n，len 为 n 的位数，nine 为 len-1 个 9。ans+=len*(n-nine)，然后 n=nine 的，重复操作到只剩个位数就好了。

[casparchen]

>>>solve(13)
17
>>>solve(123456700)
999999198

[ech0x]

先将 n 拆分成 n=99....99+m,9 的个数不定,接下去就是数字个数乘以位数 ，这就是个数学问题了。至于位数，我觉得就是这题允许的一个小 trick，转换一个数字到字符串然后获得长度，这个长度就是位数。

[lhx2008]

@casparchen 这个太强了

[lhx2008]

@Biggoldfish 是的，是这个搞法

[msg7086]

放一个简单点的算法：

def solve n
　 n = n + 1
　 digit = 0
　 scale = 1
　 while scale < n
　　 digit += n - scale
　　 scale *= 10
　 end
　 digit
end

solve 13
# => 17
solve 123456700
# => 999999198

可能比 log10 大法慢一点，但是都是基本运算，比较容易读。

[lhx2008]

@msg7086 这个写的也很好，是有公式吗

[msg7086]

@lhx2008
你这么想，1-9 是一位的，10-99 是两位的，100-999 是三位的。
所以 solve(123) 的位数就是，个位 1~123 十位 10~123 百位 100~123 再相加。

也就是
digit = 0
digit += 123 - 1 + 1
digit += 123 - 10 + 1
digit += 123 - 100 + 1

转写一下就会变成
digit = 0; scale = 1
digit += 123 - scale + 1; scale *= 10
digit += 123 - scale + 1; scale *= 10
digit += 123 - scale + 1; scale *= 10

然后写成循环就好了。

[msg7086]

这题写成 One liner 也不难的：

def solve n
0.upto(9).map{ |scale| [n + 1 - 10 ** scale, 0].max }.sum
end

solve 123456700
# => 999999198

[easylee]

希望 V 社区多来些这样的面试算法题，还是挺有趣的。

[Bryan0Z]

@msg7086 机智，我刚刚看了代码半天没看懂

[ericls]

这种题有啥意思……

[kifile]

long number=xxxxxxx;
long length=0;
while(number>0){
length+=number;
number/=10;
}
return length;

[pkookp8]

既然不用拼接，那就是数学题了。。。。