爱奇艺已知错位和SUM求原数X的题目的完美解法

#只用数字a组成order位数
#例如extend(2,3)=222, extend(4,2)=44
def extend(a, order):
     result = 0
     while order>0:
         order -= 1
         result = result*10 + a
     return result

#返回数字n的最高位数字,以及这是第几位。
#个位按第一位算起
def topDigit(n):
     order = 1
     while n >= 10:
         n //= 10
         order += 1
     return n, order

def initn(s):
     n = int(s)
     cur = None
     last_order = len(s) + 1
     result = 0
     while n != 0:
         n0, order = topDigit(n)
         extend_n0 = extend(n0, order)
         if n >= extend_n0:
             cur = n0
             n -= extend_n0
         elif n0 == 1:
             cur = 9
             order -= 1
             n -= extend(9, order)
         else:
             cur = n0 -1
             n -= extend(cur, order)
         if last_order == order:
             return -1
         result += cur * 10**(order-1)
         last_order = order
     return result

我这个方法是考虑到X = a1 a2 a3 a4...这样
则sum = a1 a2 a3 a4... +
                    a1 a2 a3...+
                         a1 a2...+
                              a1...+
                                  ...
可以看出sum-a1 a1 a1...后(即把对角线上的a1全去掉)剩下的是X = a2 a3 a4...组成的sum。

这样时间复杂度是Sum的位数,也就是O(log_10 n)

另外就是什么时候判断没有X满足这样的Sum。看看代码返回-1的那行逻辑吧不细说了。

递归还是迭代循环都行。我这里写了循环形式。
#爱奇艺##算法工程师#
全部评论
这真的是完美解法吗。。
点赞 回复 分享
发布于 2017-10-30 00:16

相关推荐

2025-12-28 22:19
门头沟学院 Java
不敢追165女神:简历写得毫无特点,你说你要是大二或者大三找寒假实习到暑期实习这段时间,你的简历还能约到面试。但是你是研究生哥,面试官不会因为你是研究生而降低要求,反而会觉得你是研究生才学了这么一点?为什么我不找个同阶段的本科生?
简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务