结果与总结
这里是式酱～(∠・ω< )⌒☆
手速场掉大分，还是太久没写题了，都是粗心wa的，题目总体还是比较简单的，T4是一个比较智慧的题，需要考虑其划分的方式，质量还是很不错的！
100342. 最小元素和最大元素的最小平均值
模拟即可，排序后每次都数组顶部和底部取出最大最小的数。
时间复杂度
class Solution:
def minimumAverage(self, nums: List[int]) -> float:
nums.sort()
ans = 10**18
for i in range(len(nums) // 2):
ans = min(ans,(nums[i] + nums[-1-i])/2)
return ans100334. 包含所有 1 的最小矩形面积 I
只需要选出一个边界包含所有的 即可，其上下左右边界分别对应所有 点横坐标纵坐标的最大最小值，计算面积即可。
时间复杂度
class Solution:
def minimumArea(self, grid: List[List[int]]) -> int:
up,down,left,right = 10**18,-10**18,10**18,-10**18
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
up = min(up,i)
down = max(down,i)
left = min(left,j)
right = max(right,j)
return (down - up + 1) * (right - left + 1)100337. 最大化子数组的总成本
划分型 ，子数组 的成本定义为：，枚举每个元素是 或者 权重开始的最大代价，在某处划分时可以交错变换权重也可以另起一个新的划分，首元素必须落在第一个子数组的头部，因此必须以 开始。
时间复杂度
class Solution:
def maximumTotalCost(self, nums: List[int]) -> int:
@cache
def dfs(i,flag):
if i == len(nums):
return 0
ans = flag * nums[i] + max(dfs(i + 1,-1 if flag == 1 else 1),dfs(i + 1,1))
return ans
return dfs(0,1)100332. 包含所有 1 的最小矩形面积 II
对于切分三个不重合的矩形，其实只有下面六种切法，可以将每个部分交给每片区域的矩形，复用 的代码就可以计算结果了。
时间复杂度 ，通过预处理四个角的前缀和可以变成 ，不过有点麻烦，就不写了。类似的题 F - Non-overlapping Squares
class Solution:
def minimumSum(self, grid: List[List[int]]) -> int:
def cal(x1,x2,y1,y2):
up, down, left, right = 10 ** 18, -10 ** 18, 10 ** 18, -10 ** 18
for i in range(x1,x2 + 1):
for j in range(y1,y2 + 1):
if grid[i][j]:
up = min(up, i)
down = max(down, i)
left = min(left, j)
right = max(right, j)
return (down - up + 1) * (right - left + 1)
m = len(grid)
n = len(grid[0])
ans = 10**18
# 三横
for i in range(m - 2):
for j in range(i + 1,m - 1):
ans = min(ans,cal(0,i,0,n - 1) + cal(i + 1,j,0,n - 1) + cal(j + 1,m - 1,0,n - 1))
# 三竖
for i in range(n - 2):
for j in range(i + 1,n - 1):
ans = min(ans,cal(0,m - 1,0,i) + cal(0,m - 1,i + 1,j) + cal(0,m - 1,j + 1,n - 1))
# 先一横 然后再切一竖
for i in range(m - 1):
for j in range(n - 1):
ans = min(ans,cal(0,i,0,j) + cal(0,i,j + 1,n - 1) + cal(i + 1,m - 1,0,n - 1))
for j in range(n - 1):
ans = min(ans, cal(0, i, 0, n - 1) + cal(i + 1, m - 1, j + 1, n - 1) + cal(
i + 1, m - 1, 0, j))
# 先一竖 再切一横
for j in range(n - 1):
for i in range(m - 1):
ans = min(ans,cal(0,i,0,j) + cal(i + 1,m - 1,0,j) + cal(0,m - 1,j + 1,n - 1))
for i in range(m - 1):
ans = min(ans,cal(0,m - 1,0,j) + cal(0,i,j + 1,n - 1) + cal(i + 1,m - 1,j + 1,n - 1))
return ans写在最后
评论 (11)
