LeetCode(94) -- 275, 287, 300, 96

P275. H-Index II (Medium)

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

My Solution

public class P275_H_IndexII {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        int n = citations.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (citations[mid] >= n - mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return citations[l] >= n - l ? n - l : 0;
    }
}

100% 这道题其实是要找出第一个符合条件的“有h个数大于等于h”。如果当前检查的数大于等于右边的个数，说明这个数是符合条件的，所以还要向左找找，看还有没有比它更小的。

The Best Solution

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int lo=0, hi=n-1;
        while (lo <= hi) {
            int m = lo + (hi-lo)/2;
            if (citations[m] == n - m) return n - m;
            if (citations[m] < n - m) lo = m + 1;
            else hi = m - 1;
        }
        return n - lo;
    }
}

P287. Find the Duplicate Number (Medium)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

My Solution

public class P287_FindtheDuplicateNumber {
    public int findDuplicate(int[] nums) {
        boolean[] exist = new boolean[nums.length - 1];
        for (int num : nums) {
            if (exist[num - 1]) {
                return num;
            }
            exist[num - 1] = true;
        }
        return -1;
    }
}

100%

Solution

答案里第一种方法就是排序，然后挨个看有没有重复的。 第二种方法是用set。 第三种方法比较神奇。

class Solution {
    public int findDuplicate(int[] nums) {
        // Find the intersection point of the two runners.
        int tortoise = nums[0];
        int hare = nums[0];
        do {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
        } while (tortoise != hare);

        // Find the "entrance" to the cycle.
        int ptr1 = nums[0];
        int ptr2 = tortoise;
        while (ptr1 != ptr2) {
            ptr1 = nums[ptr1];
            ptr2 = nums[ptr2];
        }
        return ptr1;
    }
}

龟兔赛跑，把当前index的值作为下一个index

P300. Longest Increasing Subsequence (Medium)

Given an unsorted array of integers, find the length of longest increasing subsequence.

Solution

方法一：

public class Solution {
    public int lengthOfLIS (int[] nums) {
        return lengthofLIS(nums, Integer.MIN_VALUE, 0);
    }

    public int lengthofLIS(int[] nums, int prev, int curpos) {
        if (curpos == nums.length){
            return 0;
        }
        int taken = 0;
        if (nums[curpos] > prev) {
            taken = 1 + lengthofLIS(nums, nums[curpos], curpos + 1);
        }
        int nottaken = lengthofLIS(nums, prev, curpos + 1);
        return Math.max(taken, nottaken);
    }
}

方法二:

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int memo[][] = new int[nums.length + 1][nums.length];
        for (int[] l : memo) {
            Arrays.fill(l, -1);
        }
        return lengthofLIS(nums, -1, 0, memo);
    }
    public int lengthofLIS(int[] nums, int previndex, int curpos, int[][] memo) {
        if (curpos == nums.length) {
            return 0;
        }
        if (memo[previndex + 1][curpos] >= 0) {
            return memo[previndex + 1][curpos];
        }
        int taken = 0;
        if (previndex < 0 || nums[curpos] > nums[previndex]) {
            taken = 1 + lengthofLIS(nums, curpos, curpos + 1, memo);
        }

        int nottaken = lengthofLIS(nums, previndex, curpos + 1, memo);
        memo[previndex + 1][curpos] = Math.max(taken, nottaken);
        return memo[previndex + 1][curpos];
    }
}

跟上一个差不多，但用一个二维数组记录下来了。提高性能。

方法三：DP

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}

方法四：Dynamic Programming with Binary Search

public class Solution{
    public int lengthOfLIS(int[] nums){
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

P96. Unique Binary Search Trees (Medium)

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

My Solution

public class P96_UniqueBinarySearchTrees {
    public int numTrees(int n) {
        return numTrees(1, n);
    }

    private int numTrees(int from, int to) {
        if (from > to) {
            return 0;
        }
        if (from == to) {
            return 1;
        }
        int count = 0;
        for (int i = from; i <= to; i++) {
            int left = numTrees(from, i - 1);
            int right = numTrees(i + 1, to);
            if (left == 0) {
                count += right;
            } else if (right == 0) {
                count += left;
            } else {
                count += left * right;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int i = new P96_UniqueBinarySearchTrees().numTrees(3);
        System.out.println("i = " + i);
    }
}

5% 这个我借鉴了95题，实际上应该不需要递归，可能用数学方法就能做出来。

The Best Solution

class Solution {
  public int numTrees(int n) {
    // Note: we should use long here instead of int, otherwise overflow
    long C = 1;
    for (int i = 0; i < n; ++i) {
      C = C * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) C;
  }
}

Catalan number