Massive Algorithms: LeetCode 594

https://leetcode.com/problems/longest-harmonious-subsequence

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

https://discuss.leetcode.com/topic/89990/simple-java-hashmap-solution

The idea is to keep a count of all the numbers, and eventually for each of the numbers, check if there's any adjacent number. If it's present, then add the count of both - since these two numbers form subsequence in the array.

Update : from @harkness comment, we don't need to check both +1 and -1;

Any reason to use long instead of int?

to handle this :

findLHS(new int[]{-2147483648 , 2147483647});
//2147483647 + 1 = -2147483648 , and we don't want that.

public int findLHS(int[] nums) {
    Map<Long, Integer> map = new HashMap<>();
    for (long num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    int result = 0;
    for (long key : map.keySet()) {
        if (map.containsKey(key + 1)) {
            result = Math.max(result, map.get(key + 1) + map.get(key));
        }
    }
    return result;
}

http://bookshadow.com/weblog/2017/05/21/leetcode-longest-harmonious-subsequence/

用字典cnt统计各数字出现的次数。

升序遍历cnt的键值对

X. https://discuss.leetcode.com/topic/90049/simple-java-sort-solution-beat-100

public int findLHS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    Arrays.sort(nums);
    int start = 0;
    int min = nums[0];
    int res = 0;
    int nextstart = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] - min > 1) {
            start = nextstart++;
            min = nums[start];
            i--;
        } else if (nums[i] - min == 1) {
            res = Math.max(res, i - start + 1);
            if (nums[i] != nums[i - 1]) {
                nextstart = i;
            }
        }
    }
    return res;
}

X. https://discuss.leetcode.com/topic/90049/simple-java-sort-solution-beat-100

public int findLHS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    Arrays.sort(nums);
    int start = 0;
    int min = nums[0];
    int res = 0;
    int nextstart = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] - min > 1) {
            start = nextstart++;
            min = nums[start];
            i--;
        } else if (nums[i] - min == 1) {
            res = Math.max(res, i - start + 1);
            if (nums[i] != nums[i - 1]) {
                nextstart = i;
            }
        }
    }
    return res;
}

https://medium.com/@xingren14/594-longest-harmonious-subsequence-94c93f83a4af

首先这个是subsequence，所以其实原数组的顺序已经不重要了，或者说顺序根本不是考察的范围所能用得到的，所以我们要么可以排序再分析，要么就是利用HashMap来统计频率，这也是我知道的两个解法的始源

先说排序的算法：

排序了，然后怎么分析呢？一开始想的是直接遍历然后看是不是比前一个大一或者相等。我擦这么明显的错误都能犯？不是检测是不是递增，而是相差1的子数组相当于，否则连[1,2,3]这样的数组都不过测试。那就增加个临时变量表示之前的数字？还是不对因为这样还需要回溯，但是又回到哪里去呢？我们只设一个指针来遍历是不够的。那么我们用俩
两个指针其实就是我们最喜闻乐见的sliding window了。但是这个sliding window又稍微有些不一样。一般siliding window是超出范围后结算的。但是这道题怎么说是“超出范围”呢？如果我们是决定num[right] 比 num[left] 大超过1是超出范围应该结算的话，那么这个test case就不对了：[1,1,1,4] 这个应该返回0，但是会被错误地返回3。思来想去这道题的关键是当出现rigth比left的值大1的时候，我们才可以自信的说我们有harmonious subsequence，因为如果是1 1 1 1 或者 1，3，5，8都是不行的。
于是结算就不是发现窗口扩展不下去了再结算，而是每次只要有效都要结算。动态增加而不是最后结算。这样每次看到right比left的值大1就更新下res并right＋＋。其他如果right比left大于超过1。left＋＋，否则(其实也就是等于1) right＋＋。

再说HashMap，这个思路完全不一样，先遍历数组统计各数字的频率，然后再遍历一次来看每个数字是否其＋1和－1的数也在hashmap里，如果在就把俩人的freq的和跟res比，谁大要谁。然后将当前数字从map里删掉以免重复比较。

这个思路很简单而且只需要O(n)的时间和O(n)的space。但是其运行速度却比上一个要慢了50％，为什么呢？我能想到的就是hashmap的查找和增删时间的消耗。

LeetCode 594 - Longest Harmonious Subsequence

Labels

Popular Posts