H-Index & II

mochixuan 發布于2019-08-14 17:25 / 2987人閱讀

H-Index

題目鏈接：https://leetcode.com/problems...

sort：

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0)  return 0;
        // sort
        Arrays.sort(citations);
        int n = citations.length;
        // find 1st i that citations[i] < i
        // [0, 1, 3, 5, 6]
        for(int i = 0; i < n; i++) {
            if(citations[i] >= n - i) return n - i;
        }
        return 0;
    }
}

calculate suffix sum:

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0)  return 0;
        int n = citations.length;
        int[] count = new int[n + 1];
        for(int i = 0; i < n; i++) {
            if(citations[i] > n) {
                count[n]++;
            }
            else {
                count[citations[i]]++;
            }
        }
        
        // calculate suffix sum
        int sum = 0;
        for(int i = n; i >= 0; i--) {
            sum += count[i];
            if(sum >= i) return i;
        }
        return 0;
    }
}

H-Index II

題目鏈接：https://leetcode.com/problems...

public class Solution {
    public int hIndex(int[] citations) {
        if(citations == null || citations.length == 0)  return 0;
        // binary search, find 1st c[i] >= n - i
        int n = citations.length;
        int l = 0, r = n - 1;
        while(l + 1 < r) {
            int mid = l + (r - l) / 2;
            int val = citations[mid];
            if(val == n - mid) return n - mid;
            else if(val < n - mid) l = mid;
            else r = mid;
        }
        
        if(citations[l] >= n - l) return n - l;
        if(citations[r] >= n - r) return n - r;
        return 0;
    }
}

GPU云服務器云服務器 II quartus ii ii6 ii7

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66621.html

[Leetcode] H-Index H指數

摘要：排序法復雜度時間空間思路先將數組排序，我們就可以知道對于某個引用數，有多少文獻的引用數大于這個數。代碼排序得到當前的指數數組映射法復雜度時間空間思路也可以不對數組排序，我們額外使用一個大小為的數組。 H-Index I Given an array of citations (each citation is a non-negative integer) of a research...

xumenger 2019-08-14 12:35 評論0 收藏0
274. H-Index

摘要：題目解答滿足這個的最大值不會超過數組的因為如果超過了，就不可能有這么多的數。所以就是把所有可能的個至少有個的記下來，然后找出最大的。因為是從后向前掃的，所以當前的就是滿足條件的最大數。題目：Given an array of citations (each citation is a non-negative integer) of a researcher, write a fun...

xiaochao 2019-08-14 14:09 評論0 收藏0
490. The Maze &amp;&amp; 505. The Maze II

摘要：題目鏈接和上一題不一樣的是這道題要求最短的路徑，普通的遍歷和都是可以做的，但是求最短路徑的話還是用。這里相當于每個點有至多條相連，每條的就是到墻之前的長度。 490. The Maze 題目鏈接：https://leetcode.com/problems... 又是圖的遍歷問題，就是簡單的遍歷，所以dfs和bfs都可以做，復雜度也是一樣的。這道題要求球不能停下來，即使碰到destina...

BoYang 2019-08-14 17:27 評論0 收藏0
[LeetCode] Path Sum (I &amp; II &amp; III)

摘要： 112. Path Sum Problem Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node...

張金寶 2019-08-19 11:09 評論0 收藏0
[LintCode/LeetCode] Single Number I &amp; II [位運算]

摘要：整個過程相當于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現過一次的，而出現兩次的都在里，出現三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 評論0 收藏0