7/28, FB, Simplify Path, H-Index I & II

Simplify Path

没啥特别好说的~ 用双端队列比 stack 省事很多。

收尾的时候注意下，如果字符串为空的话，需要留个 "/" 作为默认情况。

public class Solution {
    public String simplifyPath(String path) {
        String[] ops = path.split("/");
        Deque<String> deque = new LinkedList<String>();

        for(String str : ops){
            if(str.equals(".") || str.equals("")) continue;
            if(str.equals("..")) deque.pollFirst();
            else deque.offerFirst(str);
        }

        StringBuilder sb = new StringBuilder();

        while(!deque.isEmpty()){
            String str = deque.pollLast();
            sb.append('/');
            sb.append(str);
        }

        return (sb.length() == 0) ? "/" : sb.toString();
    }
}

H-Index

从图的方式理解的话，h-index 是图中最大正方形的边长。

h-index 的定义是，至少有 h 篇 paper 的 citation 数都大于等于 h.

对于给定 array, h-index 有且只有一个。

因此对于 n 篇 paper 的输入， h-index 的值一定在【0，n】区间。一个需要特别考虑的例子是下面这个：

[0,0,4,4] 的 h-index 是 2.

一开始尝试了下排序然后从右往左扫，然而遇到上面那个 case 就比较麻烦，因为数组给定的 citations 之间间隔可能很大，而这种循环做法只考虑 citation 的值作为切分点是不对的。

这道题比较直观的是O(nlogn)的解法, 对citation从大到小排序后, 从前往后加, 只要citations[i]>i; count++, 最后返回count. 实际上是在下图找正方形.

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0) return 0;
        // Maxium hindex is n, number of papers
        int n = citations.length;
        Arrays.sort(citations);
        int hindex = 0;

        for(int i = n - 1; i >= 0; i--){
            if(citations[i] > hindex) hindex++;
        }

        return hindex;
    }
}

然而这道题还可以有O(n)的解法, 这时就要利用额外空间了. 想法类似于bucket sort, 对n个paper建立n个bucket, 统计每个bucket里的count[i]. 从后往前扫, 扫到第一个位置使得total_count>i时, 返回i+1.

citations = [3, 0, 6, 1, 5] count = [1,0,1,0,2]. 加到count[2]时, total_count=3>i=2, 返回i+1;

    public int hIndex(int[] oldArray) {
        //O(n) solution
        if(oldArray == null || oldArray.length==0) return 0;
        int[] cite = new int[oldArray.length+1];
        for(int value : oldArray){
            if(value>oldArray.length)
                cite[cite.length-1]++;
            else
                cite[value]++;
        }
        int num = 0;
        for(int i=cite.length-1;i>=0;i--){
            num += cite[i];
            System.out.println(num + " " + i);
            if(num>=i)
                return i;
        }
        return 0;

H-Index II

没想到这道题居然有O(logn)的二分.

试着用 left + 1 < right 的 binary search 搞这题，搞了好半天才 AC .. corner case 一大堆。。

之前用 left + 1 < right 是相对于“元素 index” 来讲的，为的是避免越界。这里面既然我们已知最终 h-index 区间 [0, N] 了，可以直接以这两点开始，以 pointer 重合结束。

需要注意的细节是，这里要做 left = mid + 1 ，而不是 right = mid - 1，不然在 [0] 的 testcase 上会 TLE.

同时用 mid + 1 和 mid - 1 会在 [1,2] 的情况下 WA. 所以指针的推动和错位是要根据题意制定的；这题我们唯一能确定的只有两个情况：

c[mid] == N - mid ，当前位置就是完美正方形，一定是解；
c[mid] < N - mid，当前位置的 bar 太低，正解要在右边找，而且一定不会是 mid 的位置，mid + 1;

二分搜索的重点在于最后right pointer的处理, right pointer+1才是target mid的位置. 切记!

    public int hIndex(int[] citations) {
        //O(lgn) complexity
        int len = citations.length;
        int left = 0; int right = citations.length-1; int max = 0;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(citations[mid] == len-mid){
                return len-mid;
            }
            else if(citations[mid]>len-mid){
                right = mid-1;
            }
            else
                left = mid+1;
        }
        return len- (right+1); //key point

FB, Simplify Path, H-Index I & II