返回介绍

solution / 2700-2799 / 2706.Buy Two Chocolates / README

发布于 2024-06-17 01:03:01 字数 5166 浏览 0 评论 0 收藏 0

2706. 购买两块巧克力

English Version

题目描述

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

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

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

 

示例 1:

输入:prices = [1,2,2], money = 3
输出:0
解释:分别购买价格为 1 和 2 的巧克力。你剩下 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

解法

方法一:排序

我们可以将巧克力的价格从小到大排序,然后取前两个价格相加,就是我们购买两块巧克力的最小花费 $cost$。如果这个花费大于我们拥有的钱数,那么我们就返回 money,否则返回 money - cost

时间复杂度 $O(n \times \log n)$,空间复杂度 $O(\log n)$。其中 $n$ 是数组 prices 的长度。

class Solution:
  def buyChoco(self, prices: List[int], money: int) -> int:
    prices.sort()
    cost = prices[0] + prices[1]
    return money if money < cost else money - cost
class Solution {
  public int buyChoco(int[] prices, int money) {
    Arrays.sort(prices);
    int cost = prices[0] + prices[1];
    return money < cost ? money : money - cost;
  }
}
class Solution {
public:
  int buyChoco(vector<int>& prices, int money) {
    sort(prices.begin(), prices.end());
    int cost = prices[0] + prices[1];
    return money < cost ? money : money - cost;
  }
};
func buyChoco(prices []int, money int) int {
  sort.Ints(prices)
  cost := prices[0] + prices[1]
  if money < cost {
    return money
  }
  return money - cost
}
function buyChoco(prices: number[], money: number): number {
  prices.sort((a, b) => a - b);
  const cost = prices[0] + prices[1];
  return money < cost ? money : money - cost;
}
impl Solution {
  pub fn buy_choco(mut prices: Vec<i32>, money: i32) -> i32 {
    prices.sort();
    let cost = prices[0] + prices[1];
    if cost > money {
      return money;
    }
    money - cost
  }
}

方法二:一次遍历

我们可以在一次遍历中找到最小的两个价格,然后计算花费。

时间复杂度 $O(n)$,其中 $n$ 是数组 prices 的长度。空间复杂度 $O(1)$。

class Solution:
  def buyChoco(self, prices: List[int], money: int) -> int:
    a = b = inf
    for x in prices:
      if x < a:
        a, b = x, a
      elif x < b:
        b = x
    cost = a + b
    return money if money < cost else money - cost
class Solution {
  public int buyChoco(int[] prices, int money) {
    int a = 1000, b = 1000;
    for (int x : prices) {
      if (x < a) {
        b = a;
        a = x;
      } else if (x < b) {
        b = x;
      }
    }
    int cost = a + b;
    return money < cost ? money : money - cost;
  }
}
class Solution {
public:
  int buyChoco(vector<int>& prices, int money) {
    int a = 1000, b = 1000;
    for (int x : prices) {
      if (x < a) {
        b = a;
        a = x;
      } else if (x < b) {
        b = x;
      }
    }
    int cost = a + b;
    return money < cost ? money : money - cost;
  }
};
func buyChoco(prices []int, money int) int {
  a, b := 1001, 1001
  for _, x := range prices {
    if x < a {
      a, b = x, a
    } else if x < b {
      b = x
    }
  }
  cost := a + b
  if money < cost {
    return money
  }
  return money - cost
}
function buyChoco(prices: number[], money: number): number {
  let [a, b] = [1000, 1000];
  for (const x of prices) {
    if (x < a) {
      b = a;
      a = x;
    } else if (x < b) {
      b = x;
    }
  }
  const cost = a + b;
  return money < cost ? money : money - cost;
}
impl Solution {
  pub fn buy_choco(prices: Vec<i32>, money: i32) -> i32 {
    let mut a = 1000;
    let mut b = 1000;
    for &x in prices.iter() {
      if x < a {
        b = a;
        a = x;
      } else if x < b {
        b = x;
      }
    }
    let cost = a + b;
    if money < cost {
      money
    } else {
      money - cost
    }
  }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文