塞进裤子ヾ(≧O≦)〃嗷~

0%

剑指offer-66构建乘积数组-python

《剑指offer》python实现系列,全目录

注意两个list a,b
b=a 改变b的值也会改变a的值

找规律
mark
先算B[i]的一部分:
对角线左边Bleft[i] = Bleft[i-1]A[i-1]
再算整体的:
B[i] = Bleft[i]*A[i+1]
..*A[n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
def multiply( A):
B = [1]*len(A) #因为对角线元素为1,所以初始化为1
n = len(A)
#计算对角线左边的乘积
for i in range(1,n):
B[i] = B[i-1]*A[i-1]

#计算对角线右边的乘积,倒着算A的连乘方便些
temp = 1# 保存对角线右边A[i+1]*..*A[n-1]的乘积
for i in range(n-2,-1,-1):
temp *= A[i+1]
B[i] = B[i]*temp
return B
第一个版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def cheng(low,high,A):
if high<low:
return 1
if low>high:
return 1
temp=1
for i in range(low, high+1):
temp *= A[i]
return temp


def multiply( A):
B = [0]*len(A)
n = len(A)
for i in range(n):
B[i]= cheng(0, i-1,A)*cheng(i+1, n-1,A)
return B
if help:小手一抖点个广告 or 大手一挥资助一下