剣指offerシリーズ-面接問題-面接問題66.積配列の構築(python)

文書ディレクトリ

1. タイトル

2. 解題構想

2.1暴力法

2.2 2回の遍歴

3. コード実装

3.0暴力法

3.1 2回の遍歴

4. まとめ

5. 参考文献

1.テーマ
配列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].除算は使用できません.
2.問題の解き方
2.1暴力法
2.2 2回の遍歴
詳しくは試験問題66.積配列の構築(表パーティション化,明確な図解)暴力法が失敗したのは,多くの計算を繰り返したため,以前に計算した値を必ず利用し,どのように利用したかが鍵となる.
3.コード実装
3.0暴力法
つらいのは時間の制限を超えたことだ.

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
    
        B = []

        for i in range(len(a)):
            num = 1
            for j in range(len(a)):
                if i != j:
                    num *= a[j]
            B.append(num)
        return B

3.1 2回の遍歴

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        """
        """
        b, temp = [1 for i in range(len(a))], 1

        for i in range(1, len(a)):
            b[i] = b[i-1] * a[i-1]

        for i in range(len(a)-1, -1, -1):
            b[i] *= temp
            temp *= a[i]

        return b

4.まとめ
紙に絵をたくさん描くべきで、法則が見つかるかもしれません...
5.参考文献
[1]剣指offer叢書[2]剣指Offer-有名企業の面接官が典型的なプログラミング問題を詳しく話す