[已解决]Python：每日一题 358

阴阳神万物主

难度评级：中等
要素分析：算法 效率
感受：问题可以转化为对所有数字的符号做规划的二进制问题。
在时间复杂度上面，2^n  明显优于暴力破解的 n! ，而循环优于递归。
我现在在考虑要不要把贮存二进制数据的表作为一个新类去定义，直觉告诉我定义新类的话效率会更高，但是懒癌让我想到：如果已经足够了的话，就不用定义了撒。等会儿再更新作为一个新类的代码。

1. def solve(nums:'list of int>=0',s:int)->int:
   
2.     res = 0
   
3.     def bi(n):
   
4.         yield n%2
   
5.         while n := n // 2:
   
6.             yield n%2
   
7.     r = len(nums)
   
8.     for i in range(2**len(nums)):
   
9.         l = list(bi(i))
   
10.         su = 0
    
11.         for j in range(len(l)):su += nums[j] if l[j] else -nums[j]
    
12.         if su < s:continue
    
13.         while (j := j+1)<r:
    
14.             su -= nums[j]
    
15.         if su == s:
    
16.             res += 1
    
17.     return res
    
18. if __name__ == '__main__':
    
19.     print('示例 输出：',solve([1]*5,3))
    

复制代码

阴阳神万物主

这个的时间复杂度（算上定义的二进制数据自增函数）应当是 (2**n)*n

1. def solve_2(nums:'list of int>=0',s:int)->int:
   
2.     res = 0
   
3.     r = len(nums)
   
4.     class B(list):
   
5.         def __init__(self):
   
6.             list.__init__(self,(0,))
   
7.         def add(self):
   
8.             i = -1
   
9.             while 1:
   
10.                 i += 1
    
11.                 try:
    
12.                     if self[i]:self[i] = 0
    
13.                     else:self[i] += 1;return
    
14.                 except IndexError:
    
15.                     self.append(1)
    
16.                     return
    
17.     def getl():
    
18.         l = B()
    
19.         while len(l)<=r:
    
20.             yield l
    
21.             l.add()
    
22.     for l in getl():
    
23.         su = 0
    
24.         for i in range(len(l)):su += nums[i] if l[i] else -nums[i]
    
25.         if su < s:continue
    
26.         while (i := i+1)<r:
    
27.             su -= nums[i]
    
28.         if su == s:
    
29.             print(l)
    
30.             res += 1
    
31.     return res
    
32. if __name__ == '__main__':
    
33.     print('示例 输出：',solve_2([1]*5,3))

复制代码