python3京东神奇数

缺乏、安全感 2022-05-14 10:25 119阅读 0赞

题目如下

![70][]

看到了一个运用01背包思路来解决的方案，代码很简洁，链接在这里

[https://blog.csdn.net/bing\_lee/article/details/77899602][https_blog.csdn.net_bing_lee_article_details_77899602]

**说说我的思路**

1 主要目的，找出该数中各个位上的数组成的集合M中是否存在某个组合K使得sum(K)== sum(M)/2

2 当M中的最大值max(M) > sum(M)/2时，则该数不可能为神奇数，如1119

3 从M的第一个元素开始，递归寻找目标组合K，对于不可能的组合及时剪枝，避免冗余的递归计算

4 每次递归浅复制M的子集M'，并去除当前选中的元素

5 找到sum(K)== sum(M)/2的组合K则返回True

6 当M'中元素个数为0，时返回False

import time
    def run(a,b):
        sum = 0
        for i in range(a,b):
            if check(i):
                sum += 1
        return  sum
    
    
    def num2array(n):
        n_str = str(n)
        length = len(n_str)
        arr = []
        for i in range(length):
            arr.append(int(n_str[i]))
        arr.sort()
        return arr
    
    
    def check(n):
        n_arr = num2array(n)
        a = sum(n_arr)
        # 偶数才有可能成为神奇数
        if a % 2 == 0:
            half = int(a / 2)
            max_item = max(n_arr)
            if max_item > half:
                return False
            else:
                if max_item == half:
                    return True
                else:
                    return  handler(n_arr,0,half)
    
    
    
    
    def handler(arr,sum,half):
        length = len(arr)
        if length == 0:
            return False
        for k in arr:
            tmp_sum = sum + k
            if tmp_sum == half:
                return True
            else:
                if tmp_sum > half:
                    continue
                else:
                    arr1 = arr[:]
                    arr1.remove(k)
                    if handler(arr1,tmp_sum,half):
                        return True
    
    a = 1
    b = 65535
    start = time.time()
    sum = run(a,b)
    end = time.time()
    print('共有：%d 个神奇数,检测耗时%.2f s' % (sum,end-start))

运行结果

共有：19977 个神奇数,检测耗时0.66 s

python不愧为胶水语言，功能强大，速度较慢，要想达到京东要求的1s执行，估计用C/C++会好一点

思考

当输入区间跨度非常大的时候，会有很多重复计算。如11113111和31111111的检测任务是一样的，但是却检测了多次。

我们考虑简历一个结果字典D来存储排好序的数字，如上述两个数的key都是11111113

我们在检查是否为神奇数之前先检查字典D中有没有该数的key，有则直接返回，没有再检查，如果检测结果为神奇数在，则加入字典

代码如下

import time
    
    class MagicNumber:
    
        __dict = {}
    
        def run(self,a,b):
            sum = 0
            for i in range(a,b):
                if self.check(i):
                    sum += 1
                    # print(i)
            return  sum
    
    
        def num2array(self,n):
            n_str = str(n)
            length = len(n_str)
            arr = []
            for i in range(length):
                arr.append(int(n_str[i]))
            arr.sort()
            return arr
    
    
        def check(self,n):
            n_arr = self.num2array(n)
            a = sum(n_arr)
            # 偶数才有肯能成为神奇数
            if a % 2 == 0:
                half = int(a / 2)
                max_item = max(n_arr)
                if max_item > half:
                    return False
                else:
                    key = self.array2string(n_arr)
                    if key in self.__dict:
                        return  True
                    if max_item == half:
                        self.__dict[key] = 1
                        return True
                    else:
                        re = self.handler(n_arr,0,half)
                        if re:
                            self.__dict[key] = 1
                        return  re
    
        def array2string(self,arr):
            string = ''
            for i in arr:
                string += str(i)
            return  string
    
    
        def handler(self,arr,sum,half):
            # 最后还么没有满足
            length = len(arr)
            if length == 0:
                return False
            for k in arr:
                tmp_sum = sum + k
                if tmp_sum == half:
                    return True
                else:
                    if tmp_sum > half:
                        continue
                    else:
                        arr1 = arr[:]
                        arr1.remove(k)
                        if self.handler(arr1,tmp_sum,half):
                            return True
    
        def get_dict(self):
            return self.__dict
    
    a = 1
    b = 1000000
    start = time.time()
    c = MagicNumber()
    sum = c.run(a,b)
    end = time.time()
    print('共有：%d 个神奇数,检测耗时%.2f s' % (sum,end-start))

65535条数据检查时间还提高了

**共有：19977 个神奇数,检测耗时0.73 s**

100w个数检查了20s，不知道哪位大佬能给个C的运行时间

**共有：376413 个神奇数,检测耗时20.13 s**  
这里还有个问题，简历字典也是很消耗时间的，不过个人觉得，随着输入区间的增大，字典的优势会逐渐显露的

PS 本人电脑配置

![70 1][]

[70]: /images/20220514/fa2dfdedbbfe46c69ebbc2c305a70044.png
[https_blog.csdn.net_bing_lee_article_details_77899602]: https://blog.csdn.net/bing_lee/article/details/77899602
[70 1]: /images/20220514/c2bc1deed5df47b2b353b4b8ec488fa0.png