题目描述
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。
思路
这里禁止使用除法。观察B数组中元素的规律,第i个元素的值为第1i-1个袁术和i+1n的乘积。那么很自然的考虑把结果分成两部分来计算。一部分是i前面的部分,一部分是i后面的部分。
然后注意一下开头和结尾的处理就可以。
代码
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
# write code here
B = self.helper(A)
return B
def helper(self,nums):
if len(nums) == 0:
return []
if len(nums) == 1:
return nums[0]
forward = []
backward = [1] * (len(nums) + 1)
forward.append(nums[0])
backward[len(nums) - 1] = nums[len(nums) - 1]
B = []
val_0 = 1
for i in range(len(nums)):
val_0 = val_0 * nums[i]
B.append(val_0)
for i in range(1, len(nums)):
val_1 = forward[i - 1] * nums[i]
forward.append(val_1)
for i in range(len(nums) - 2, -1, -1):
val_2 = backward[i + 1] * nums[i]
backward[i] = val_2
for i in range(1, len(nums)):
val_3 = forward[i - 1] * backward[i + 1]
B.append(val_3)
return B
网友评论