最接近的数字

本题目从如下链接看到:

https://blog.csdn.net/svitter/article/details/78490322

原文作者也提供了解题思路

题目

一个K位的数N

(K \leq 2000 ， N \leq 10 20)

找出一个比N大且最接近的数，这个数的每位之和与N相同，用代码实现之。

例如：数 50 每位数之和是 5,

与50最接近的数是 104,

104 每位数之后也是 5；

112 所求数为121；

8 -> 17

10 -> 100

91 -> 118

1999000 -> 2000899

29399 -> 29489

本题的难点是, 数据的位数,可以达到1000多位,

这就直接否决了,用数字逐个遍历的解法.

突破点是, 最接近的数, 而且还要比给定的数大.

所以, 广泛的情况是, 高位数 +1, 低位数-1, 这样得出来的数肯定就是位数之和是相等的

但特别的情况是像 50 19 的情况

# 需要计算的数字列表
calc_list = [1, 0, 0, 9]
# 打印 计算的数字列表的和
print(sum(calc_list))

# 倒序遍历数字列表
# 第 i 位 -1
# 第 i-1 位 +1

for i in range(len(calc_list)-1, -1, -1):
    ir0 = calc_list[i] - 1

    if i-1 >= 0:
        ir1 = calc_list[i-1] + 1
        # 如果 i 位 -1 和 i+1 位 +1, 都满足条件时,
        # 则找到数据
        if 0 < ir0 < 10 and 0 < ir1 < 10:
            calc_list[i] = ir0
            calc_list[i-1] = ir1
            # 特殊情况, 如果是最高位符合条件
            # 因为要找大于目标数的最接近的数
            # 所以,在最高位+1的情况下, 后续位数,可以按从小到大重新排列
            if i - 1 == 0:
                l2 = calc_list[1:]
                l2.sort()
                calc_list[1:] = l2
            break
    else:
        # 原最高位 -1
        calc_list[i] = ir0
        # 增加1位最高位,为1的
        calc_list.insert(0, 1)
        # 在最高位为1的情况下, 后续数字列表进行从小到大排序
        l2 = calc_list[1:]
        l2.sort()
        calc_list[1:] = l2

# 结果数字列表
# 打印被计算出来的数字列表
print(calc_list)
# 打印被计算出来的数字列表的和
print(sum(calc_list))

View Code

如上代码的核心处理就是, 高位+1, 低位-1.

测试了部分特殊数据,都是正确的,

但不能保证,是否适用所有数据.