人生海海

我有时候会怀疑,解决复杂问题,是一种瘾。

这种复杂问题,包括一个解一个迷宫,拼一个乐高,做一道难题,通关一个超难的游戏。很多人一旦投入其中,就废寝忘食直到把它解决。甚至在解决之后,还继续不停寻找,然后接着沉迷其中。还比如,有类人被称为”工作狂“。他们加起班来没日没夜,多半也是陶醉在自己解决问题的”爱好“中。

从进化论的角度,也容易接受。那些生理上对解决问题有偏好的人,更容易被选择出来继续帮助自己的族群。同样的两个村庄,遇到干旱,有办法引水灌溉的,大概率会存活下来。从生理层面,也站得住脚。问题被解决,本身也有奖励性质。一旦自激,形成正循环,这种”成瘾“也就水到渠成。

既然是瘾,不妨再说一道Foobar的题,巩固一下我们的神经反射。

题目依旧是又臭又长。大意就是有一个量子油箱(一个数字),你可以选择三种操作,加一、减一或者减半(偶数时可)。问最少多少步,可以把这个数字变成1。

刚看完题,我心想,这是一道送分题啊。每次的操作固定,动态规划(DP)公式就基本确定了:

f(n) = min( f(n-1), f(n+1), f(n/2)  ) + 1

简单调试、加边界、优化,得出代码:

def solution(n):
    c = {0: 0, 1: 0, 2: 1, 3: 2}
    i = 4
    end = int(n)
    while i <= end:
        c[i] = min(c[(i+1)/2], c[(i-1)/2]) + 2 if i % 2 == 1 else c[i//2] + 1
        i += 1
    return c[end]

这里有个小优化,就是在选择操作时,优先选择”减半“。这个小”贪心“没有数学证明,不过如果想象一个二进制数100100,最快让他变小的操作,显然是右移,也就是”减半“。

通过了测试数据,又编了几个”大“数,也没什么毛病。提交……不出意外的又挂了。终于明白,简单的题目不可能是常态,踩坑才是。

回到题目,重新审题。在最后一段,找到了数据大小:

The fuel intake control panel can only display a number up to 309 digits long, so there won’t ever be more pellets than you can express in that many digits

原来是一个309位长的数字,还™说是”only“……不知道这到底是来自高山的俯视,还是深海的冷……

显然,300位长的数字,没法用默认类型来运算了。只能用近十年没用过的”数组“运算了。顾名思义,对于这种大数,可以把每一位分开,用一个数组存起来。四则运算时,模拟竖式,对每一位对应进行运算。

根据之前的分析,这三种操作可以对应成二进制数的加、减和右移操作。所以在用数组运算时,不妨直接换成二进制。将问题分解后,我们需要几个辅助函数

def plus1(b: array)   # 二进制数组加一
def minus1(b:array)   # 二进制数组减一
def divide2(b:array)  # 二进制数组右移
def convert_to_bin(s) # 十进制字符串转二进制

有了辅助函数,就又可以回到刚才的算法,分为四步走:

1. 转换10进制数组数字为2进制
2. 如果末位是0,则直接做除二操作,当前步数+1
3. 如果末位是1,则分别递归求解+1和-1操作,步数取其中较小的+1
4. 边界值是数字1

显然直接递归多半会挂掉,所以这里我选择用队列(queue)存储中间状态,及其对应步数。遇到状态重复时,可以果断剪掉步数太多的状态。

最终运算部分代码如下:

def calc(b):
    queue = [(b,0)]
    ans = len(b) * 2
    found = {tuple(b): ans}
    while len(queue) > 0:
        current, n = queue.pop(0)
        if current[0] == 1:
            if len(current) == 1:
                ans = min(ans, n)
                continue
            added = add1(current)
            key = tuple(added)
            if n+1 < found.get(key, ans):
                found[key] = n+1
                queue.append((added, n+1))
            minused = minus1(current)
            key = tuple(minused)
            if n+1 < found.get(key, ans):
                found[key] = n+1
                queue.append((minused, n + 1))
        else:
            while current[0] == 0:
                n += 1
                current.pop(0)
            tc = tuple(current)
            if n < found.get(tc,ans):
                found[tc] = n
                queue.append((current, n))
    return ans

这个题开始,题目开始变得复杂。

复杂的问题,要先分解,再逐个击破。

You Might Also Like
发表评论