diff options
Diffstat (limited to 'avoid_flood_city.c')
-rw-r--r-- | avoid_flood_city.c | 123 |
1 files changed, 123 insertions, 0 deletions
diff --git a/avoid_flood_city.c b/avoid_flood_city.c new file mode 100644 index 0000000..92a1a29 --- /dev/null +++ b/avoid_flood_city.c @@ -0,0 +1,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); +} |