python编程实战（三）

题目1：

给你一个整数数组nums，返回 数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积 。

题目数据保证数组nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。

请不要使用除法，且在O(n)时间复杂度内完成此题。

关键数据结构：

列表（一维数组）

核心思路：

除nums[i]元素之外的元素乘积可以分为两部分，nums[i]之前的元素的乘积和nums[i]之后的元素的乘积；将数组num正向遍历一遍之后，可以再反向遍历一遍，然后用一个数组先存储前元素乘积，再存储后元素乘积。

代码：

class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n
# 从左到右计算前缀积
prefix = 1
for i in range(n):
ans[i] = prefix
prefix *= nums[i]
# 从右到左计算后缀积并乘以结果
suffix = 1
for i in range(n - 1, -1, -1):
ans[i] *= suffix
suffix *= nums[i]
return ans

题目2：

给你一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。

关键数据结构：
用列表实现哈希表效果

关键思路：
原地哈希算法，我们希望在位置i上的值是i+1，如在位置0上的位置是1，这样可以起到高效的排序效果；如果位置i上的数！=i+1，那么此时的i+1就是缺失的最小正整数。

代码：
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
target_idx = nums[i] - 1
nums[i], nums[target_idx] = nums[target_idx], nums[i]

for i in range(n):
if nums[i] != i + 1:
return i + 1

return n + 1

题目3：

给定一个mxn的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法（原地算法是指在算法执行过程中，只使用常数量级的额外空间，主要通过对输入数据的原有存储空间进行修改来完成计算，而不需要额外的数据结构来存储中间结果或输出结果)。

关键数据结构：

二维数组

思路：

使用双循环遍历矩阵每个元素，如果某个元素为0，将其对应的行、列通过布尔值打上标记；再次双循环遍历矩阵，如果某一行或者某一列标记为零，将整行或整列元素置0

代码（这里偷懒没用原地算法）：

class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row = m * [False]
col = n * [False]

for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = True
col[j] = True

for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0