LeetCode 2706. 购买两块巧克力【数组,一次遍历】1207

2024-01-01 21:04

本文主要是介绍LeetCode 2706. 购买两块巧克力【数组,一次遍历】1207,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组 prices ,它表示一个商店里若干巧克力的价格。同时给你一个整数 money ,表示你一开始拥有的钱数。

你必须购买 恰好 两块巧克力,而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。

请你返回在购买两块巧克力后,最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱,请你返回 money 。注意剩余钱数必须是非负数。

示例 1:

输入:prices = [1,2,2], money = 3
输出:0
解释:分别购买价格为 12 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0

示例 2:

输入:prices = [3,2,3], money = 3
输出:3
解释:购买任意 2 块巧克力都会超过你拥有的钱数,所以我们返回 3

提示:

  • 2 <= prices.length <= 50
  • 1 <= prices[i] <= 100
  • 1 <= money <= 100

解法 一次遍历

遍历 prices \textit{prices} prices ,维护最小值 mn 1 \textit{mn}_1 mn1 和次小值 mn 2 \textit{mn}_2 mn2

如果 mn 1 + mn 2 > money \textit{mn}_1+\textit{mn}_2>\textit{money} mn1+mn2>money ,那么剩余的钱会变成负数,返回 money \textit{money} money ,否则返回 money − mn 1 − mn 2 \textit{money}-\textit{mn}_1-\textit{mn}_2 moneymn1mn2

// python
class Solution:def buyChoco(self, prices: List[int], money: int) -> int:mn1 = mn2 = inffor p in prices:if p < mn1:mn2 = mn1mn1 = pelif p < mn2:mn2 = preturn money if mn1 + mn2 > money else money - mn1 - mn2// go
func buyChoco(prices []int, money int) int {mn1, mn2 := math.MaxInt, math.MinIntfor _, p := range prices {if p < mn1 {mn2 = mn1mn1 = p} else if p < mn2 {mn2 = p}}if mn1 + mn2 <= money {return money - mn1 - mn2}return money
}

复杂度分析:

  • 时间复杂度: O ( n ) \mathcal{O}(n) O(n) ,其中 n n n p r i c e s prices prices 的长度。
  • 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1) 。仅用到若干额外变量。

这篇关于LeetCode 2706. 购买两块巧克力【数组,一次遍历】1207的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/560507

相关文章

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

WiFi6时代来临! 华三H3C NX54路由器还值得购买吗?

《WiFi6时代来临!华三H3CNX54路由器还值得购买吗?》WiFi6时代已经来临,众多路由器厂商也纷纷推出了兼容WiFi6协议的路由器,今天我们将深入体验H3CNX54路由器,这款由知名企业... 随着科技的发展,WiFi6逐渐走进了我们的日常生活之中,相比WiFi5来说,WiFi6拥有更高的带宽、更高

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu