Leetcode 【238、1011】

题目描述：【Array】238. Product of Array Except Self

解题思路：

题目要求不能使用除法操作，并且时间复杂度要求为 O(n)。

方法1（空间复杂度为 O(n)）：

如 nums = [1,2,3,4]，观察到对于第 i 个位置的数字，其结果为左边 i-1 个数的乘积与右边 N-i 个数的乘积之积（如第 3 个位置的数字 3，其结果为左边的两个数 1、2 与右边的 1 个数 4 相乘）。因此，我们可以使用两个和 nums 同样大小的数组 left 和 right，left 是从左到右进行累乘（不包括当前数字在内）；right 是从右到左累乘（不包括当前数字）。最后，ans[i] = left[i] * right[i]。

举例：对于 nums = [1,2,3,4]，我们可以得到 left = [1,1,2,6]，right = [24,12,4,1]，最终的答案就是 [24,12,8,6]。

Python3 实现：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        left = [1] * len(nums)
        right = [1] * len(nums)
        for i in range(1, len(nums)):   # 从左到右累乘，保存第 i 个数字的前 i-1 个数的乘积
            left[i] = left[i-1] * nums[i-1]
        for i in range(len(nums)-2, -1, -1):  # 从右到左累乘，保存第 i 个数字的后 N-i 个数的乘积
            right[i] = right[i+1] * nums[i+1]
        for i in range(len(nums)):  # 对应位置相乘即为答案
            left[i] *= right[i]
        return left

方法2（空间复杂度为 O(1)）：

除了最后的结果，可不可以将空间复杂度降为 O(1) 呢？观察到方法 1，当从左到右的 left 数组求出来后，实际上我们可以直接对 left 数组进行从右到左操作，然后用一个变量在从右到左遍历的过程中累乘右边 N-i 个数的乘积，从而就可以省略创建 right 数组，达到空间复杂度为 O(1) 的效果。

Python3 实现：

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1] * len(nums)
        for i in range(1, len(nums)):  # 从左到右累乘，保存第 i 个数字的前 i-1 个数的乘积
            ans[i] = ans[i-1] * nums[i-1] 
        right = 1  # 用一个变量累乘右边 N-i 个数字的乘积
        for i in range(len(nums)-1, -1, -1):
            ans[i] *= right
            right *= nums[i]  # 累乘
        return ans

---

问题描述：【Array，Binary Search】1011. Capacity To Ship Packages Within D Days

解题思路：

分析题目之后，可以想出一种朴素的解法。那就是去遍历最小容量的所有值，直到找到满足条件的最小容量。

注意：最小容量是有上下界的，即下界为 max(weights) （因为即使是最小容量，也肯定要能够装下最大的那个货物），上界为 sum(weights)（因为如果天数限制为 1 天，最小容量就是所有货物之和）。

当然最简单的就是从最小容量的下界开始，一个个去找，但这样做时间复杂度为 O(n^2)，超时了。因为我们知道了最小容量的上下界，所以我们容易想到这是一道考察二分查找的题目。时间复杂度就可以降为 O(n*logn)。

但是还要注意，这道题和二分查找还有所区别。这道题中，我们是要找到 D 天之内的最小容量，而不是刚好等于 D 天。也就是说，当我们找到一个容量在 D 天之内可以装完还不够，还要继续再找，直到找到一个容量，它大于了 D 天，并且不满足 low <= high，循环结束。这个时候，下界 low 才是最终的最小容量。

Python3 实现：

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low = max(weights)
        high = sum(weights)
        while low <= high:  # 二分查找的循环条件
            capacity = (low + high) // 2  # capacity相当于二分查找中的middle
            tem = 0
            need = 1
            for weight in weights:
                if tem + weight > capacity:
                    need += 1
                    tem = 0
                tem += weight
            if need <= D:  # 根据题意，<=的情况要合并到一起，并且满足这个条件的capacity不一定是最小容量，所以这里不能直接return
                high = capacity - 1
            elif need > D:
                low = capacity + 1   
        return low  # 下界low才是满足条件的最小容量