LC1 Two Sum

Problem

Given a string, find the length of the longest substring without repeating characters.

Example 1:

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Think

将数组改造成hashtable，然后遍历数组，找hashtable中是否有target - nums[i]

Code 
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for(int i = 0; i < nums.size(); i++){
        map[nums[i]] = i;
    }
    for(int i = 0; i < nums.size(); i++){
        if(map.count(nums[i]) && map[target - nums[i]] > i){
            return {i, map[target - nums[i]]};
        }
    }
    return {-1, -1};
}

LC30 Substring with Concatenation of All Words

Problem

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

1
2
3
4
5
6
Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

1
2
3
4
Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []
Think

首先将所有的words存在hash table中，计算所查找的子串的长度以及每个单词的长度和数量。

遍历开头长度为wordSize的子字符串，即第一个可能的起始节点在[0, wordSize - 1]中，设cnt为需要的word的数目。

然后遍历所有的word，如果word在map中存在，则对应的值-1，cnt - 1；如果此时j大于总共所需长度len = n * wordSize，则去找这个对应最开头的那一个长度为wordSize的子串，相当于滑动窗口的左端向右滑动了一位，使map中对应word+1， cnt+1；最后判断此时cnt是否等于0，如果等于0则说明找到一个满足条件的位置，

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> findSubstring(string s, vector<string>& words) {
    if(words.empty()) return {};
    vector<int> res;
    int n = words.size();
    int wordSize = words[0].size();
    int len = n * wordSize;
    if(len > s.size()) return {};
    unordered_map<string, int> map;
    for(auto word: words){
        map[word]++;
    }
    int cnt = n;
    for(int i = 0; i < wordSize; i++){
        unordered_map<string, int> cur = map;
        cnt = n;
        for(int j = i; j + wordSize <= s.size(); j += wordSize){
            string word = s.substr(j, wordSize);
            if(cur[word]-- > 0) cnt--;
            if(j - len >= 0){
                string out = s.substr(j - len, wordSize);
                if(++cur[out] > 0) cnt++;
            }
            if(cnt == 0) res.push_back(j - len + wordSize);
        }
    }
    return res;
}

LC36 Valid Sudoku

Problem

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

img
A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.
Think

直接判断每行每列和每个3x3矩阵即可

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
bool isValidSudoku(vector<vector<char>>& board) {
    bool flag = true;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            flag = flag && isValidSub(board, i, j);
            if(!flag) return flag;
        }
    }
    
    for(int i = 0; i < 9; i++){
        flag = flag && isValidCol(board, i);
        if(!flag) return flag;
    }

    for(int i = 0; i < 9; i++){
        flag = flag && isValidRow(board, i);
        if(!flag) return flag;
    }

    return flag;
}
bool isValidSub(vector<vector<char>>& board, int m, int n){
    int map[9] = {0};
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            char c = board[i + m * 3][j + n * 3];
            if(isdigit(c)){
                int cur = c - '1';
                if(map[cur] == 0) map[cur]++;
                else{
                    return false;
                }
            }
        }
    }
    return true;
}

bool isValidCol(vector<vector<char>>& board, int m){
    int map[9] = {0};
    for(int i = 0; i < 9; i++){
        char c = board[i][m];
        if(isdigit(c)){
            int cur = c - '1';
            if(map[cur] == 0) map[cur]++;
            else{
                return false;
            }
        }
    }
    return true;
}

bool isValidRow(vector<vector<char>>& board, int m){
    int map[9] = {0};
    for(int i = 0; i < 9; i++){
        char c = board[m][i];
        if(isdigit(c)){
            int cur = c - '1';
            if(map[cur] == 0) map[cur]++;
            else{
                return false;
            }
        }
    }
    return true;
}

LC37 Sudoku Solver

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

img
A sudoku puzzle…

img
…and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.
Think

回溯递归，判断当前填写是否合法

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void solveSudoku(vector<vector<char>>& board) {
    helper(board, 0, 0);
}
bool helper(vector<vector<char>>& board, int m, int n){
    if(m == 9) return true;
    if(n == 9) return helper(board, m + 1, 0);
    if(board[m][n] != '.') return helper(board, m, n + 1);
    for(char c = '1'; c <= '9'; c++){
        if(isValid(board, m, n, c)){
            board[m][n] = c;
            if(helper(board, m, n + 1)) return true;
            board[m][n] = '.';
        }
    }
    return false;
}
bool isValid(vector<vector<char>>& board, int m, int n, char val){
    for(int i = 0; i < 9; i++){
        if(board[m][i] == val) return false;
    }

    for(int i = 0; i < 9; i++){
        if(board[i][n] == val) return false;
    }

    int row = m - m % 3, col = n - n % 3;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if(board[row + i][col + j] == val) return false;
        }
    }

    return true;
}

LC76 Minimum Window Substring

Problem

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Think

hash table + 滑动窗口

首先将t中所有的字母都存在hash table中，然后预处理字符串s，删去其中所有的不存在于t中的字符，转化为包含下标和字符的数组；

设置滑动窗口为[l, r]，判断r处的字符是否在t中，且是否有剩余的容量，如果恰好容量到达t中该字符的数目，则已匹配好的字符数目formed ++；然后对左端的l进行右移处理：如果formed == required，则可以右移l，并将当前的[l, r]存进结果中，然后将l处的字符的数目恢复即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
string minWindow(string s, string t) {
    unordered_map<char, int> m;
    for(auto c: t){
        m[c]++;
    }
    int required = m.size();
    vector<pair<int, char>> filteredS;
    for(int i = 0; i < s.size(); i++){
        char c = s[i];
        if(m.count(c)){
            filteredS.push_back({i, c});
        }
    }
    int l = 0, r = 0, formed = 0;
    unordered_map<char, int> wordCnt;
    int ans[] = {-1, 0, 0};

    while(r < filteredS.size()){
        char c = filteredS[r].second;
        wordCnt[c]++;
        if(m.count(c) && m[c] == wordCnt[c]){
            formed++;
        }
        while(l <= r && required == formed){
            c = filteredS[l].second;
            int start = filteredS[l].first;
            int end = filteredS[r].first;
            if (ans[0] == -1 || end - start + 1 < ans[0]) {
                ans[0] = end - start + 1;
                ans[1] = start;
                ans[2] = end;
            }
            wordCnt[c]--;
            if(m.count(c) && wordCnt[c] < m[c]) formed--;
            l++;
        }
        r++;
    }
    return ans[0] == -1 ? "" : s.substr(ans[1], ans[2] - ans[1] + 1);
}

LC138 Copy List with Random Pointer

Problem

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

img

1
2
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

img

1
2
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

img

1
2
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

1
2
3
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

  • -10000 <= Node.val <= 10000
  • Node.random is null or pointing to a node in the linked list.
  • Number of Nodes will not exceed 1000.
Think
  • Approach 1

递归+hash table

  • Approach 2

三次遍历，第一次复制节点，插在当前节点之后；第二次赋值random指针；第三次断开链接，注意要恢复原来的链表。

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> m;
    return helper(head, m);
}
Node* helper(Node* cur, unordered_map<Node*, Node*>& m){
    if(!cur) return NULL;
    if(m.count(cur)) return m[cur];
    Node* node = new Node(cur->val);
    m[cur] = node;
    node->next = helper(cur->next, m);
    node->random = helper(cur->random, m);
    return node;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Node* copyRandomList(Node* head) {
    if (!head) return NULL;
    Node *cur = head;
    while (cur) {
        Node *t = new Node(cur->val);
        t->next = cur->next;
        cur->next = t;
        cur = t->next;
    }
    cur = head;
    while (cur) {
        if (cur->random) cur->next->random = cur->random->next;
        cur = cur->next->next;
    }
    cur = head;
    Node *res = head->next;
    while (cur) {
        Node *t = cur->next;
        cur->next = t->next;
        if (t->next) t->next = t->next->next;
        cur = cur->next;
    }
    return res;
}

LC149 Max Points on a Line

Problem

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

1
2
3
4
5
6
7
8
9
10
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
|        o
|     o
|  o  
+------------->
0  1  2  3  4

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
|  o
|     o        o
|        o
|  o        o
+------------------->
0  1  2  3  4  5  6

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Think

分三部分，首先确定一个点，然后判断和这个点在一条直线上的点的数目（未遍历过的点），其中分解为对于每一个点，都将这个点和初始选择的点构成的直线加入到map中，注意此处需要判断重复点和水平线（或者竖直线）的情况。

p.s.由于double可能存在精度不够的情况，这里采用pair<dx, dy>作为map的key，因此需要先进行化简，即先求最小公约数。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
vector<vector<int>> points;
pair<int, int> addLine(int i, int j, int count, int duplicate, map<pair<int, int>, int>& lines, int& horizontal){
    int x1 = points[i][0], x2 = points[j][0];
    int y1 = points[i][1], y2 = points[j][1];
    if(x1 == x2 && y1 == y2){
        duplicate++;
    }
    else if(y1 == y2){
        horizontal++;
        count = max(horizontal, count);
    }
    else{
        int dx = x1 - x2, dy = y1 - y2;
        int g = gcd(dx, dy);
        dx = dx / g;
        dy = dy / g;
        pair<int, int> p = {dx, dy};
        if(!lines.count(p)) lines[p] = 1;
        lines[p]++;
        count = max(count, lines[p]);
    }
    return {count, duplicate};
}
int maxPointsThroughI(int i){
    map<pair<int, int>, int> lines;
    int horizontal = 1;
    int count = 1;
    int duplicate = 0;
    for(int j = i + 1; j < points.size(); j++){
        auto p = addLine(i, j, count, duplicate, lines, horizontal);
        count = p.first;
        duplicate = p.second;
    }
    return count + duplicate;
}
int gcd(int x, int y){
    if(y == 0) return x;
    else return gcd(y, x % y);
}
int maxPoints(vector<vector<int>>& points) {
    this->points = points;
    int n = points.size();
    if(n < 3) return n;
    int res = 1;
    for(int i = 0; i < n; i++){
        res = max(res, maxPointsThroughI(i));
    }
    return res;
}

LC166 Fraction to Recurring Decimal

Problem

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

1
2
Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

1
2
Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

1
2
Input: numerator = 2, denominator = 3
Output: "0.(6)"
Think

首先判断结果的正负，然后将除数和被除数都转变为long型的正数，求出整数部分和余数remainder。

如果remainder = 0，说明为整数，直接返回即可；

如果remainder不为0，则建立一个hash table，存放每一个remainder对应在res的什么位置；当remainder不等于0时循环：如果此时hash table中存在当前remainder，说明之前遇到过这个remainder，也就是产生了循环，因此直接去hash table中找上一次遇到这个remainder的开始的位置，在那个地方插入左括号，res最右端插入右括号，返回即可；否则，记录当前remainder的位置，remainder乘10，然后将这一位的结果存入res，remainder变成这一位除完的余数。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string fractionToDecimal(int numerator, int denominator) {
    if(numerator == 0) return "0";
    string res = "";
    if(numerator < 0 ^ denominator < 0) res += "-";
    long dividend = abs(numerator);
    long divisor = abs(denominator);
    res += to_string(dividend / divisor);
    long reminder = dividend % divisor;
    if(reminder == 0) return res;
    res += ".";
    unordered_map<long, int> m;
    while(reminder != 0){
        if(m.count(reminder)){
            res.insert(res.begin() + m[reminder], '(');
            res += ")";
            break;
        }
        m[reminder] = res.size();
        reminder *= 10;
        res += to_string(reminder / divisor);
        reminder = reminder % divisor;
    }
    return res;
}

LC187 Repeated DNA Sequences

Problem

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: “ACGAATTCCG”. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example:

1
2
3
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]
Think

滑动窗口+hash table，注意substr的复杂度为O(L)，其中L为截取的长度。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<string> findRepeatedDnaSequences(string s) {
    int n = s.size();
    unordered_set<string> strSet;
    set<string> res;
    string str = s.substr(0, 10);
    strSet.insert(str);
    for(int i = 1; i <= n - 10; i++){
        str.erase(str.begin());
        str += s[i + 9];
        if(strSet.count(str)) res.insert(str);
        else strSet.insert(str);
    }
    vector<string> ans(res.begin(), res.end());
    return ans;
}

LC204 Count Primes

Problem

Count the number of prime numbers less than a non-negative number, *n*.

Example:

1
2
3
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Think

设定一个长度为n的数组，每一位表示当前下标对应的数字处是否为质数。遍历数组，如果当前数字为质数，则将所有它的倍数都置为true。统计这个数组中false的数目即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int countPrimes(int n) {
    if(n <= 2) return 0;
    vector<bool> passed(n, false);
    int sum = 1;
    int upper = sqrt(n);
    for(int i = 3; i < n; i += 2){
        if(!passed[i]){
            sum++;
            if(i > upper) continue;
            for(int j = i * i; j < n; j += i){
                passed[j] = true;
            }
        }
    }
    return sum;
}

LC205 Isomorphic Strings

Problem

Given two strings *s* and *t*, determine if they are isomorphic.

Two strings are isomorphic if the characters in *s* can be replaced to get *t*.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

1
2
Input: s = "egg", t = "add"
Output: true

Example 2:

1
2
Input: s = "foo", t = "bar"
Output: false

Example 3:

1
2
Input: s = "paper", t = "title"
Output: true

Note:
You may assume both *s* and *t* have the same length.

Think

首先建立数组m1和m2，其包含了s和t里面的每个字符串和下标的对应关系。如果当前字符串s在m1中对应的下标和字符串t在m2中对应的下标不一致，则说明这当中某一个字符出现在了别的地方，也就是不满足要求的一一对应的关系，返回false，否则记录当前的字符和下标。

Code 
1
2
3
4
5
6
7
8
9
10
bool isIsomorphic(string s, string t) {
    int n = s.size();
    vector<int> m1(256, -1), m2(256, -1);
    for(int i = 0; i < n; i++){
        if(m1[s[i]] != m2[t[i]]) return false;
        m1[s[i]] = i;
        m2[t[i]] = i;
    }
    return true;
}

LC217 Contains Duplicate

Problem

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

1
2
Input: [1,2,3,1]
Output: true

Example 2:

1
2
Input: [1,2,3,4]
Output: false

Example 3:

1
2
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
Think

hash table

Code 
1
2
3
4
5
6
7
8
bool containsDuplicate(vector<int>& nums) {
    unordered_set<int> s;
    for(auto n: nums){
        if(s.count(n)) return true;
        s.insert(n);
    }
    return false;
}

LC219 Contains Duplicate II

Problem

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Think

Hash table存放当前数字和下标

Code 
1
2
3
4
5
6
7
8
9
10
11
bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> s;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(s.count(nums[i])){
                if(i - s[nums[i]] <= k) return true;
            }
            s[nums[i]] = i;
        }
        return false;
    }

LC242 Valid Anagram

Problem

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Think

Hash table，分别遍历s和t，判断是否还有余量

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isAnagram(string s, string t) {
    if(s.size() != t.size()) return false;
    unordered_map<char, int> m;
    for(auto c: s){
        m[c]++;
    }

    for(auto c: t){
        if(!m.count(c)) return false;
        else{
            m[c]--;
            if(m[c] < 0) return false;
        }
    }
    return true;
}

LC274 H-Index

Problem

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her Npapers have at least h citations each, and the other N − h papers have no more than hcitations each.”

Example:

1
2
3
4
5
6
Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Think

首先对论文进行升序排序，设当前遍历到的论文为i，则每次判断第n - 1 - i篇论文（即第i大的论文）的引用数是否大于i，如果大于，则说明要找的临界点还在后面，i++，否则返回i即可。

Code 
1
2
3
4
5
6
7
int hIndex(vector<int>& citations) {
    sort(citations.begin(), citations.end());
    int n = citations.size();
    int i = 0;
    while(i < n && citations[n - 1 - i] > i) i++;
    return i;
}