Leetcode 238

この問題は、配列内の各要素が自身以外の要素の積であり、除算操作は使用できません.O(n)の時間的複雑さが要求されるが,一つの配列にとって,O(n)を用いた時間的複雑さは,最大最小値の平均和,各ビットの前の和の最大最小値と平均値を得ることができるものを整理することができる.これらのO(n)を用いてこれらの最も基本的な情報を得ることができ,問題全体の解を構築する.最初は再帰的な考え方で解きましたが、複雑さが増すことに気づきました.問題全体を分割し、その要素を除くすべての要素の積を要求する以上、解はその要素の左の要素の積にその要素の右の要素の積を乗じたものに等しい.さらに,各ビット上の左右の両側要素の積について,O(n)の時間的複雑さによって得ることができる.この問題の解決策は上記のようになります.
進級:定数の空間複雑度を採用する必要があります.構想は結果を返す配列を利用することです.これはまだ実現していません.次回復習するときにします.構想は上記と同じです.コードは次のとおりです.

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        left = []
        right = []
        result = []
        left_value = 1
        right_value = 1
        for i in range(len(nums)):
            left.append(left_value*nums[i])
            left_value = left_value * nums[i]
        for i in range(len(nums)-1, -1, -1):
            right.append(right_value*nums[i])
            right_value = right_value * nums[i]
        for i in range(len(nums)):
            if i == 0:
                result.append(right[len(nums)-i-2])
            elif i == len(nums)-1:
                result.append(left[i-1])
            else:
                result.append(left[i-1]*right[len(nums)-i-2])
        return result