(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 的值作为切分点是不对的。

但是排序 + 遍历依然可以做，代码如下：

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;
    }
}

正确的做法是从 N 到 0 递减遍历一遍，才能保证得到的 h-index 是最大的，但是我们需要在扫描过程中知道对于每一个切分点 val 来讲，到底有多少个 >= val 的 paper.

换句话说，这是一种类似 “后缀和” 的计数算法，先记录所有可能的切分点；如果一个 paper 的引用次数大于 N ，则直接记录在 count[n] 上，代表 “我不管到底是什么，反正大于 N 了”，其他位置各自计算。然后从后向前扫，依次记录后缀和即可。

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;
        int[] counts = new int[n + 1];
        for(int i = 0; i < n; i++){
            if(citations[i] > n) counts[n]++;
            else counts[citations[i]]++;
        }

        int biggerCount = 0;
        for(int index = n; index >= 0; index--){
            biggerCount += counts[index];
            if(biggerCount >= index) return index;
        }

        return 0;
    }
}

H-Index II

试着用 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;

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0) return 0;

        int N = citations.length;
        int left = 0;
        int right = N;

        while(left < right){
            int mid = left + (right - left) / 2;

            if(citations[mid] == N - mid){
                return N - mid;
            } else if(citations[mid] < N - mid){
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return N - left;
    }
}