输入:n (1 < n < 10^9)
从 1 开始到 n,转成字符串,然后拼接在一起
输出:这个字符串的长度
比如:
输入 13
拼接:12345678910111213
输出 17
特别注意:
时间限制 0.01s 一个数,也就是说不能真的做字符串拼接
1
lhx2008 OP 我是花了 40 分钟才做出来,时间复杂度 O(length(n))
|
2
njlcazl 2018-04-20 21:45:25 +08:00 via iPhone
看着像数位 dp 的题
|
3
orangeade 2018-04-20 21:49:19 +08:00 via Android
对每个数按位数分类,然后统计?
|
4
orangeade 2018-04-20 21:55:33 +08:00 via Android 5
13:9 * 1 + 4 * 2,
看下 n 的位数,如果是 n=123,就是 9 * 1 + 90 * 2 +(123 - 100 + 1)* 3 找下规律就行 |
5
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; } |
6
casparchen 2018-04-20 22:00:21 +08:00 7
有公式啊,O(1)
``` from math import floor, log10 solve = lambda n: (n+1)*floor(log10(10*n)) - (10**floor(log10(10*n))-1)/9 ``` |
7
tautcony 2018-04-20 22:00:49 +08:00 via Android
数数题嘛。设数字为 n,len 为 n 的位数,nine 为 len-1 个 9。ans+=len*(n-nine),然后 n=nine 的,重复操作到只剩个位数就好了。
|
8
casparchen 2018-04-20 22:02:52 +08:00
>>>solve(13)
17 >>>solve(123456700) 999999198 |
9
ech0x 2018-04-20 22:05:06 +08:00 1
先将 n 拆分成 n=99....99+m,9 的个数不定,接下去就是数字个数乘以位数 ,这就是个数学问题了。至于位数,我觉得就是这题允许的一个小 trick,转换一个数字到字符串然后获得长度,这个长度就是位数。
|
10
lhx2008 OP @casparchen 这个太强了
|
11
lhx2008 OP @Biggoldfish 是的,是这个搞法
|
12
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 大法慢一点,但是都是基本运算,比较容易读。 |
14
msg7086 2018-04-20 23:46:25 +08:00 4
@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 然后写成循环就好了。 |
15
msg7086 2018-04-20 23:53:46 +08:00 1
这题写成 One liner 也不难的:
def solve n 0.upto(9).map{ |scale| [n + 1 - 10 ** scale, 0].max }.sum end solve 123456700 # => 999999198 |
16
easylee 2018-04-21 00:55:48 +08:00
希望 V 社区多来些这样的面试算法题,还是挺有趣的。
|
18
ericls 2018-04-21 04:53:46 +08:00 via iPhone 1
这种题有啥意思……
|
19
kifile 2018-04-21 07:04:35 +08:00 1
long number=xxxxxxx;
long length=0; while(number>0){ length+=number; number/=10; } return length; |
20
pkookp8 2018-04-21 08:31:56 +08:00 via Android
既然不用拼接,那就是数学题了。。。。
|