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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
// 1488. Avoid Flood in The City
#include "leetcode.h"
/*
* your country has an infinite number of lakes. initially, all the lakes are
* empty. but when it rains over the n'th lake, the n'th lake becomes full of
* water. if it rains over a lake that is full of water, there will be a flood.
* your goal is to avoid any floods. if there are multiple valid answers, return
* any of them. if it is impossible to avoid flood, return an empty array.
* notice that if yo uchose to dry a full lake, it becomes empty. but if you
* chose to dry an empty lake, nothing happens.
*/
#define HASH_SIZE 200003
struct hash_entry {
int key;
int val;
bool used;
};
int hash_func(int key) {
if (key < 0)
key = -key;
return key % HASH_SIZE;
}
int *hash_get(struct hash_entry *obj, int key) {
int hash = hash_func(key);
while (obj[hash].used) {
if (obj[hash].key == key)
return &obj[hash].val;
hash++;
if (hash == HASH_SIZE)
hash = 0;
}
return NULL;
}
int *hash_put(struct hash_entry *obj, int key, int val) {
int hash = hash_func(key);
while (obj[hash].used) {
if (obj[hash].key == key) {
obj[hash].val = val;
return &obj[hash].val;
}
hash++;
if (hash == HASH_SIZE)
hash = 0;
}
obj[hash].used = true;
obj[hash].key = key;
obj[hash].val = val;
return &obj[hash].val;
}
int dry_day(int *dry_days, int dry_cnt, int target) {
int low = 0, high = dry_cnt - 1, res = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (dry_days[mid] > target) {
res = mid;
high = mid - 1;
} else
low = mid + 1;
}
return res;
}
int *avoidFlood(int *rains, int rainsSize, int *returnSize) {
*returnSize = rainsSize;
int *ans = (int *)malloc(rainsSize * sizeof(int));
int *dry = (int *)malloc(rainsSize * sizeof(int));
int dry_cnt = 0;
struct hash_entry *hash_table =
(struct hash_entry *)calloc(HASH_SIZE, sizeof(struct hash_entry));
for (int i = 0; i < rainsSize; i++) {
if (!rains[i]) {
dry[dry_cnt++] = i;
ans[i] = 1;
} else {
int *prev = hash_get(hash_table, rains[i]);
if (prev) {
int idx = dry_day(dry, dry_cnt, *prev);
if (idx == -1) {
free(ans);
free(dry);
free(hash_table);
*returnSize = 0;
return NULL;
}
int day = dry[idx];
ans[day] = rains[i];
memmove(dry + idx, dry + idx + 1, (dry_cnt - idx - 1) * sizeof(int));
dry_cnt--;
}
hash_put(hash_table, rains[i], i);
ans[i] = -1;
}
}
free(dry);
free(hash_table);
return ans;
}
int main() {
int r1[] = {1, 2, 3, 4}, r2[] = {1, 2, 0, 0, 2, 1}, r3[] = {1, 2, 0, 1, 2};
int rs1, *af1 = avoidFlood(r1, ARRAY_SIZE(r1), &rs1);
int rs2, *af2 = avoidFlood(r2, ARRAY_SIZE(r2), &rs2);
int rs3, *af3 = avoidFlood(r3, ARRAY_SIZE(r3), &rs3);
for (int i = 0; i < rs1; i++)
printf("%d ", af1[i]); // expect: -1 -1 -1 -1
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", af2[i]); // expect: -1 -1 2 1 -1 -1
printf("\n");
for (int i = 0; i < rs3; i++)
printf("%d ", af3[i]); // expect: null
printf("\n");
free(af1);
free(af2);
free(af3);
}
|