# (FB) Simplify Path, H-Index I & II

## [Simplify Path](https://leetcode.com/problems/simplify-path/)

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

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

```java
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](https://leetcode.com/problems/h-index/)

![](/files/-MUt7c2Brut2ZwTvZayG)

## 这题有[官方答案](https://leetcode.com/articles/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 的值作为切分点是不对的。

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

```java
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 了”，其他位置各自计算。然后从后向前扫，依次记录后缀和即可。

```java
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](https://leetcode.com/problems/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;**

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/728-_fb-_simplify_path-_h-index_i_and_ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.