爱奇艺已知错位和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的那行逻辑吧不细说了。
递归还是迭代循环都行。我这里写了循环形式。
#爱奇艺##算法工程师#

