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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2410 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

输出：这个字符串的长度

比如：

输入 13

拼接：12345678910111213

输出 17

特别注意：

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

字符

拼接

输入

输出

20 条回复 • 2018-04-21 08:31:56 +08:00

lhx2008

2018-04-20 21:42:04 +08:00

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

njlcazl

2018-04-20 21:45:25 +08:00 via iPhone

看着像数位 dp 的题

orangeade

2018-04-20 21:49:19 +08:00 via Android

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

orangeade

2018-04-20 21:55:33 +08:00 via Android

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

Biggoldfish

2018-04-20 21:57:41 +08:00

今天美团的笔试题吧，就是楼上的思路。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

2018-04-20 22:00:21 +08:00

有公式啊，O(1)

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

tautcony

2018-04-20 22:00:49 +08:00 via Android

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

casparchen

2018-04-20 22:02:52 +08:00

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

ech0x

2018-04-20 22:05:06 +08:00

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

lhx2008

2018-04-20 22:09:43 +08:00

@casparchen 这个太强了

lhx2008

2018-04-20 22:11:26 +08:00

@Biggoldfish 是的，是这个搞法

msg7086

2018-04-20 22:29:18 +08:00

放一个简单点的算法：

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

2018-04-20 22:46:49 +08:00

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

msg7086

2018-04-20 23:46:25 +08:00

@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

2018-04-20 23:53:46 +08:00

这题写成 One liner 也不难的：

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

solve 123456700
# => 999999198