1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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);
}
|