说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。
题目来源
- 分类：数组
- 构建乘积数组
题目描述
给定一个数组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]。不能使用除法。
解题思路（参考剑指offer 第二版）
B[0] = A[1] * A[2] * A[3] * A[4] ....A[n-1] ;（没有A[0]）
B[1 ]= A[0] * A[2] * A[3] * A[4] ....A[n-1] ;（没有A[1]）
B[2] = A[0] * A[1] * A[3] * A[4] ....A[n-1] ;（没有A[2]）
相当于一个矩阵，被省去的那个数字设为1，这样的话，先把上三角的数一行一行撑起来，接着在和下三角的数相乘，节省空间。
把数组B看成一个矩阵创建
高效的方法，把B[i] = A[0] * A[1] ....A[i-1] * A[i + 1] * ...A[n - 1] ;看成A[0] * A[1] ....A[i-1] 和 A[i + 1] * ...A[n - 1]两部分的乘积。因此数组B可以用一个矩阵来创建，如上图所示。在图中B[i]为矩阵中第i行所有元素的乘积。
不妨设定C[i]=A[0]A[1]...A[i-1]，D[i]=A[i+1]...A[n-2]A[n-1]。C[i]可以用自上而下的顺序计算出来，即C[i]=C[i-1]A[i-1]。类似的，D[i]可以用自下而上的顺序计算出来，即D[i]=D[i+1]A[i+1]。
下面代码中通过两个for循环分别来解决C[i]与D[i]。
对于第一个for循环
上三角型
第一步：b[0] = 1;
第二步：b[1] = b[0] * a[0] = a[0]
第三步：b[2] = b[1] * a[1] = a[0] * a[1];
第四步：b[3] = b[2] * a[2] = a[0] * a[1] * a[2];
第五步：b[4] = b[3] * a[3] = a[0] * a[1] * a[2] * a[3];
下三角型，自下向上
第一步
temp *= a[4] = a[4];
b[3] = b[3] * temp = a[0] * a[1] * a[2] * a[4];
第二步
temp *= a[3] = a[4] * a[3];
b[2] = b[2] * temp = a[0] * a[1] * a[4] * a[3];
第三步
temp *= a[2] = a[4] * a[3] * a[2];
b[1] = b[1] * temp = a[0] * a[4] * a[3] * a[2];
第四步
temp *= a[1] = a[4] * a[3] * a[2] * a[1];
b[0] = b[0] * temp = a[4] * a[3] * a[2] * a[1];
编程实现
PHP
<?php
运行时间：60ms
占用内存：2424k
function multiply($numbers)
{
if (empty($numbers) || count($numbers) <= 0) {
return [];
}
$length = count($numbers);
$mulNums = array();
$mulNums[0] = 1;
for ($i = 1; $i < $length; $i++) {
$mulNums[$i] = $mulNums[$i - 1] * $numbers[$i];
}
$temp = 1;
for ($i = $length - 2; $i >= 0; $i--) {
$temp *= $numbers[$i + 1];
$mulNums[$i] *= $temp
}
return $mulNums;
}
?>
Python
运行时间：28ms
占用内存：5732k
'''
# -*- coding:utf-8 -*-
class Solution:
def multiply(self, A):
if not A or len(A)<0:
return 0
length = len(A)
B = [1] * length
# 上三角
for i in range(1, length):
B[i] = B[i - 1] * A[i - 1]
temp = 1
for i in range(length - 2, -1, -1):
temp = temp * A[i + 1]
B[i] *= temp
return B
S = Solution()
print S.multiply([1,2,3,4,5])
网友评论