做美食原创视频网站wordpress 调用最新文章

当前位置： 首页 > news >正文

做美食原创视频网站,wordpress 调用最新文章,那家建网站宝盒好用,Wordpress分享到微信图标博客主页#xff1a;誓则盟约系列专栏#xff1a;IT竞赛 专栏关注博主#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出#xff0c;及时修改感谢大家点赞#x1f44d;收藏⭐评论✍ 2742.给墙壁刷油漆【困难】 题目#xff1a; 给你两个长度为 n 下标从 0…博客主页誓则盟约系列专栏IT竞赛 专栏关注博主后期持续更新系列文章如果有错误感谢请大家批评指出及时修改感谢大家点赞收藏⭐评论✍  2742.给墙壁刷油漆【困难】 题目 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠 一位需要 付费 的油漆匠刷第 i 堵墙需要花费 time[i] 单位的时间开销为 cost[i] 单位的钱。一位 免费 的油漆匠刷 任意 一堵墙的时间为 1 单位开销为 0 。但是必须在付费油漆匠 工作 时免费油漆匠才会工作。 请你返回刷完 n 堵墙最少开销为多少。 示例 1 输入cost [1,2,3,2], time [1,2,3,2] 输出3 解释下标为 0 和 1 的墙由付费油漆匠来刷需要 3 单位时间。同时免费油漆匠刷下标为 2 和 3 的墙需要 2 单位时间开销为 0 。总开销为 1 2 3 。示例 2 输入cost [2,3,4,2], time [1,1,1,1] 输出4 解释下标为 0 和 3 的墙由付费油漆匠来刷需要 2 单位时间。同时免费油漆匠刷下标为 1 和 2 的墙需要 2 单位时间开销为 0 。总开销为 2 2 4 。提示 1 cost.length 500cost.length time.length1 cost[i] 10**61 time[i] 500 分析问题 思路一 首先我们需要理解问题的本质是在给定成本和时间的列表情况下找到满足一定体积需求的最小花费。这个问题通过定义一个 dfs 函数来解决函数中的参数 i 表示当前考虑的物品索引j 表示剩余需要的体积。 接下来分析 dfs 函数的逻辑。当 j 0 时表示剩余需要的体积已经满足要求不需要再选择物品所以返回 0 。当 i 0 且 j 0 时表示没有物品可选但仍有剩余体积需求这是不合法的情况所以返回正无穷大 inf 。对于其他情况有两种选择一是选择当前物品此时需要花费 cost[i] 剩余需要的体积变为 j - time[i] - 1 然后递归调用 dfs(i - 1, j - time[i] - 1) 二是不选择当前物品直接递归调用 dfs(i - 1, j) 。函数返回这两种选择中的最小值。 然后要注意到使用了 cache 装饰器进行记忆化搜索。这是为了避免重复计算相同的子问题提高算法的效率。 最后在 paintWalls 方法中通过获取 cost 列表的长度 n 然后调用 dfs(n - 1, n) 来计算最小的花费。 思路二 首先定义两个匿名函数 min 和 max 分别用于求两个数中的最小值和最大值。 然后获取 cost 列表的长度 n 并初始化一个列表 f 。 f[0] 设为 0  f[1] 到 f[n] 设为正无穷大 inf 。 接下来通过遍历 cost 和 time 列表的对应元素 c 和 t 进行动态规划的计算。 对于每个 c 和 t 从 n 到 1 逆序遍历 f 列表。对于每个 j 更新 f[j] 的值。更新的方式是取当前的 f[j] 和 f[max(j - t - 1, 0)] c 中的最小值。 max(j - t - 1, 0) 表示在考虑当前时间 t 的情况下能够完成的工作量对应的索引。通过这种方式我们在每个位置 j 上都找到了使用前 j 个物品能够达到的最小花费。 最后函数返回 f[n] 即使用所有物品能够达到的最小花费。 代码实现 思路一代码实现 class Solution:def paintWalls(self, cost: List[int], time: List[int]) - int:cache # 记忆化搜索def dfs(i: int, j: int) - int: # j 表示剩余需要的体积if j 0: # 没有约束后面什么也不用选了return 0if i 0: # 此时 j0但没有物品可选不合法return infreturn min(dfs(i - 1, j - time[i] - 1) cost[i], dfs(i - 1, j))n len(cost)return dfs(n - 1, n)思路二代码实现 class Solution:def paintWalls(self, cost: List[int], time: List[int]) - int:# 定义一个匿名函数min用于求两个数的最小值min lambda a, b: b if b a else a# 定义一个匿名函数max用于求两个数的最大值max lambda a, b: b if b a else an len(cost)# 初始化一个列表ff[0]为0f[1]到f[n]为正无穷大f [0] [float(inf)] * n# 遍历cost和time列表的对应元素for c, t in zip(cost, time):# 从n到1逆序遍历f列表for j in range(n, 0, -1):# 更新f[j]的值取当前f[j]和f[max(j - t - 1, 0)] c的最小值f[j] min(f[j], f[max(j - t - 1, 0)] c)# 返回f[n]即完成所有工作的最小花费return f[n] 总结 思路一代码详解 定义了一个内部的 dfs 函数该函数使用了记忆化搜索通过 cache 装饰器实现。dfs 函数接受两个参数i 表示当前考虑的物品索引j 表示剩余需要的体积。在 dfs 函数中如果 j 0 表示剩余需要的体积已经满足要求不需要再选择物品返回 0 。如果 i 0 且 j 0 表示没有物品可选但仍有剩余体积需求这种情况是不合法的返回 inf 表示正无穷大。对于其他情况有两种选择 选择当前物品索引为 i 那么需要花费 cost[i] 并且剩余需要的体积变为 j - time[i] - 1 然后递归调用 dfs(i - 1, j - time[i] - 1) 。不选择当前物品直接递归调用 dfs(i - 1, j) 。最后函数返回这两种选择中的最小值。在 paintWalls 方法中首先获取 cost 列表的长度 n 然后调用 dfs(n - 1, n) 来计算最小的花费。 总的来说这段代码的目的是通过递归的方式在考虑每个物品的选择与否的情况下计算出满足剩余体积需求的最小花费。记忆化搜索的使用可以避免重复计算提高算法的效率。 考点 动态规划两段代码都运用了动态规划的思想来解决问题。通过定义合适的状态如代码中的 f 数组和状态转移方程如更新 f[j] 的值来逐步求解最优解。函数定义与使用代码中定义了匿名函数如 min 和 max 函数来简化比较和操作。列表操作涉及到列表的初始化、遍历正序和逆序以及元素的更新。逻辑推理与问题分析需要理解问题的要求找出合适的解法并将其转化为代码实现。 收获 深入理解动态规划的概念和应用通过实际解决这个问题更加熟悉如何根据问题的特点定义状态和状态转移方程从而有效地运用动态规划来求解最优解。提高函数使用和定义的能力学会了使用匿名函数来简洁地表达一些常见的操作增强了代码的可读性和简洁性。增强对列表数据结构的操作能力包括列表的初始化、遍历和元素的修改能够更加熟练地运用列表来解决实际问题。培养逻辑思维和问题分析能力在理解问题的基础上能够将其转化为有效的算法和代码实现提高了解决复杂问题的能力。学会从不同的角度思考问题两段代码虽然都解决了同一个问题但实现方式略有不同通过对比学习可以拓宽解题思路提高解决问题的灵活性。 “祈愿万家灯火熨烫过脉络刀山与火海多深刻都陪你渡过。”——《不痛》