diff options
-rw-r--r-- | product_last_k_num.c | 67 | ||||
-rw-r--r-- | product_last_k_num.py | 47 |
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)) |