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

LeetCode每日一题——1774. 最接近目标价格的甜点成本

LeetCode每日一题系列

题目:828. 统计子串中的唯一字符
难度:普通


文章目录

  • LeetCode每日一题系列
  • 题目
  • 示例
  • 思路
  • 题解


题目

你打算做甜点,现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则:

必须选择 一种 冰激凌基料。
可以添加 一种或多种 配料,也可以不添加任何配料。
每种类型的配料 最多两份 。
给你以下三个输入:

baseCosts ,一个长度为 n 的整数数组,其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
toppingCosts,一个长度为 m 的整数数组,其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
target ,一个整数,表示你制作甜点的目标价格。
你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案,返回 成本相对较低 的一种。

示例

示例 1:

输入:baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出:10
解释:考虑下面的方案组合(所有下标均从 0 开始):

  • 选择 1 号基料:成本 7
  • 选择 1 份 0 号配料:成本 1 x 3 = 3
  • 选择 0 份 1 号配料:成本 0 x 4 = 0 总成本:7 + 3 + 0 = 10 。

示例 2:

输入:baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出:17
解释:考虑下面的方案组合(所有下标均从 0 开始):

  • 选择 1 号基料:成本 3
  • 选择 1 份 0 号配料:成本 1 x 4 = 4
  • 选择 2 份 1 号配料:成本 2 x 5 = 10
  • 选择 0 份 2 号配料:成本 0 x 100 = 0 总成本:3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3:

输入:baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出:8
解释:可以制作总成本为 8 和 10 的甜点。返回 8 ,因为这是成本更低的方案。

示例 4:

输入:baseCosts = [10], toppingCosts = [1], target = 1
输出:10
解释:注意,你可以选择不添加任何配料,但你必须选择一种基料。

提示:

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 104
1 <= target <= 104

思路

递归加回溯

  1. 题目要求的意思是基料必须选一种,对于每种配料可以①不选②选一次③选两次
  2. 我们可以在外层嵌套一层for循环,遍历所有的基料
  3. 递归中我们遍历所有配料,并将每种配料的选择分为上述三种情况,依次向下遍历累加即可,注意这里含有回溯思想。把每次结果记入集合中
  4. 最后我们可以得到所有情况的集合,根据题目要求我们可以再将集合排序,规则为结果减去target的绝对值从小到大排序,二者相等的话根据结果的大小从小到大排序。最后挑选排序后的第一个元素即为所求

题解

class Solution:
    def closestCost(self, baseCosts: List[int], toppingCosts: List[int], target: int) -> int:
        ans = set()
        # 递归,求出所有添加配料可能的结果
        def dfs(s, index, toppingCosts):
            ans.add(s)
            for i in range(index, len(toppingCosts)):
                for j in [1,2]:
                    dfs(s + j * toppingCosts[i], i+1, toppingCosts)
        # 外层循环为基料
        for i in baseCosts:
            dfs(i, 0, toppingCosts)
        # 最后返回排序后的第一个元素
        return sorted(ans, key = lambda x: (abs(x-target), x))[0]

相关文章:

  • [附源码]JAVA毕业设计口腔医院网站(系统+LW)
  • 电子学会2021年3月青少年软件编程(图形化)等级考试试卷(四级)答案解析
  • 微服务架构
  • 研发效能工程实践-利用Superset快速打造大数据BI平台
  • Springboot RabbitMq源码解析之RabbitListener注解 (四)
  • MedNeRF:用于从单个X射线重建3D感知CT投影的医学神经辐射场
  • 性能测试工具:如何录制脚本?
  • Dubbo SPI扩展机制源码详解(基于2.7.10)
  • 创建你的第⼀个XXL-Job分布式调度任务
  • 基于X86的运算板卡加速边缘智能应用
  • 基于MCMC的交通量逆建模(Matlab代码实现)
  • [附源码]计算机毕业设计校园代取快递系统Springboot程序
  • MapStruct与lombok加载顺序问题与annotationProcessorPaths的关系?
  • Express:CORS 跨域资源共享
  • SpringBoot+Vue项目便捷洗衣服务平台
  • c语言结构体看这篇文章就够啦(详细介绍结构体)
  • MySQL主从复制
  • 公众号网课题库接口
  • 《C++ Primer Plus》第九章:内存模型和名称空间(1)
  • JAVA复习【11】单列集合Collection:ArrayList、 LinkedList、HashSet、TreeSet学习与使用
  • 格式化并挂载ubi文件系统过程详解
  • 自由概率(Free probability)
  • 大数据之HBase基础
  • Python爬虫教你爬取视频信息
  • 基于微信小程序的火锅店点餐系统小程序
  • 一文带你吃透红黑树---红黑树如此简单
  • 经济的1000+篇文章总结
  • 【数据结构】基础:AVL树(平衡二叉树)
  • 【C++11】lambda表达式、包装器、bind 与 placeholders
  • 【深度学习基础6】自编码器及其变体
  • 2023年重庆高考588分能报什么大学 588分能上哪些院校
  • 2023年山东春季高考考试时间 什么时候考试
  • 单招被调剂可以不去吗 还能高考吗
  • 2023湖南双一流大学名单 湖南哪所学校好
  • 中专考大学要考什么科目 内容有哪些
  • 预计2023国家专项计划录取分数线是多少
  • 2021年浙江工商大学杭州商学院学费是多少 各专业收费标准
  • 神经科学专业课程有哪些
  • 2023软件工程专业课程有哪些 就业方向是什么
  • 现在进行时结构是什么 怎么构成的