LeetCode(29) -- 697, 700, 703

P697. Degree of an Array (Easy)

非空数组，最大的频度叫做它的degree。找到最小的连续子数组的长度，满足它的degree跟原数组的degree相同。

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

我的思路

把每个数放到hashmap里， 记录它的出现频率，第一次出现的坐标以及最后一次出现的坐标。

我的代码

public class E_697_DegreeOfAnArray {
    public int findShortestSubArray(int[] nums) {
        HashMap<Integer, Integer[]> map = new HashMap<>();
        int degree = 0, ans = Integer.MAX_VALUE;
        List<Integer> degreeElements = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            Integer[] info = new Integer[3];
            if (map.containsKey(nums[i])) {
                info = map.get(nums[i]);
                info[0]++;
                info[2] = i;
            } else {
                info[0] = 1;
                info[1] = i;
            }
            if (info[0] > degree) {
                degree = info[0];
                degreeElements.clear();
                degreeElements.add(nums[i]);
            } else if (info[0] == degree) {
                degreeElements.add(nums[i]);
            }
            map.put(nums[i], info);
        }
        for (Integer degreeElement : degreeElements) {
            Integer[] info = map.get(degreeElement);
            if (info[2] == null) {
                ans = Math.min(ans, 1);
            } else {
                ans = Math.min(ans, info[2] - info[1] + 1);
            }
        }
        return ans;
    }
}

42%

答案

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> left = new HashMap(),
            right = new HashMap(), count = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (left.get(x) == null) left.put(x, i);
            right.put(x, i);
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        int ans = nums.length;
        int degree = Collections.max(count.values());
        for (int x: count.keySet()) {
            if (count.get(x) == degree) {
                ans = Math.min(ans, right.get(x) - left.get(x) + 1);
            }
        }
        return ans;
    }
}

最优解

class Solution {
    public int findShortestSubArray(int[] nums) {
        //bucket sort;
        int max = Integer.MIN_VALUE;
        for(int i : nums) {
            max = Math.max(max, i);
        }
        int[] bucket = new int[max+1];
        int[] firstIndex = new int[max+1];
        int[] lastIndex = new int[max+1];
        int degree = 0;
        for(int i=0; i<nums.length; i++) {
            bucket[nums[i]]++;
            if(bucket[nums[i]] == 1) {
                firstIndex[nums[i]] = i;
                lastIndex[nums[i]] = i;
            }else{
                lastIndex[nums[i]] = i;
            }
            degree = Math.max(degree, bucket[nums[i]]);
        }
        int ret = Integer.MAX_VALUE;
        for(int i=0; i<bucket.length; i++) {
            if(bucket[i] == degree) {
                ret = Math.min(lastIndex[i] - firstIndex[i] + 1, ret);
            }
        }
        return ret;
    }
}

手工HashMap（bucket）

P700. Search in a Binary Search Tree (Easy)

在一个BST中寻找某个值的子节点。

我的思路

BST最基本的遍历。

我的代码

public class E_700_SearchinaBinarySearchTree {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }
}

100%

最优解

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {

        return searchBST1(root, val);

    }
    public TreeNode searchBST1(TreeNode root, int val)
    {
        if(root == null) return null;

        if(root.val == val){
            return root;
        }

        if(val < root.val)
            return searchBST1(root.left, val);
        else
            return searchBST1(root.right, val);

    }
}

P703. Kth Largest Element in a Stream (Easy)

一个流中第k大的数

我的思路

看答案用min heap。

讨论区

class KthLargest {

    private Queue<Integer> pq;
    private int k;

    public KthLargest(int k, int[] nums) {
        pq = new PriorityQueue<>(k);
        this.k = k;
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        pq.add(val);
        if (pq.size() == k + 1) {
            pq.remove();
        }
        return pq.peek();
    }
}

最优解

class KthLargest {

    public int[] nums;
    public int len, k;

    public KthLargest(int k, int[] nums) {
        this.nums = new int[k + 1];
        len = 0;
        this.k = k;
        for (int i = 0; i < nums.length; i++)
            insert(nums[i]);
    }

    public int add(int val) {
        insert(val);
        return nums[0];
    }

    public void insert(int number)
    {
        if (len < k){
            nums[len] = number;
            moveUp(len++);
        }
        else {
            if (nums[0] < number){
                nums[0] = number;
                moveDown(0);
            }
        }

    }

    public void moveUp(int index)
    {
        if (index == 0)
            return;
        int fatherIndex = (index - 1) / 2;
        if (nums[index] < nums[fatherIndex])
        {
            int temp = nums[index];
            nums[index] = nums[fatherIndex];
            nums[fatherIndex] = temp;
            moveUp(fatherIndex);
        }
    }

    public void moveDown(int index)
    {
        if (index * 2 + 2 < len)
        {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;
            if ((nums[leftChild] < nums[index])&&(nums[leftChild] <= nums[rightChild]))
            {
                int temp = nums[index];
                nums[index] = nums[leftChild];
                nums[leftChild] = temp;
                moveDown(leftChild);
            }
            else if ((nums[rightChild] < nums[index])&&(nums[rightChild] <= nums[leftChild]))
            {
                int temp = nums[index];
                nums[index] = nums[rightChild];
                nums[rightChild] = temp;
                moveDown(rightChild);
            }
        }
        else if (index * 2 + 2 == len)
        {
            int leftChild = index * 2 + 1;
            if (nums[leftChild] < nums[index])
            {
                int temp = nums[index];
                nums[index] = nums[leftChild];
                nums[leftChild] = temp;
                moveDown(leftChild);
            }
        }
    }
}