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

zltzlt

今天的题目：

给定一个数组，返回数组中的所有子数组之和。

说明：如果数组为 [2, 4, 1]，则该数组所有的子集是 [[2], [4], [1], [2, 4], [4, 1], [2, 4, 1]]。

示例 1：

输入：[1, 2, 3]
输出：20
解释：(1) + (2) + (3) + (2 + 3) + (1 + 2) + (1 + 2 + 3) = 20

示例 2：

输入：[1, 2]
输出：6
解释：(1) + (2) + (1 + 2) = 6

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

newbison

2020-1-22 18:20:15

上一题不会，这一题我用递归来解决吧。实在看不懂你们的高深的方法。

1. def func312(array):
   
2.     l = len(array)
   
3.     res = 0
   
4.     if l == 1:
   
5.         res = array[0]
   
6.     elif l == 2:
   
7.         res = array[0] + array[1] + (array[0] + array[1])
   
8.     else:
   
9.         res = func312(array[:(l-1)])
   
10.         for i in range(0, l):
    
11.             res += add(array[i:])
    
12.     #递归法解决该问题，每添加一个元素，多出来的数组统统加一遍
    
13.     return res
    
14. 
    
15. def add(array):
    
16.     res = 0
    
17.     for each in array:
    
18.         res += each
    
19.     return res
    
20. 
    
21. 
    
22. print('array [1, 2, 3]的答案是: ', func312([1, 2, 3]))
    
23. print('array [1, 2]的答案是: ', func312([1, 2]))
    
24. print('array [5, 2, 8, 4, 2]的答案是: ', func312([5, 2, 8, 4, 2]))
    

复制代码

跳转到最佳答案楼层

776667

1. def fun312(x):
   
2.     sub_array = []
   
3.     for i in range(len(x)):
   
4.         for j in range(i+1,len(x)+1):
   
5.             sub_array.append(x[i:j])
   
6.     return sum([sum(i) for i in sub_array])

复制代码

wanting-for

1. def add(num:int,length,list1):
   
2.     list2 = []
   
3.     for i in range(length):
   
4.         if i+num<=length:
   
5.             list2.append(sum(list1[i:i+num]))
   
6.     return list2
   
7. def solve_312(list1:list):
   
8.     lenght = len(list1)
   
9.     sum_list = []
   
10.     for i in range(1,lenght):
    
11.         sum_list.extend(add(i,lenght,list1))
    
12.     return sum(sum_list)+sum(list1)
    
13. print(solve_312([5,2,8,4,2]))

复制代码

一把梭子直接干，暴力解决，完事收工！
请楼主帮忙测试一下，非常感谢！！！
昨天忙，没带电脑，今天补上！

fan1993423

Croper 发表于 2020-1-22 14:51
写成一行的版本

这应该是这道题最好的解法了

_2_

Croper 发表于 2020-1-22 14:51
写成一行的版本

厉害厉害

newbison

改善了一下，不用递归了。

1. def func312(array):
   
2.     l, res = len(array), 0
   
3.     for i in range(0, l):
   
4.         for j in range(i+1, l+1):
   
5.             for each in array[i:j]:
   
6.                 res += each
   
7.     return res
   
8. print('array [1, 2, 3]的答案是: ', func312([1, 2, 3]))
   
9. print('array [1, 2]的答案是: ', func312([1, 2]))
   
10. print('array [5, 2, 8, 4, 2]的答案是: ', func312([5, 2, 8, 4, 2]))

复制代码

阴阳神万物主

zltzlt 发表于 2020-1-22 14:40
解答错误

输入：[5, 2, 8, 4, 2]

汗~是我疏忽了……

1. def solve(lst):
   
2.     res = times = 0
   
3.     while len(lst)>1:
   
4.         times += len(lst)
   
5.         res += (lst[0]+lst[-1]) * times
   
6.         #print('调试',lst[0],lst[-1],times)
   
7.         lst = lst[1:-1]
   
8.     else:
   
9.         if lst:
   
10.             res += lst[0]*(times+1)
    
11.     return res
    
12. if __name__ == '__main__':
    
13.     print('示例1 输出：',solve([1,2,3]))
    
14.     print('示例2 输出：',solve([1,2]))
    

复制代码

zltzlt

TJBEST 发表于 2020-1-22 20:40
楼主试试这个，我感觉不算慢

1217 ms

TJBEST

楼主试试这个，我感觉不算慢

1. def fun312(arr):
   
2.     if arr == []:
   
3.         return 0
   
4.     res = 0
   
5.     N = len(arr)
   
6.     for i in range(0,N//2):
   
7.         alpha = (i + 1)*(N - i)
   
8.         res = res + (arr[i] + arr[N - 1 - i])* alpha
   
9.     if N % 2:
   
10.         alpha = (N//2 + 1)*(N - N//2)
    
11.         res = res + arr[N//2]*alpha
    
12.     return res

复制代码

zltzlt

TJBEST 发表于 2020-1-22 20:28
楼主先不要封题，我想到一个方法，可能比较快，一会受累测一下啊

收到

TJBEST

楼主先不要封题，我想到一个方法，可能比较快，一会受累测一下啊

fan1993423

1. def fun312(lst):
   
2.     t=[]
   
3.     for i in range(1,len(lst)+1):
   
4.         for j in range(len(lst)-i+1):
   
5.             t.extend(lst[j:j+i])
   
6.     return sum(t)

复制代码

可能效率低哈

newbison

上一题不会，这一题我用递归来解决吧。实在看不懂你们的高深的方法。

1. def func312(array):
   
2.     l = len(array)
   
3.     res = 0
   
4.     if l == 1:
   
5.         res = array[0]
   
6.     elif l == 2:
   
7.         res = array[0] + array[1] + (array[0] + array[1])
   
8.     else:
   
9.         res = func312(array[:(l-1)])
   
10.         for i in range(0, l):
    
11.             res += add(array[i:])
    
12.     #递归法解决该问题，每添加一个元素，多出来的数组统统加一遍
    
13.     return res
    
14. 
    
15. def add(array):
    
16.     res = 0
    
17.     for each in array:
    
18.         res += each
    
19.     return res
    
20. 
    
21. 
    
22. print('array [1, 2, 3]的答案是: ', func312([1, 2, 3]))
    
23. print('array [1, 2]的答案是: ', func312([1, 2]))
    
24. print('array [5, 2, 8, 4, 2]的答案是: ', func312([5, 2, 8, 4, 2]))
    

复制代码

TJBEST

我的代码总是很长，需要改进

1. def fun312(arr):
   
2.     def inner(n):
   
3.         down_gate = n - 1
   
4.         up_gate = N - n
   
5.         res = 0
   
6.         if down_gate <= up_gate:
   
7.             for i in range(0,down_gate):
   
8.                 res = res + (i + 1)*arr[i]
   
9.             for i in range(down_gate,up_gate + 1):
   
10.                 res = res + n * arr[i]
    
11.             for i in range(up_gate + 1,N):
    
12.                 res = res + (N - i) * arr[i]
    
13.             return res
    
14.         else:
    
15.             for i in range(0,up_gate):
    
16.                 res = res + (i + 1)*arr[i]
    
17.             for i in range(up_gate,down_gate + 1):
    
18.                 res = res + (N - n + 1) * arr[i]
    
19.             for i in range(down_gate + 1,N):
    
20.                 res = res + (N - i) * arr[i]
    
21.             return res
    
22.             
    
23.                
    
24.     if arr == []:
    
25.         return 0
    
26.    
    
27.     res = 0
    
28.     N = len(arr)
    
29.     for i in range(1,N + 1):
    
30.         res = res + inner(i)
    
31.     return res

复制代码

塔利班

kinkon 发表于 2020-1-22 16:07
佩服...

没有，看了大神的感觉走了点弯路，，

kinkon

塔利班 发表于 2020-1-22 15:30

佩服...

塔利班

1. def f312(x):
   
2.     s=sum(x)
   
3.     n=len(x)
   
4.     r=n*(n+1)//2*s
   
5.     coef=[(n-i)*(n-i-1)//2 for i in range(n)]
   
6.     for e in zip(x,coef,coef[::-1]):
   
7.         a,b,c=e
   
8.         r-=a*(b+c)
   
9.     return r

复制代码

kinkon

Croper 发表于 2020-1-22 14:51
写成一行的版本

只是佩服Croper老大的头脑

Croper

看起来测试用例有点长。。。

Croper

写成一行的版本

1. def func312(l:list):
   
2.         return sum((i+1)*(len(l)-i)*l[i] for i in range(len(l)))

复制代码