資訊專欄INFORMATION COLUMN
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66621.html
摘要：排序法復(fù)雜度時(shí)間空間思路先將數(shù)組排序，我們就可以知道對(duì)于某個(gè)引用數(shù)，有多少文獻(xiàn)的引用數(shù)大于這個(gè)數(shù)。代碼排序得到當(dāng)前的指數(shù)數(shù)組映射法復(fù)雜度時(shí)間空間思路也可以不對(duì)數(shù)組排序，我們額外使用一個(gè)大小為的數(shù)組。 H-Index I Given an array of citations (each citation is a non-negative integer) of a research...
摘要：題目解答滿足這個(gè)的最大值不會(huì)超過數(shù)組的因?yàn)槿绻^了，就不可能有這么多的數(shù)。所以就是把所有可能的個(gè)至少有個(gè)的記下來，然后找出最大的。因?yàn)槭菑暮笙蚯皰叩模援?dāng)前的就是滿足條件的最大數(shù)。 題目：Given an array of citations (each citation is a non-negative integer) of a researcher, write a fun...
摘要：題目鏈接和上一題不一樣的是這道題要求最短的路徑，普通的遍歷和都是可以做的，但是求最短路徑的話還是用。這里相當(dāng)于每個(gè)點(diǎn)有至多條相連，每條的就是到墻之前的長(zhǎng)度。 490. The Maze 題目鏈接：https://leetcode.com/problems... 又是圖的遍歷問題，就是簡(jiǎn)單的遍歷，所以dfs和bfs都可以做，復(fù)雜度也是一樣的。這道題要求球不能停下來，即使碰到destina...
摘要： 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...
摘要：整個(gè)過程相當(dāng)于，直接在和里去掉既是又是的。所以最后返回的，一定是只出現(xiàn)過一次的，而出現(xiàn)兩次的都在里，出現(xiàn)三次的都被消去了。 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...
閱讀 1642·2023-04-26 02:50
閱讀 3627·2023-04-26 00:28
閱讀 2010·2023-04-25 15:18
閱讀 3279·2021-11-24 10:31
閱讀 1082·2019-08-30 13:00
閱讀 1071·2019-08-29 15:19
閱讀 1834·2019-08-29 13:09
閱讀 3043·2019-08-29 13:06
