diff options
Diffstat (limited to 'longest_harmonious_subseq.c')
-rw-r--r-- | longest_harmonious_subseq.c | 62 |
1 files changed, 62 insertions, 0 deletions
diff --git a/longest_harmonious_subseq.c b/longest_harmonious_subseq.c new file mode 100644 index 0000000..1c1e5b4 --- /dev/null +++ b/longest_harmonious_subseq.c @@ -0,0 +1,62 @@ +// 594. Longest Harmonious Subsequence +#include "leetcode.h" + +/* + * we define a harmonious array as an array where the difference between its + * maximum value and its minimum value is exactly 1. given an integer array + * 'nums', return the length of the its longest harmonious subsequnce among all + * its possible subsequnces. + */ + +struct hash { + int num; + int cnt; + UT_hash_handle hh; +}; + +struct hash *mem; +static int idx; + +int *entry(struct hash **set, int n) { + struct hash *tmp; + HASH_FIND_INT(*set, &n, tmp); + if (!tmp) { + tmp = &mem[idx++]; + tmp->num = n; + tmp->cnt = 0; + HASH_ADD_INT(*set, num, tmp); + } + return &(tmp->cnt); +} + +bool contains(struct hash **obj, int num) { + struct hash *tmp; + HASH_FIND_INT(*obj, &num, tmp); + return tmp; +} + +int findLHS(int *nums, int numsSize) { + struct hash *set = NULL, *p, *tmp, *s; + int ans = 0; + idx = 0; + mem = (struct hash *)calloc(numsSize, sizeof(struct hash)); + for (int i = 0; i < numsSize; i++) + (*entry(&set, nums[i]))++; + HASH_ITER(hh, set, s, tmp) { + int key = s->num; + if (contains(&set, key + 1)) { + int sum = *entry(&set, key) + *entry(&set, key + 1); + if (sum > ans) + ans = sum; + } + } + free(mem); + return ans; +} + +int main() { + int n1[] = {1, 3, 2, 2, 5, 2, 3, 7}, n2[] = {1, 2, 3, 4}, n3[] = {1, 1, 1, 1}; + printf("%d\n", findLHS(n1, ARRAY_SIZE(n1))); // expect: 5 + printf("%d\n", findLHS(n2, ARRAY_SIZE(n2))); // expect: 2 + printf("%d\n", findLHS(n3, ARRAY_SIZE(n3))); // expect: 0 +} |