LeetCode/Java/904.java at master · strengthen/LeetCode · 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
117
118
119
120
121
122
123
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
    public int totalFruit(int[] tree) {
        if(tree.length==0){
            return 0;
        }
        int present = tree[0];
        int present_index= 0;
        int index = 1, start=0, maxLen = 0;
        while(index<tree.length && tree[index]==present){
            index++;
        }
        if(index==tree.length){
            return index-start;
        }
        int previous = present;
        int previous_index = index-1;
        present = tree[index];
        present_index = index;
        while(index<tree.length){
            if(tree[index]==previous){
                previous = present;
                present = tree[index];
                present_index = index;
            }
            else if(tree[index]!=present){
                maxLen = Math.max(index-start, maxLen);
                start = present_index;
                previous = present;
                present = tree[index];
                present_index = index;
            }
            index++;
        }
        return Math.max(maxLen, index-start);

    }
}
__________________________________________________________________________________________________
sample 43216 kb submission
class Solution {

    /*
    add to j
    if map moe than 2
        then move i;
    update ans
    */

    public class CountMap {
        HashMap<Integer, Integer> map;

        public CountMap() {
            map = new HashMap();
        }

        public int size() {
            return map.size();
        }

        public int get(int k) {
            if(!map.containsKey(k)) {
                map.put(k,0);
            }
            return map.get(k);
        }

        public void put(int k, int v) {
            int val = get(k) + v;
            if (val == 0) {
                map.remove(k);
            } else {
                map.put(k, val);
            }
        }
    }
    public int totalFruit(int[] tree) {
        int ans = 0;
        int f = 0;
        CountMap map = new CountMap();
        for (int s = 0; s < tree.length; s++) {
            map.put(tree[s], 1);
            while(map.size() > 2) {
                map.put(tree[f++], -1);
            }
            ans = Math.max(ans, s-f+1);
        }
        return ans;
    }

    public int totalFruit(int[] tree, int i) {
        /*
        0 - 1
        1 - 2
        2 - 1


        */

        int a = Integer.MIN_VALUE, b = Integer.MIN_VALUE;
        int ans = 0;
        for (; i < tree.length; i++) {
            if (tree[i] == a || tree[i] == b)   {
                ans++;
                continue;
            }
            if (a == Integer.MIN_VALUE) {
                a = tree[i];
                ans++;
            } else if (b == Integer.MIN_VALUE) {
                b = tree[i];
                ans++;
            } else {
                break;
            }
        }

        return ans;
    }
}
__________________________________________________________________________________________________