題目描述
給定一個陣列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[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）
對于A長度為1的情況，B無意義，故而無法構建，因此該情況不會存在，
思路
- 讀題，理解陣列B的規律，發現B[ i ]即i的位置A[i]不存在，也可以理解為1，
- 不能使用除法，即不能使用這個方法B[i] = A[1] * A[2] * … * A[n-1] / A[1]
畫圖可發現，類似矩陣的上下三角
不規則圖形可以拆分為規則圖形計算面積，本題也可以試試
代碼
public class Solution {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
B[0] = 1;
//下三角
for (int i = 1; i < A.length; i++) {
B[i] = B[i-1] * A[i-1];//利用相鄰B陣列元素的相似性，避免重復計算，同時避免了再次使用for回圈
}
int temp = 1;
//上三角
for (int i = A.length-2; i >= 0 ; i--) {
temp = temp * A[i+1];
B[i] = B[i] * temp;
}
return B;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/2813.html
標籤：其他