253. Meeting Rooms II

三刷
Version #3 Sort start & end at the same time

3.68 %
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        List<int[]> list = new ArrayList<>();
        for (Interval interval : intervals) {
            list.add(new int[]{interval.start, 1});
            list.add(new int[]{interval.end, -1});
        }
        Collections.sort(list, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1]; // end happens before start
            return a[0] - b[0];
        });
        int count = 0;
        int result = 0;
        for (int i = 0; i < list.size(); i++) {
            count += list.get(i)[1];
            result = Math.max(result, count);
        }
        return result;
    }
}


Version #2
sort start & end separately
用count表示现在有的meeting rooms的数量
如果有meeting结束 可以把后面的放进vacant的room
如果没有结束的meeting 就需要增加rooms的数量
81.05 %
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        int length = intervals.length;
        int[] starts = new int[length];
        int[] ends = new int[length];
        for (int i  = 0; i < length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int count = 0;
        int pEnd = 0;
        for (int pStart = 0; pStart < length; pStart++) {
            if (starts[pStart] < ends[pEnd]) {
                count++;
            } else {
                pEnd++;
            }
        }
        return count;
    }
}

Version #1 Naive Sort Intervals Version
重点是breaking tie
看到discuss里面还有用heap和分别sort start&end的方法，懒得看了

49.06 %
class Solution {
    class Tuple implements Comparable<Tuple> {
        int time;
        int isStart; //start -> 1, end -> 0
        public Tuple(int time, int isStart) {
            this.time = time;
            this.isStart = isStart;
        }
        @Override
        public int compareTo(Tuple that) {
            if (this.time != that.time) {
                return this.time - that.time;
            } else {
                return this.isStart - that.isStart;
            }
        }
    }
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        List<Tuple> times = new ArrayList<>();
        for (Interval i : intervals) {
            times.add(new Tuple(i.start, 1));
            times.add(new Tuple(i.end, 0));
        }
        Collections.sort(times);
        int max = 0;
        int count = 0;
        for (Tuple tuple : times) {
            if (tuple.isStart == 1) {
                count++;
                max = Math.max(count, max);
            } else {
                count--;
            }
        }
        return max;
    }
}

416. Partition Equal Subset Sum

二刷 07/2022

Version #1 0/1 Knapsack

Time O(N * Sum)

Space O(N * Sum)

Runtime: 26 ms, faster than 91.77% of Java online submissions for Partition Equal Subset Sum.

Memory Usage: 43.5 MB, less than 75.86% of Java online submissions for Partition Equal Subset Sum.

class Solution {

    public boolean canPartition(int[] nums) {

        int target = 0;

        for (int num : nums) {

            target += num;

        }

        if (target % 2 != 0) {

            return false;

        }

        target /= 2;

        // dp[i][s] - [0, i) numbers can add up to s

        boolean[][] dp = new boolean[nums.length + 1][target + 1];

        dp[0][0] = true;

        for (int i = 1; i <= nums.length; i++) {

            for (int j = target; j >= 0; j--) {

                if (dp[i - 1][j] || (j >= nums[i - 1] && dp[i - 1][j - nums[i - 1]])) {

                    dp[i][j] = true;

                }

            }

            if (dp[i][target]) {

                return true;

            }

        }

        return dp[nums.length][target];

    }

}

Version #2 HashSet

Time O(N * Sum of all numbers)

Space O(Sum of all numbers)

Runtime: 410 ms, faster than 5.82% of Java online submissions for Partition Equal Subset Sum.

Memory Usage: 117.8 MB, less than 6.46% of Java online submissions for Partition Equal Subset Sum.

class Solution {

    public boolean canPartition(int[] nums) {

        int target = 0;

        for (int num : nums) {

            target += num;

        }

        if (target % 2 != 0) {

            return false;

        }

        target /= 2;

        Set<Integer> visited = new HashSet<>();

        visited.add(0);

        for (int num : nums) {

            Set<Integer> newSum = new HashSet<>();

            for (int prev : visited) {

                if (prev + num == target) {

                    return true;

                }

                newSum.add(prev + num);

            }

            visited.addAll(newSum);

        }

        return false;

    }

}

一刷 06/2022

Version #1 0/1 Knapsack DP

It could be optimized to 1d DP

Time O(N*Sum)

Space O(N*Sum)

Runtime: 51 ms, faster than 61.41% of Java online submissions for Partition Equal Subset Sum.

Memory Usage: 54.3 MB, less than 44.88% of Java online submissions for Partition Equal Subset Sum.

class Solution {

    public boolean canPartition(int[] nums) {

        int sum = 0;

        for (int num : nums) {

            sum += num;

        }

        if (sum % 2 != 0) {

            return false;

        }

        sum /= 2;

        // System.out.printf("sum=%d\n", sum);

        // The [0, i) numbers can sum up to j

        boolean[][] dp = new boolean[nums.length + 1][sum + 1];

        // The first 0 number can sum up to 0

        dp[0][0] = true;

        for (int i = 1; i <= nums.length; i++) {

            // the nums[i - 1] item

            int num = nums[i - 1];

            for (int j = 0; j < sum + 1; j++) {

                if (num <= j) {

                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num];

                } else {

                    dp[i][j] = dp[i - 1][j];

                }

            }

            if (dp[i][sum]) {

                return true;

            }

        }

        return dp[nums.length][sum];

    }

}

297. Serialize and Deserialize Binary Tree

参考 449. Serialize and Deserialize BST
Version #5 Byte Manipulation
这个方法是把Integer直接变成string给改成byte 表示法，可以压缩space
String ->
-2^31 =  -2147483648 -> 11 chars
https://www.javamex.com/tutorials/memory/string_memory_usage.shtml
Byte -> 0xFFFFFFFF
4 bytes
No string-integer conversion needed

如果是 int -> byte[] -> char[] 的话，转换回来的时候
如果不
// return (int) ((data[0] & 0xff) << 24)
        //     | ((data[1] & 0xff) << 16)
        //     | ((data[2] & 0xff) << 8)
        //     | (data[3] & 0xff);
就会出错

然而如果直接 int -> char[]就不需要考虑这个问题，因为在int -> char[] 的时候已经
 (char)((x >> 24) & 0xff),
            (char)((x >> 16) & 0xff),
            (char)((x >> 8) & 0xff),
            (char)(x & 0xff)
了


99.15 %

public class Codec {
    private char NULL_VALUE = '0';
    private char NOT_NULL_VALUE = '1';
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        seHelper(root, sb);
        return sb.toString();
    }
 
    private void seHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL_VALUE);
            return;
        }
        char[] array = int2Bytes(node.val);
        sb.append(NOT_NULL_VALUE).append(array[0]).append(array[1]).append(array[2]).append(array[3]);
        seHelper(node.left, sb);
        seHelper(node.right, sb);
    }
 
    private char[] int2Bytes(int x) {
        return new char[]{
            (char)((x >> 24) & 0xff),
            (char)((x >> 16) & 0xff),
            (char)((x >> 8) & 0xff),
            (char)(x & 0xff)
        };
    }

    // Decodes your encoded data to tree.
    private int index;
    public TreeNode deserialize(String data) {
        index = 0;
        return deHelper(data.toCharArray());
    }
 
    private TreeNode deHelper(char[] data) {
        if (data[index++] == NULL_VALUE) {
            return null;
        }
        TreeNode node = new TreeNode(bytes2Int(new char[]{
            data[index],
            data[index + 1],
            data[index + 2],
            data[index + 3]
        }));
        index += 4;
        node.left = deHelper(data);
        node.right = deHelper(data);
        return node;
    }
    private int bytes2Int(char[] data) {
        return (int) (data[0] << 24)
            | (data[1] << 16)
            | (data[2] << 8)
            | data[3];
    }
}



Version #3 Iteration with Stack
二刷
看一刷的不知道自己在写什么。。。为什么需要一个boolean来判断是不是left？
Stack 加的时候注意是先左后右
Stack deserialize的时候，都是向左走到底，然后向右跳一个
39.88 %
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> stack = new LinkedList<>();
        stack.addFirst(root);
        while (!stack.isEmpty()) {
            TreeNode curr = stack.removeFirst();
            if (curr == null) {
                sb.append("#,");
            } else {
                sb.append(curr.val + ",");
                stack.addFirst(curr.right);
                stack.addFirst(curr.left);
            }
        }
        System.out.println(sb.toString());
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] strs = data.split(",");
        Deque<TreeNode> stack = new LinkedList<>();
        int pointer = 0;
        if (strs.length == 0 || strs[pointer].equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
        TreeNode curr = root;
        stack.addFirst(root);
        pointer++;
        while (pointer < strs.length) {
            while (curr != null) {
                stack.addFirst(curr);
                curr.left = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
                pointer++;
                curr = curr.left;
            }
            curr = stack.removeFirst();
            curr.right = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
            pointer++;
            curr = curr.right;
        }
        return root;
    }
}

一刷
Iteration desirialization 好难啊，写了好久好久好久
stack里面放的是已经连完左节点但是等待右subtree的点
curr代表的是当下等待连左节点的点

如果遇到null
1st -> 证明当前curr的left subtree是null
          当前curr已经是Left most node
          开始往外pop
2nd -> 在pop round，pop出的点是waiting for its right subtree
           此时遇到null 证明当前点的right subtree是NULL
           直接继续pop

37.48 %
public class Codec {
    private static final String DIVIDER = "/";
    private static final String NULL = "null";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return null;
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                sb.append(curr.val);
                sb.append(DIVIDER);
                stack.push(curr);
                curr = curr.left;
            } else {
                sb.append(NULL + DIVIDER);
                curr = stack.pop();
                curr = curr.right;
            }
   
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) return null;
        String[] strs = data.trim().split(DIVIDER);
        int index = 0;
        TreeNode root = new TreeNode(Integer.valueOf(strs[index++]));
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        stack.push(curr);
        int n = strs.length;
        // Nodes in stack -> waiting for their right subtree
        // curr -> waiting for its left subtree
        while (index < n) {
            while (index < n && !strs[index].equals(NULL)) {
                curr.left = new TreeNode(Integer.valueOf(strs[index++]));
                curr = curr.left;
                stack.push(curr);
            }
            // Top nodes left subtree is null, get the next candidate node
            while (index < n && strs[index].equals(NULL)) {
                curr = stack.pop();
                index++;
            }
            // strs[index] is not NULL
            if (index < n) {
                curr.right = new TreeNode(Integer.valueOf(strs[index++]));
                curr = curr.right;
                stack.push(curr);
            }
        }
        return root;
    }
}

Version #4 Recursion DFS
Pre-Order Traversal
注意pointer是一个global变量，每一次recursion的当前层负责给pointer + 1
二刷
94.28 %
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        seHelper(root, sb);
        return sb.toString();
    }
    private void seHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val + ",");
        seHelper(node.left, sb);
        seHelper(node.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] strs = data.split(",");
        int[] pointer = new int[]{0};
        return deHelper(strs, pointer);
    }
    private TreeNode deHelper(String[] strs, int[] pointer) {
        if (strs[pointer[0]].equals("#")) {
            pointer[0]++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(strs[pointer[0]]));
        pointer[0]++;
        node.left = deHelper(strs, pointer);
        node.right = deHelper(strs, pointer);
        return node;
    }
}


Version #1 jiuzhang Version BFS with Queue
二刷
49.87 %
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return null;
        }
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode curr = que.poll();
            if (curr == null) {
                sb.append("#,");
            } else {
                sb.append(curr.val + ",");
                que.offer(curr.left);
                que.offer(curr.right);
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] strs = data.split(",");
        Queue<TreeNode> que = new LinkedList<>();
        if (strs.length == 0) {
            return null;
        }
        int pointer = 0;
        TreeNode root = new TreeNode(Integer.valueOf(strs[pointer++]));
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode curr = que.poll();
            TreeNode left = null;
            if (!strs[pointer].equals("#")) {
                left = new TreeNode(Integer.valueOf(strs[pointer]));
                que.offer(left);
            }
            pointer++;
            curr.left = left;
       
            TreeNode right = null;
            if (!strs[pointer].equals("#")) {
                right = new TreeNode(Integer.valueOf(strs[pointer]));     
                que.offer(right);
            }
            pointer++;
            curr.right = right;
        }
        return root;
    }
}
一刷
49.35 %
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "{}";
        ArrayList<TreeNode> que = new ArrayList<>();
        que.add(root);
        TreeNode curr = null;
        for (int i = 0; i < que.size(); i++) {
            curr = que.get(i);
            if (curr == null) continue;
            que.add(curr.left);
            que.add(curr.right);
        }
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        curr = que.get(0);
        int index = 1;
        sb.append(String.valueOf(curr.val));
        while (index < que.size()) {
            curr = que.get(index);
            index++;
            sb.append(",");
            if (curr == null) sb.append("#");
            else sb.append(String.valueOf(curr.val));
        }
        sb.append("}");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("{}")) {
            return null;
        }
        String[] vals = data.substring(1, data.length() - 1).split(",");
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        queue.add(root);
        int index = 0;
        boolean isLeftChild = true;
        for (int i = 1; i < vals.length; i++) {
            if (!vals[i].equals("#")) {
                TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
                if (isLeftChild) {
                    queue.get(index).left = node;
                } else {
                    queue.get(index).right = node;
                }
                queue.add(node);
            }
            if (!isLeftChild) {
                index++;
            }
            isLeftChild = !isLeftChild;
        }
        return root;

    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Version #2

 57.60 %
自己改进了一下感觉比上个方法简洁一点 就是传统地用queue
上个方法里面用ArrayList作为Queue然后用get(index) 来代替queue.poll()感觉也挺有意思的
注意！string == "#"是不对的 必须string.equals("#");
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        TreeNode curr = null;
        while (!que.isEmpty()) {
            curr = que.poll();
            if (curr == null) {
                sb.append("#,");
                continue;
            } else {
                sb.append(String.valueOf(curr.val));
                sb.append(",");
            }
            que.add(curr.left);
            que.add(curr.right);
        }
        char c = sb.charAt(sb.length() - 1);
        do {
            sb.deleteCharAt(sb.length() - 1);
            c = sb.charAt(sb.length() - 1);
        } while (c == '#' || c == ',');

        //System.out.println(sb.toString());
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") return null;
        String[] vals = data.split(",");
        Queue<TreeNode> que = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
        que.add(root);
        TreeNode curr = null;
        boolean isLeft = true;
        for (int index = 1; index < vals.length; index++) {
            if (vals[index].equals("#")) {
                curr = null;
            } else {
                curr = new TreeNode(Integer.valueOf(vals[index]));
                que.add(curr);
            }
            if (isLeft) {
                que.peek().left = curr;
            } else {
                que.poll().right = curr;
            }
            isLeft = !isLeft;
        }
        return root;
    }
}

373. Find K Pairs with Smallest Sums

Version #1 MinHeap with Lambda

41.23 %
class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> result = new ArrayList<>();
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) return result;
        // minHeap -> always poll out the minimum sum and add its adjacent sums
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(10, (pairA, pairB) ->
                                                           (nums1[pairA[0]] + nums2[pairA[1]]) - (nums1[pairB[0]] + nums2[pairB[1]]));
        minHeap.offer(new int[]{0, 0});
        while (k-- > 0 && !minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int i1 = curr[0];
            int i2 = curr[1];
            result.add(new int[]{nums1[i1], nums2[i2]});
            if (i1 == 0 && (i2 + 1 < nums2.length)) minHeap.offer(new int[]{i1, i2 + 1});
            if (i1 + 1 < nums1.length) minHeap.offer(new int[]{i1 + 1, i2});
        }
     
        return result;
    }
}

Version #2 Self-defined  class -> Tuple with is own compareTo method
LC上看到的，拿过来做reference
如果lambda写不好可以参考这个方法
92.17 %

"public class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>(); int m = nums1.length, n = nums2.length; List<int[]> res = new ArrayList<int[]>(); if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res; for(int j = 0; j <= n-1; j++) pq.offer(new Tuple(0, j, nums1[0]+nums2[j])); for(int i = 0; i < Math.min(k, m *n); i++) { Tuple t = pq.poll(); res.add(new int[]{nums1[t.x], nums2[t.y]}); if(t.x == m - 1) continue; pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y])); } return res; } } class Tuple implements Comparable<Tuple> { int x, y, val; public Tuple (int x, int y, int val) { this.x = x; this.y = y; this.val = val; } @Override public int compareTo (Tuple that) { return this.val - that.val; } }"

652. Find Duplicate Subtrees

Version #2
基本思路还是差不多，比Version#1好一些
map.getOrDefault(curr, 0) 这个method 用着很不错哎 Mark一下

 53.39 %
HashMap key-> String, value -> count of Nodes with same string
If and only if count == 2, we add current node into result list
if (count == 1) duplicate hasn't been found yet
if (count > 2) this result has already added into the result list

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        if (root == null) return result;
        Map<String, Integer> map = new HashMap<>();
        dfsHelper(root, map, result);
        return result;
    }
    private String dfsHelper(TreeNode root, Map<String, Integer> map, List<TreeNode> result) {
        if (root == null) return "#";
        String curr = root.val + "/" + dfsHelper(root.left, map, result) + "/" + dfsHelper(root.right, map, result);
        if (map.getOrDefault(curr, 0) == 1) result.add(root);
        map.put(curr, map.getOrDefault(curr, 0) + 1);
        return curr;
    }
}


Version #1
HashMap 的key是String，value是TreeNode
因为一组相同的subTree只记录其中一个，所以用一个HashSet记录看到过的subTree Root
看了Version#2 的答案感觉不如Version#2写的好
29.41 %
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        // key-serialized string of subtree, value-the node
        if (root == null) return new ArrayList<TreeNode>();
        Map<String, TreeNode> map = new HashMap<>();
        Set<TreeNode> set = new HashSet<>();
        // TODO
        dfsHelper(root, map, set);
        return new ArrayList<TreeNode>(set);
    }
    private String dfsHelper(TreeNode root, Map<String, TreeNode> map, Set<TreeNode> set) {
        if (root == null) {
            return "#";
        }
        String curr = root.val + "/" + dfsHelper(root.left, map, set) + "/" + dfsHelper(root.right, map, set);
        if (map.containsKey(curr)) {
            set.add(map.get(curr));
        } else {
            map.put(curr, root);
        }
        return curr;
    }
}

595. Big Countries

87.60 %
SELECT World.name, World.population, World.area
FROM World
WHERE World.area > 3000000
OR World.population > 25000000

414. Third Maximum Number

default minHeap

If we need a maxHeap, we can write

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());

Version #1 Priority Queue
18.80 %
class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) throw new IllegalArgumentException();
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        Set<Integer> visited = new HashSet<>();
        int max = nums[0];
        for (int num : nums) {
            if (visited.contains(num)) continue;
            max = Math.max(num, max);
            if (minHeap.size() < 3) {
                minHeap.offer(num);
            } else {
                if (num >= minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(num);
                }
            }
            visited.add(num);
        }
        return minHeap.size() == 3 ? minHeap.peek() : max;
    }
}

Version #2 Direct Compare
以为很简单，其实爆炸难写
难点主要是duplicate和不够3个distinct Integers的处理

一开始我把三个值都设成num[0], 发现错的离谱，比如[3, 2, 1] 如果一开始都是3的话，后面就没法Update了
所以一开始都设成null
然后又有问题，譬如second是null，不能无脑把second设成当前值，因为有可能当前的值等于first，就会有duplicate
这里面具体的逻辑还是没搞清，看到答案写先和三个值比一下，如果相等就continue，觉得很有道理
但是自己写的时候 nums[i] == first 这种写法是会报NulPointerException的
所以应该写成！！ Integer n : nums ....    n.equals(first)
可以说非常考基本功了
33.14 %

class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0) throw new IllegalArgumentException();
        Integer first = null;
        Integer second = null;
        Integer third = null;
        //case1     case2    case3     case4
        //       1        2        3
        for (Integer n : nums) {
            // if nums[i] == 1st/2nd/3rd, we do nothing
            if (n.equals(first) || n.equals(second) || n.equals(third)) continue;
            if (first == null || n > first) {
                third = second;
                second = first;
                first = n;
            } else if (second == null || n > second) {
                third = second;
                second = n;
            } else if (third == null || n > third) {
                third = n;
            }
        }
        return third == null ? first : third;
    }
}