趣味编程思维 十

在游戏节目中，参赛者会得到一个数字。他们可以通过点击一个按钮来增加或减少一个数字中的一个数字。他们需要在尽可能少的点击次数中使所有的数字都相等。例如，如果数字114，点击三次, 将一个数字减少三次，给出111。

对于以下每一个数字，使所有数字相等所需的最少点击次数是多少？

A. 2393

B. 99478

C. 5559993321

暴力枚举算法

def disCount(s): #字符串转换位数字数组
    distances = []
    s = [int(i) for i in s]
    for i in range(min(s),max(s)+1):
        distances.append((i,sum([abs(i-j) for j in s])))
    return min(distances,key=lambda x:x[1])
s = '5559993321'
print(disCount(s))

s = '99478'
print(disCount(s))

s = '2393'
print(disCount(s))

OUTPUT:

(5, 23)
(8, 7)
(3, 7)

考察思路的训练任务，往往需要从算法角度找到简单且可重复执行的步骤；
因为每一条线路逐一枚举往往效率不足，耗费时间过长！
特别是任务规模庞大，例如遇到远超过下面三个任务的100 * 100的方阵

image.png image.png image.png

S 出发到，相邻的2个节点标记拿到的金币数量, 放入该节点的数组大到小排序存放，取最大的值，遍历到相邻的2个节点(向右或向左），前一个节点的值与该节点金币相加，再取最大值标记，重复以上步骤直到F点，若干个值中取最大即可

image.png