diff options
author | Jack Sangdahl <[email protected]> | 2025-06-29 18:50:02 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-29 18:50:02 -0600 |
commit | 15efdf1024a15a3f8016f31063fc0ce286ef5b2b (patch) | |
tree | 093ee02e340c168ed40e9e8860c8a4c580dc001d | |
parent | 2815a0d9727446bb9f4a1cbd4bed70eb58e97298 (diff) | |
download | leetcode-15efdf1024a15a3f8016f31063fc0ce286ef5b2b.tar.gz leetcode-15efdf1024a15a3f8016f31063fc0ce286ef5b2b.zip |
594. longest harmonious subsequence
-rw-r--r-- | longest_harmonious_subseq.c | 62 | ||||
-rw-r--r-- | longest_harmonious_subseq.py | 26 |
2 files changed, 88 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 +} diff --git a/longest_harmonious_subseq.py b/longest_harmonious_subseq.py new file mode 100644 index 0000000..1252090 --- /dev/null +++ b/longest_harmonious_subseq.py @@ -0,0 +1,26 @@ +# 594. Longest Harmonious Subsequence +from collections import Counter + +""" +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. +""" + + +class Solution(object): + def findLHS(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + c = Counter(nums) + return max((c[i] + c[i + 1]) * (c[i + 1] != 0) for i in c) + + +if __name__ == "__main__": + obj = Solution() + print(obj.findLHS(nums=[1, 3, 2, 2, 5, 2, 3, 7])) + print(obj.findLHS(nums=[1, 2, 3, 4])) + print(obj.findLHS(nums=[1, 1, 1, 1])) |