aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--product_last_k_num.c67
-rw-r--r--product_last_k_num.py47
2 files changed, 114 insertions, 0 deletions
diff --git a/product_last_k_num.c b/product_last_k_num.c
new file mode 100644
index 0000000..a0ed930
--- /dev/null
+++ b/product_last_k_num.c
@@ -0,0 +1,67 @@
+// 1352. Product of the Last K Numbers
+#include "leetcode.h"
+
+/*
+ * design an algorithm that accepts a stream of integers and retrieves the
+ * product of the last 'k' integers of the stream. implement the
+ * 'ProductOfNumbers' class. the test cases are generated so that at any time,
+ * the product of any contiguous sequence of numbers will fit into a single
+ * 32-bit integer without overflowing.
+ */
+
+typedef struct {
+ int *pre;
+ int size;
+ int capacity;
+} ProductOfNumbers;
+
+ProductOfNumbers *productOfNumbersCreate() {
+ ProductOfNumbers *obj =
+ (ProductOfNumbers *)calloc(1, sizeof(ProductOfNumbers));
+ obj->pre = (int *)calloc(2, sizeof(int));
+ obj->pre[0] = 1;
+ obj->size = 1;
+ obj->capacity = 2;
+ return obj;
+}
+
+void productOfNumbersAdd(ProductOfNumbers *obj, int num) {
+ if (obj->size == obj->capacity) {
+ obj->capacity *= 2;
+ obj->pre = (int *)realloc(obj->pre, obj->capacity * sizeof(int));
+ }
+ if (num) {
+ int prev = obj->pre[obj->size - 1];
+ obj->pre[obj->size++] = prev * num;
+ } else {
+ obj->size = 0;
+ obj->capacity = 2;
+ obj->pre = (int *)realloc(obj->pre, obj->capacity * sizeof(int));
+ obj->pre[obj->size++] = 1;
+ }
+}
+
+int productOfNumbersGetProduct(ProductOfNumbers *obj, int k) {
+ return k < obj->size ? obj->pre[obj->size - 1] / obj->pre[obj->size - k - 1]
+ : 0;
+}
+
+void productOfNumbersFree(ProductOfNumbers *obj) {
+ free(obj->pre);
+ free(obj);
+}
+
+int main() {
+ ProductOfNumbers *obj = productOfNumbersCreate();
+ productOfNumbersAdd(obj, 3);
+ productOfNumbersAdd(obj, 0);
+ productOfNumbersAdd(obj, 2);
+ productOfNumbersAdd(obj, 5);
+ productOfNumbersAdd(obj, 4);
+ printf("%d\n", productOfNumbersGetProduct(obj, 2)); // expect: 20
+ printf("%d\n", productOfNumbersGetProduct(obj, 3)); // expect: 40
+ printf("%d\n", productOfNumbersGetProduct(obj, 4)); // expect: 0
+ productOfNumbersAdd(obj, 8);
+ printf("%d\n", productOfNumbersGetProduct(obj, 2)); // expect: 32
+ productOfNumbersFree(obj);
+}
diff --git a/product_last_k_num.py b/product_last_k_num.py
new file mode 100644
index 0000000..e555476
--- /dev/null
+++ b/product_last_k_num.py
@@ -0,0 +1,47 @@
+# 1352. Product of the Last K Numbers
+
+"""
+design an algorithm that accepts a stream of integers and retrieves the
+product of the last 'k' integers of the stream. implement the
+'ProductOfNumbers' class. the test cases are generated so that at any time,
+the product of any contiguous sequence of numbers will fit into a single
+32-bit integer without overflowing.
+"""
+
+
+class ProductOfNumbers(object):
+ def __init__(self):
+ self.pre = [1]
+
+ def add(self, num):
+ """
+ :type num: int
+ :rtype: None
+ """
+ if num == 0:
+ self.pre = [1]
+ else:
+ self.pre.append(self.pre[-1] * num)
+
+ def getProduct(self, k):
+ """
+ :type k: int
+ :rtype: int
+ """
+ if k >= len(self.pre):
+ return 0
+ return self.pre[-1] / self.pre[-k - 1]
+
+
+if __name__ == "__main__":
+ obj = ProductOfNumbers()
+ obj.add(3)
+ obj.add(0)
+ obj.add(2)
+ obj.add(5)
+ obj.add(4)
+ print(obj.getProduct(2))
+ print(obj.getProduct(3))
+ print(obj.getProduct(4))
+ obj.add(8)
+ print(obj.getProduct(2))