topcoder practice: ZooExchangeProgram

为了兴趣，也为了保持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

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

topcoder practice: ZooExchangeProgram

题面：

代码及详解：

Related

Leave a Reply Cancel reply

题面：

代码及详解：

Share this:

Related

Leave a Reply Cancel reply