LongestHarmoniousSubsequence2 [source code]

public class LongestHarmoniousSubsequence2 {
static

public class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int maxLen = 0;
        int firstPrev = 0, secondPrev = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > nums[firstPrev]) {
                if (nums[i] - nums[firstPrev] == 1) {
                    if (nums[i] > nums[secondPrev]) secondPrev = i;
                } else if (nums[i - 1] - nums[firstPrev] == 1) {
                    maxLen = Math.max(maxLen, i - firstPrev);
                    if (nums[i] - nums[i - 1] == 1) {
                        firstPrev = secondPrev;
                        secondPrev = i;
                    } else {
                        firstPrev = secondPrev = i;
                    }
                } else firstPrev = secondPrev = i;
            }
        }
        return Math.max(maxLen, secondPrev > firstPrev ? (nums.length - firstPrev) : 0);
    }
}

    public static void main(String[] args) {
        LongestHarmoniousSubsequence2.Solution tester = new LongestHarmoniousSubsequence2.Solution();
        int[] input1 = {1,3,2,2,5,2,3,7};//5
        int[] input2 = {1,3,5,7,9,11,13,15,17};//0
        int[] input3 = {4289383,46930886,81692777,14636915,57747793,24238335,19885386,49760492,96516649,89641421};//0
        int[] input4 = {1,3,2,2,5,2,3,6,2,1,2,3,2,3,2,3,2,3,7};//5
        int[] input5 = {1,2,2,1};//4
        int[] input6 = {1,2,3,3,1,-14,13,4};//3
        assert tester.findLHS(input1) == 5;
        assert tester.findLHS(input2) == 0;
        assert tester.findLHS(input3) == 0;
        assert tester.findLHS(input4) == 14;
        assert tester.findLHS(input5) == 4;
        assert tester.findLHS(input6) == 3;

        System.out.println(tester.findLHS(input6));
    }
}

单纯的直接hash的问题就是最后 space 占用直接取决于值域. 其实最后的 time 也取决于这个值域区间. 这个在性能上其实就很容易吃亏;

硬要做, 用 hashtable count 了之后, 按key 排序,应该也是不难做的; 不过感觉速度会不太好;

感觉这个题目直接 sort 了做更好写;
sort了之后的一个比较简化的思路就是每一个 value 的starting index都可以用一个 table 记录下来; 不过这个感觉不是最优解;

花了好长时间, 终于做出来了, 不过最后做出来的是最优解!!! 43(99.61), 人生中第一个绝对最优解, 而且还花了这么多功夫之后得到的, 真的是满足感爆棚.

整个算法就是要依靠逻辑链来进行分析吧, 这个算法的时候就显示出大括号不能随便绕, 不然真把自己绕晕了.

前面的逻辑其实都还算不难处理, 就是最后一个 branch 的:

} else firstPrev = secondPrev = i;

这个自己写的时候真是没有想到, 最后是被 input6给 break 出来的. 最后这个加上去完全就是为了专门处理这个的情况. 这个 branch只有在最开头的时候才会发生, 最开始first 和 second 都还在一起的时候, 然后后面出现一个大的 uptick, 这个时候你前面两个 branch 是都匹配不上的, 只能专门为这个情形准备一个 branch.

另外, 还是老生常谈了, 写这种逻辑链的时候, && in conditional header, 真的是太危险了, 真的不要随便乱用, 有点时候nested if真的是必要的. 这种&&在if header 里面的错误使用, 会让后面的所有 else 的 parse 都出错;

不过这个题的题号是594, 算是新题, 估计现在提交的人也不多, 后面我这个算法估计还是可能会被超越;

另外尽管这个算法最后的结果很好, 但是真正面试的时候人家肯定还是要问你 hashtable 的O(n) 的算法的:

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

这个解还是很干脆的. 我本来以为如果直接用 hashtable 做, count 完了需要 sort, 结果反而是不需要 sort 的;

这个是一个优化成1pass 的版本:

public class Solution {  
    public int findLHS(int[] nums) {  
        HashMap < Integer, Integer > map = new HashMap < > ();  
        int res = 0;  
        for (int num: nums) {  
            map.put(num, map.getOrDefault(num, 0) + 1);  
            if (map.containsKey(num + 1))  
                res = Math.max(res, map.get(num) + map.get(num + 1));  
            if (map.containsKey(num - 1))  
                res = Math.max(res, map.get(num) + map.get(num - 1));  
        }  
        return res;  
    }  
}

Problem Description

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.

Difficulty:Easy
Category:Algorithms
Acceptance:39.79%
Contributor: love_Fawn
Companies
liveramp
Related Topics
hash table