Leetcode 【238、1011】
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)。
但是还要注意，这道题和二分查找还有所区别。明天继续分析，先贴代码...
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
tem = 0
need = 1
for weight in weights:
if tem + weight > capacity:
need += 1
tem = 0
tem += weight
if need <= D:
high = capacity - 1
elif need > D:
low = capacity + 1
return low