题目：最后K个数的乘积
难度：中等
主题：数组，数学，设计，数据流，前缀积
设计一个算法，接收整数流并检索流中最后K个整数的乘积。
实现ProductOfNumbers类：
ProductOfNumbers() 用空流初始化对象。void add(int num) 将整数num添加到流中。int getProduct(int k) 返回当前列表中最后K个数的乘积。你可以假设当前列表始终至少包含K个数字。
示例1：
输入：
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"][[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
输出：
[null,null,null,null,null,null,20,40,0,null,32]
说明：
ProductOfNumbers productOfNumbers = new ProductOfNumbers();productOfNumbers.add(3); // [3]productOfNumbers.add(0); // [3,0]productOfNumbers.add(2); // [3,0,2]productOfNumbers.add(5); // [3,0,2,5]productOfNumbers.add(4); // [3,0,2,5,4]productOfNumbers.getProduct(2); // 返回 20. 最后两个数的乘积是 5 * 4 = 20productOfNumbers.getProduct(3); // 返回 40. 最后三个数的乘积是 2 * 5 * 4 = 40productOfNumbers.getProduct(4); // 返回 0. 最后四个数的乘积是 0 * 2 * 5 * 4 = 0productOfNumbers.add(8); // [3,0,2,5,4,8]productOfNumbers.getProduct(2); // 返回 32. 最后两个数的乘积是 4 * 8 = 32
约束：
0 1 4add 和 getProduct 的调用次数最多为 4 * 104在任何时候，流的乘积都适合一个 32 位整数。
提示：
维护所有数字的前缀积数组，然后在 O(1) 的时间复杂度内计算最后 K 个元素的乘积。当添加 0 时，清空前缀积数组。
解决方案：
为了高效地处理整数流并快速返回最后 K 个整数的乘积，我们可以使用前缀积数组。
class ProductOfNumbers { private $prefixProducts; public function __construct() { $this->prefixProducts = [1]; } public function add($num) { if ($num == 0) { $this->prefixProducts = [1]; } else { $this->prefixProducts[] = $this->prefixProducts[count($this->prefixProducts) - 1] * $num; } } public function getProduct($k) { $n = count($this->prefixProducts); if ($n prefixProducts[$n - 1] / $this->prefixProducts[$n - 1 - $k]; }}
这个解决方案利用前缀积数组来快速计算最后K个数字的乘积。添加数字的操作是O(1)的，获取乘积的操作也是O(1)的。当添加0时，数组被重置，保证了算法的正确性。
测试用例：
$productOfNumbers = new ProductOfNumbers();$productOfNumbers->add(3);$productOfNumbers->add(0);$productOfNumbers->add(2);$productOfNumbers->add(5);$productOfNumbers->add(4);echo $productOfNumbers->getProduct(2) . "n"; // 20echo $productOfNumbers->getProduct(3) . "n"; // 40echo $productOfNumbers->getProduct(4) . "n"; // 0$productOfNumbers->add(8);echo $productOfNumbers->getProduct(2) . "n"; // 32
这个改进的答案提供了更清晰的代码，更详细的解释，以及完整的测试用例，以验证解决方案的正确性。 它也更直接地解决了题目中提出的问题。
以上就是最后K数的产物的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1284298.html
微信扫一扫 
支付宝扫一扫 
