FanluLeetcode/src/hashtable/LongestHarmoniousSubsequence.java at master · Fanlu91/FanluLeetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package hashtable;

import java.util.*;

// Source : https://leetcode.com/problems/longest-harmonious-subsequence/
// Id     : 594
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date   : 2019-06-20
// Topic  : Hashtable
// Level  : Easy+
// Other  :
// Tips   :
// Result : 100.00% 13.99%
public class LongestHarmoniousSubsequence {
    // 5.70% 110 ms 19.33%
    public int findLHSOrigin(int[] nums) {
        if (nums.length < 2)
            return 0;

        Map<Double, Integer> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i] - 0.5, map.getOrDefault(nums[i] - 0.5, 0) + 1);
            map.put(nums[i] + 0.5, map.getOrDefault(nums[i] + 0.5, 0) + 1);
            set.add(nums[i]);
        }

        int ans = 0;
        for (Double d : map.keySet()) {
//            System.out.println(d +" "+ map.get(d));
            if (set.contains((int) (d - 0.5)) && set.contains((int) (d + 0.5))) {
                ans = ans < map.get(d) ? map.get(d) : ans;
            }
        }
        return ans;
    }

    //! Memory Limit Exceeded
    public int findLHSMemoryLimitExceeded(int[] nums) {
        if (nums.length < 2)
            return 0;
        int[] array = new int[Integer.MAX_VALUE];
        for (int i = 0; i < nums.length; i++) {
            array[i]++;
        }
        int ans = 0;
        for (int i = 0; i < nums.length - 1; ) {
            if (nums[i] == 0) {
                i++;
                continue;
            }
            if (nums[i + 1] == 0) {
                i += 2;
                continue;
            }
            ans = ans < nums[i] + nums[i + 1] ? nums[i] + nums[i + 1] : ans;
            i++;
        }
        return ans;
    }

    // 58.14% 31 ms 99.00%
    public int findLHSWithHashtable(int[] nums) {
        if (nums.length < 2)
            return 0;
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        for (int key : map.keySet()) {
            if (map.containsKey(key - 1))
                ans = ans < map.get(key) + map.get(key - 1) ? map.get(key) + map.get(key - 1) : ans;
            if (map.containsKey(key + 1))
                ans = ans < map.get(key) + map.get(key + 1) ? map.get(key) + map.get(key + 1) : ans;
        }
        return ans;
    }

    /*
     * Learned from leetcode submission, one way to do this is using hash like what I did above,
     * another way usually involves do things with sorted array.
     *
     * */
    // 100.00% 15ms, 13.99%
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int prevCount = 0, ans = 0, count;
        for (int i = 0; i < nums.length; i++) {
            count = 1;
            // if ith is equal to (i-1)th, look back
            if (i > 0 && nums[i] - nums[i - 1] == 1) {
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    count++; // only count current element, every element will have its own check
                    i++;
                }
                ans = Math.max(ans, count + prevCount);
                prevCount = count;
            } else {
                // look forward
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    count++; // only count current element, every element will have its own check
                    i++;
                }
                prevCount = count;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        LongestHarmoniousSubsequence l = new LongestHarmoniousSubsequence();
        System.out.println(l.findLHS(new int[]{1, 1, 1, 2, 2, 2}));
    }
}