一道穷举法算法题

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

题目是在topcoder看到的，但是不小心关了，不记得是题号了。

题目如下:

给定一组数，求哪这组数字能够组成的最长连续子序列，但其中比较特殊的是0可以代替任何数

注意: 其中的数字可以重复
限制条件:
数字的返回是从 0 ~ 1000000 包含0, 1000000
这组数的数量不超过 50

1) 0, 6, 5, 10, 3, 0, 11
返回 5
解释:
如果把两个0，一个当做4, 一个当做7
那么可以得到最长连续子序列是 3, 4, 5, 6, 7
如果把两个0, 一个当做2, 一个当做4
那么可以得到最长连续子序列是 2, 3, 4, 5, 6

2) 100,100,100,101,100,99,97,103
返回 3
解释:
最长连续子序列是 99, 100, 101

3) 0, 0, 0, 1 , 2, 6, 8, 1000
返回 6

解释:
最长连续子序列是 1, 2, 3, 4, 5, 6

解法:
思路: 先将这组数排序，然后在不连续的数字中插入0, 然后从这组数的头部开始遍历尝试找到最长的连续子序列

# -*- coding:utf-8 -*-  
class CardStraights(object):  
    def longestStraight(self, tp):  
        res = 0  
        count = 0  
        ll = sorted(tp)  
        for i in range(len(ll)):  
            if ll[i] == 0:  
                count =  count + 1  
        #print count  

        new_list = []  
        last = None  
        for i in range(len(ll)):  
            if ll[i]!=0:  
                if ll[i]!= last:  
                    new_list.append(ll[i])  
                    if i < len(ll) -1 and ll[i + 1] != ll[i] + 1:  
            # 插入0的个数  
                        zero_count = min(50, ll[i + 1] - ll[i] - 1)  
                        for j in range(zero_count):  
                            new_list.append(0)  
            else:  
                new_list.append(ll[i])  

            last = ll[i]      

        for i in range(count):  
            new_list.append(0)    

        print new_list  
        ll = new_list  
        length = len(ll)  
        for i in range(length):  
            curr = 0  
            curr_zero = 0  
            for j in range(i, length):  
                curr = curr + 1  
                if ll[j] == 0:  
                    curr_zero = curr_zero + 1  

                if curr_zero > count:  
                    curr = curr -1   
                    break  
            if curr > res:  
                res = curr  

        return res    

def min(a,b):  
    if a<b:  
        return a  
    else:  
        return b  

c = CardStraights()  
print c.longestStraight((0,6,5,10,3,0,11))  
print c.longestStraight((100,100,100,101,100,99,97,103))  
print c.longestStraight((0,0,0,1,2,6,8,1000,1005,1010))