leetcode
leetcode 1951 ~ 2000
买钢笔和铅笔的方案数

买钢笔和铅笔的方案数

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.1 MB


/*
 * Problem: Same as above.
 *
 * Approach using Java Streams:
 * 1. We use IntStream to generate the number of pens we can buy.
 * 2. For each number of pens, calculate the remaining money and determine the number of pencils that can be bought.
 * 3. Sum up all the combinations using the sum method of the IntStream.
 */

import java.util.stream.IntStream;

public class Solution {
    public int waysToBuyPensPencils(int total, int cost1, int cost2) {
        return IntStream.rangeClosed(0, total / cost1)
                .map(pens -> (total - pens * cost1) / cost2 + 1)
                .sum();
    }
}

解释

方法:

此题解采用了一个递归函数,以及主函数计算购买方案的数目。主函数首先确定能购买的最大钢笔数量n,然后计算剩余的钱数b。递归函数f(a, b, c, n)用来计算钢笔和铅笔的购买组合数,其中a为钢笔价格,b为剩余钱数,c为铅笔价格,n为最大可以购买的钢笔数量。递归函数首先检查a是否大于等于c,若是,根据等差数列求和公式计算组合数。然后剩余的钱数b用来检查能否直接按价格c买铅笔。接着,如果b还有剩余,则继续计算购买m支铅笔后还能买多少支钢笔的情况,通过递归调用f计算。这个递归过程会逐渐减小问题的规模,直到一方商品买不起为止。

时间复杂度:

O(total / cost2)

空间复杂度:

O(total / cost2)

代码细节讲解

🦆
递归函数f中的条件`if a >= c`的存在是为了什么?这里的逻辑是如何帮助减少计算次数的?
这个条件用于检查当前钢笔的价格`a`是否大于等于铅笔的价格`c`。当`a >= c`时,可以将钢笔的价格对铅笔的价格进行取模操作,从而简化计算。这是因为,如果钢笔价格高于或等于铅笔价格,那么在计算购买组合时,可以将部分钢笔价格转换为多个铅笔的购买,这样可以减少后续计算的复杂度。通过取模后,钢笔的新价格(即余数)会变小,从而在后续递归调用中减少计算量。
🦆
在递归函数f中,如何理解这一行代码`res += (a // c) * n * (n+1) // 2`,它的计算原理和目的是什么?
这行代码利用了等差数列的求和公式来快速计算在钢笔价格模铅笔价格后,仍然能够购买的铅笔数量。`a // c`计算了每种钢笔购买方案中可以额外购买的铅笔数量,而`n * (n+1) // 2`则是从0到n的等差数列和,代表了不同购买数量的钢笔时可以额外获得的铅笔总数。这种方式可以在不逐一枚举每种购买方案的情况下,快速计算出可以额外购买的铅笔总数,从而加速整个计算过程。
🦆
为什么在递归函数f中,当`a == 0`时,可以直接返回`res + (b // c) * (n + 1)`?这里的逻辑是基于什么考虑?
当`a == 0`时,表示钢笔的价格经过取模后为0,即铅笔价格是钢笔价格的整数倍。这种情况下,钢笔的价格对计算铅笔的购买数量不再有任何影响,因此可以直接计算剩余金额`b`能购买多少铅笔,并将结果乘以总的钢笔购买方案数(包括不购买钢笔的情况,即`n + 1`)。这样可以直接得到总的购买组合数,无需进一步递归,从而简化了计算过程。
🦆
递归函数f使用了表达式`m * n - f(c, c - b - 1, a, m-1)`来计算剩余的方案数,这种方式有什么特别的意义或优势?
这个表达式利用了递归来交换钢笔和铅笔的角色,从而减少计算的复杂度。`m`代表在当前剩余金额和价格条件下,最多可以购买的铅笔数量。`m * n`计算了在买了m支铅笔的情况下所有可能的钢笔购买方案。然后使用`f(c, c - b - 1, a, m-1)`递归计算在钢笔和铅笔价格交换,且金额调整后的剩余情况中,不重复计算已经考虑过的组binations。这种方法通过递归处理和角色交换,允许算法在较小的搜索空间内进行,从而优化了性能并减少了重复计算。

相关问题