买钢笔和铅笔的方案数
难度:
标签:
题目描述
代码结果
运行时间: 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`的存在是为了什么?这里的逻辑是如何帮助减少计算次数的?
▷🦆
在递归函数f中,如何理解这一行代码`res += (a // c) * n * (n+1) // 2`,它的计算原理和目的是什么?
▷🦆
为什么在递归函数f中,当`a == 0`时,可以直接返回`res + (b // c) * (n + 1)`?这里的逻辑是基于什么考虑?
▷🦆
递归函数f使用了表达式`m * n - f(c, c - b - 1, a, m-1)`来计算剩余的方案数,这种方式有什么特别的意义或优势?
▷