Category: 算法

有这样一个面试题：已知哈夫曼树有121个叶子节点，求非叶子节点的个数

没接触过相关概念或者忘了的，我稍微用白话解释下：

哈夫曼树：将N个数据结构当叶子节点，以其某个域的值V作为权重，把这些叶子节点组合成一棵树（N个节点都要存在且仅作为叶子节点），使得所有叶子节点到树根的加权路径和最小，即距离D*V的总和最小
树的度：树中某个节点最多有几个

举例来说，如果给定列表[1,2,3,4,5]，组成一棵度为2的哈夫曼树，有如下步骤：

1、从中选择2个最小的构成一棵树，并计算构成后的树的权，1 + 2 = 3
2、将新构成的树重新加入列表得到：[4,5,3(1,2)]
3、如果新的列表大于2（度），跳转到步骤1，否则剩余节点全部加入一个根节点，完成构建

有了这些基本概念后，如何求解呢，我们先问下GPT看看

GPT-4给出的公式和推导过程如下：

首先，假设一棵度为m的哈夫曼树有n个叶子节点，x个非叶子节点，那么它的总节点数为n+x。
其次，观察这棵树的结构，可以发现除了根节点外，每个非叶子节点都有m个子节点，而每个叶子节点都没有子节点。所以，这棵树的总分支数为xm+0n，也就是xm。
再次，由树的基本性质可知，一棵有k个节点的树，它的分支数等于k-1。
所以，这棵树的总分支数也可以表示为n+x-1。 最后，将上面两个等式联立，得到xm=n+x-1，解得x=⌈(n-1)/ (m-1)⌉。

于是，补齐这个不满的节点可得的准确的表达式及其推导形式：

x * m = n + y + x - 1
x = ((n-1)+y)/(m-1)

根据前述两个断言，补齐的y个节点，数量在[0,m-2]闭区间内，可以不需要补齐，但绝对不会补齐m-1个（断言二），但注意y不等于n%m，以叶子节点5、度3的哈夫曼树为例，不需要补齐（第一层3个节点，两个叶子节点，第二层三个叶子节点），而不是需要补齐2个。而补齐的最终目的就是为了让每个非叶子节点可以有m个子节点，所以对(n-1)/(m-1)向上取整即可以达到目的，求出最少满足条件的x。

还有一种利用构建规律来计算的方法，比如每一轮合并后都会从n个节点内先扣除m个节点再加入一个非叶子节点，那么可以用(n-1)/(m-1)再向上取整来计算。这种方式得出的公式一致，但是很难解释n-1以及向上取整。而且，当度大于等于3时，哈夫曼树的构建已经不能直接找M个最小节点合并了，需要加入一些占位节点补齐，例如[1,1,1,1,1,1]这个数列，如果按最小M合并方法，将得到[6,3(1,1,1),3(1,1,1)]这棵非常对称的树，但他的加权路径和12不是最小的，而加入一个占位节点0，得到[0,1,1,1,1,1,1]，再利用最小M个节点合并法，将得到[6,1,2(0,1,1),3(1,1,1)]，他的加权路径和为11，比前面的更小。

这篇文章是尝试给像作者一样的算法爱好者（业余的委婉说法）解释一下编辑距离求解方法的思考过程，其实也是为了强迫自己真正的吃透编辑距离求解的方法论，以期能达到举一反三的效果。根据以上受众定位，我首先还是引入一段对编辑距离的解释，然后再从递归到递推（动态规划）讲讲对这个问题求解本身的正向思考过程，而不是拿到一个解法来说明它的正确性。

编辑距离的定义是用增删改三种操作将一个字符串演变为一个目标字符串所需的操作次数。比如将horse转化为ros，可以是如下步骤：
1）删除h变成orse； 2）删除o变成rse； 3）增加o变成rose； 4）删除e变成ros
也可以是如下步骤：
1）改h为r变成rorse； 2）删r变成rose； 3）删e变成ros
显然第二种策略要优于第一种，但是这种演变策略的排列组合随着源串a和目的串b的长度增长会几何级数的增长。我们需要用程序来求解。

这是一个典型的考动态规划的编程题，很多文章都会给出一个递推公式，但是这个递推公式为何正确，得到这个公式的思考过程是啥，为什么这么思考？回答了这几个问题才算理解了编辑距离的精髓，而且才能有举一反三的可能性。看了很多解释的文章，感觉都是从结果来理解和解释递推过程反证过程的有效性，隔靴搔痒，没有讲到这个公式是怎么得来的，怎么一下子就能得出这么精妙的计算方法，感觉就像现在解释机器学习模型的原理那样，训练出来一个有效的神经网络结构，然后再试图解释每一层是在干嘛，然而并不是一开始设计的时候就知道会是这样。但编辑距离这个算法是完全由人想出来的，必然是有设计者的心路历程可循。下面讲下我对这个问题的理解思路。

最容易想到的方法是递归，递归函数以目标字符串和源字符串为输入参数，代码如下：

def lev(a, b):
    if len(a) == 0 or len(b) == 0:
        return max(len(a),len(b))
    if a[0] == b[0]:
        return lev(a[1:],b[1:]) #首字符相等则跳过
    ADD = lev(a,b[1:]) # add b[0]到a的开始, 问题转化为求a,b[1:]的编辑距离，因为头部相同的字符不增加编辑距离
    DEL = lev(a[1:],b) # del a[0]
    REP = lev(a[1:],b[1:]) # set a[0] = b[0], 问题转为求a[1:],b[1:]，原因同计算a的解释
    return 1 + min(ADD,DEL,REP)

 

Continue reading “尝试讲清楚编辑距离求解”

LeetCode上一个中等难度的题，可以用递归，当然也可以用动态规划（这道题目的状态转移方程有点复杂，定义为中等让我感觉被鄙视了），下面先上动态规划的代码：

Continue reading “动态规划：括号生成”

这一题用递归很简单，直接深度优先搜索所有排序，取最大值即可，但是完全没有DP的思想而且求解时间不可接受；但是如果要DP，如何减少状态数？要知道本题的输入数列排序是影响最终结果的。

下面的解法是DP的，这个DP的妙处在于仍然用输入数列A的子数列组合As作为状态，但是这个状态下面仍然分一些子状态，不过不是用这个子数组的所有排序作为子状态而是用一种hash的方式，即将该子数组的可能结果（子数组每一种排序按题目算法所求得的状态值R=x+x^As[i]）对64（2的6次方）求余所得作为子状态的index。

为什么可以这么做？因为题目中数组A最大的数为50（6bit,可覆盖），所以在一个状态转移到下一状态时，即某个子数组新加入一个元素的时候，其实只需要考虑状态值R的低6位不同的情况即可，因为只有低6位有后效性，只有低6位相同的所有排序只需取最大状态值（这里不用求具体排序，主要求最大值），其他都不用考虑了，而不同的低6位值可能带来不同的有效子状态。说白了，就是当前低6位不一样的，现在不能判定以后谁优谁劣，而当前低6位相同的，已经可以毫无顾忌的进行优胜劣汰了。这样一来就大大减少了需要考虑的分支，于是求解效率就呈几何级数地提高了。

class Xscoregame:
    def getscore(self, a):
        s = {(0,0):0}
        n = len(a)

        ln = 1<<n
        for i in range(0, ln):
            for j in range(0, 64):
                if s.get((i,j), -1) < 0:
                    continue
                for idx,k in enumerate(a):
                    e = 1 << idx
                    if e & i > 0:
                        continue
                    t = s[(i,j)]
                    t += t ^ k
                    ni = i|e
                    nj = t%64
                    s[(ni, nj)] = max(s.get((ni, nj),-1), t)

        ret = 0
        nn = ln - 1
        for j in range(0, 64):
            ret = max(ret, s.get((nn,j),-1))

        return ret

if __name__ == "__main__":
    print Xscoregame().getscore([1,2,3])
    print Xscoregame().getscore([10,0,0,0])
    print Xscoregame().getscore([1,1,1,1,1,1])
    print Xscoregame().getscore([1,0,1,0,1,0,1,0])
    print Xscoregame().getscore([50,0,1,0,1,0,1,0,1,0,1,0,1,0,1])

 

这题显示只有18%的AC率，题目本身不难，估计都是败在执行时间上了；我的解法如下，典型的DP思维，子问题是：如果已知长度为n-1的情况下，和或操作相等的数列，求长度为n的情况；状态index为每个满足条件的数列的和Sn-1（因为和或相等，也是该数列的或），状态值为该index对应的数列有多少种。状态转移方程为:

if Xn | Sn-1 == Xn + Sn-1: then Stat[Xn|Sn-1] += Stat[Sn-1]

class YetAnotherORProblem2:
    def countSequences(self, n, r):
        ls = {0:1}
        c = 0
        mc = 1
        while mc < r:
            mc <<= 1
        mc -= 1

        for i in range(0, n+1):
            if i == n:
                for k,v in ls.items():
                    c += v
                return c%1000000009
            cs = {0:0}
            for k,v in ls.items():
                mask = mc^k
                # 这里是个重要的优化，大于mask+1的值不可能满足条件
                for j in range(0, mask+1):
                    if k & j == 0:
                        cs[k+j] =  cs.get(k+j, 0) + v
            ls = cs.copy()

 

又一次暴力求解被羞辱，这个题感觉一定可以for循环代替递归，然而经验值不足（智商感人的委婉说法😢）没能在放弃之前想出来，于是再次拿来主义：

点我展开代码和解析

这是一道标记为hard的题，确实比较hard

开始用了一个比较简单暴力的方法，其实也是DP思路，但是状态取的比较偷懒，直接用了所有的可能组合作为状态，虽然在求解过程中可以利用到已经搜索过的状态，但是整个搜索空间还是太大了，导致虽然结果正确，但是严重超时了：

class YetAnotherTwoTeamsProblem:
    def count(self, skill):
        ss = 0
        for i in skill:
            ss += i
        #skill.sort()
        mask = (1 << len(skill)) - 1
        stat = {0:0}
        sm = {0:100000}
        su = {}
        c = 0
        for idx,s in enumerate(skill):
            i = 1<<(idx+1)
            for j in stat.keys():
                n = i|j
                if i == j or stat[j] < 0 or stat.get(n, 1) < 0:
                    continue

                temp = s + stat[j]
                sm[n] = min(sm[j], s)
                h = su.get(temp, {}).get(sm[n], 0)
                stat[n] = temp
                if h != 0:
                    if h == -2:
                        c += 1
                        stat[mask^n] = -1
                    elif h == -1:
                        stat[mask^n] = -1
                    continue

                d = ss - temp
                if temp < d:
                    stat[n] = temp
                elif temp == d:
                    stat[n] = -1
                    stat[mask^n] = -1
                else:
                    if temp - d < sm[n]*2:
                        stat[n] = -2
                        stat[mask^n] = -1
                        c += 1
                    else:
                        stat[n] = -1
                ht = su.get(temp, {})
                if ht == {}:
                    su[temp] = {sm[n]:stat[n]}
                else:
                    ht[sm[n]] = stat[n]

        return c

又做了一次伸手党，看了解答后醒悟了，其实在我自己的解法中已经朦胧的利用了当前考察组合的skill总和作为状态。正解是采用了skill总和作为状态index。 点我展开分析内容

再来水一道简单题：题目地址

想法很自然，记录下当前的方向，一旦出现方向不一致的就把总数加一，同时方向改变，否则continue，然而其实已经包含了动态规划思想

上代码：

class ZigZag:
    def longestZigZag(self, seq):
        count = 1
        d = 0
        p = seq[0]
        for i in seq[1:]:
            if p == i:
                continue
            elif p < i:
                if d == 1:
                    p = i
                    continue
                else:
                    count += 1
                d = 1
            else:
                if d == -1:
                    p = i
                    continue
                else:
                    count += 1
                d = -1
            p = i

        return count

看了下别人提交的，思路一样，只不过有人上来先把整个序列的变化趋势算一遍，即遍历seq，然后算出seq[i]-seq[i-1]的值记录下来记为V[i]，其实要的就是一个正负号，然后再次遍历还是记录当前的方向，乘以当前遍历到的那个趋势V[i]，乘积发生变化时就在结果上加一并改变当前方向值。

为了兴趣，也为了保持coding的能力，重新开始写一些算法题；为了对算法了解的更透彻，也为了锻炼表达能力，干脆在博客里面对解题代码进行详解，代码是自己写的，但也不排除参考了别人的解法，消化吸收了就是自己的，不是吗？

题面：

太长了，就不贴了，链接在此

代码及详解：

class ZooExchangeProgram:
    def getNumber(self, label, lower, upper):
        l = list(label)
        # 这个r就是我们最后要通过各种现有label组的合并达到的目标集合
        r = range(lower, upper+1)

        # 简单的将无解的情况排除
        for i in r:
            if i not in l:
                return -1

        # 按照给定的目标集合，将所有在包含于目标集合的label组都整理出来
        groups = []
        start = 0
        for i,x in enumerate(l):
            if x not in r:
                if start < i:
                    groups.append(set(l[start:i]))
                start = i + 1
            elif i == len(l) - 1:
                groups.append(set(l[start:i+1]))

        # 去除重复的组，因为我们最终求解的是达成目标集合所需要最小的组数量，答案不用给出包含具体某个组的信息，所以去重不影响结果，只会加速求解；这一段代码体现了python的简洁，一个in关键字就可以代替C语言的compare函数，虽然背后的效率肯定比C低，但是这对让程序员关注算法本身提供了极大便利。当然还有其它更加高效的list of lists去重方法，比如使用库itertools，但是本题的限制了label的数量为50个之内，所以最多有50个组，双重循环一次也还能接受。
        ng = []
        for i in groups:
            if i not in ng:
                ng.append(i)

        # tricky part: 这里开始才是本题的精髓，使用的是动态规划；状态定义为某个组所覆盖的元素集合，或者多个组的并集所覆盖的元素集合，最终状态就是目标集合，而每个组，或者每种多组的并集所构成的所有状态都是中间状态；而且，达成同一种状态可能有多种组合形式；暴力求解方法就是搜索计算所有这些组构成的全部组合形式，将其中构成最终状态的组合记录下来，然后从中找到由最少组构成的组合；这种方法所需计算量非常大，因为其搜索过程中放弃了很多中间结果，为了搜索到一组可能解，过程中走过的弯路，在下一组求解中可能仍然要重新走一遍，这是极大的浪费；动态规划思想记录下搜索过程中的任何一次尝试结果。本题中，我们要纪录的就是每次搜索到某个中间状态时所需要的组合数，下次再组合出这种状态时，比较以前记录下来的值，如果本次组合数更小则更新记录；这样，只需遍历一次所有组合，就能得到所有可能的中间状态的最小组合数，届时只需要从中选择那个最终状态对应的组合数即可。
        count = [0] * 50
        state = {0:0}
        mode = []
        mask = 0
        ret = 0

        # 这里是为了优化程序的执行时间，需要将那些必须选入组合的组排除出我们搜索的范围，反正无论如何它们都得入选，我们干嘛还要去考虑它们呢，博主一开始就是没有排除它们，在提交后被判失败，自己测试发现其中一个case居然耗费了12s之多。哪些是必选的呢，就是那些包含了别人都没有的元素的组，到这里我们所说的组都是包含于目标集合的，所以有独一无二的元素的组必须入选。
        # 先计算所有目标集合中的元素哪些是只存在于一个组中的
        for i in ng:
            for j in i:
                count[j] += 1
        # 对独一无二的元素，我们单独处理，把它们排除在搜索范围（搜索范围的组构成mode）内，然后将它们所在的组的并集mask记录下来；其它的组计算出它们的状态值作为key保存在字典state里面，对应的value记为1，即这种状态显然只需要对应的单个组自己就能构成。
        # 之所以用字典，而不用list，因为list的索引必须是连续的，即使中间很多item都没有用到，也要为他们分配内存，这样的话会浪费大量的内存，比如我们这题当中的label最大可以到50，也就是说从1到50，这50个label会有1<<50种可能的状态组合，那我们需要一个1<<50，即1*2^50，即使用最小的byte型数组（python好像不能指定类型），那也是1024TB的内存，博主开始也没有意识到这个问题，直接用了list，在测试过程中python报memory error才恍然发现了这么个大bug。而python提供了字典这么好的一个数据结构，使用字典可以做到用多少给多少，大大大的减少了内存浪费。
        for i in ng:
            temp = 0
            only = False
            for j in i:
                if count[j] == 1:
                    only = True
                temp += 1<<(j-1)
            if not only:
                mode.append(temp)
                state[temp] = 1
            else:
                mask |= temp
                ret += 1

        if mask == (1<<upper)-(1<<(lower-1)):
            return ret

        best = 50 # 不会比50个组的组合更差的情况了
        for m in mode:
            for i in state.keys():
                # 新的状态可由老状态和m组成，但未必比历史记录更优
                state[i|m] = min(state.get(i|m,50), state.get(i,50)+1)
                if mask|i|m  == (1<<upper)-(1<<(lower-1)):
                   best = min(best, ret+state[i|m])

        return best