发表于 | 分类于

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

解法1：

C++

1

Java

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
public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        int start = 0;
        int end = citations.length - 1;
        int n = citations.length;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (citations[mid] >= n - mid) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        if (citations[start] >= n - start) {
            return n - start;
        }
        if (citations[end] >= n - end) {
            return n - end;
        }
        return n - end - 1;
    }
}

发表于 | 分类于

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:
You may assume k is always valid, 1 ? k ? n2.

解法1：Heap

用heap的思想，先把第一排或者第一列放入queue中，然后操作k-1次，每一次拿出一个元素，并且把他下面一行的元素也推入queue中。最后在堆顶的就是所求的答案。
C++

1

Java

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
public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        PriorityQueue<Tuple> queue = new PriorityQueue<>(new Comparator<Tuple>() {
            public int compare(Tuple left, Tuple right) {
                return left.val - right.val;
            }
        });
        int row = matrix.length;
        int col = matrix[0].length;
        for (int j = 0; j < col; j++) {
            queue.offer(new Tuple(0, j, matrix[0][j]));
        }
        for (int count = 0; count < k - 1 ; count++) {
            Tuple temp = queue.poll();
            if (temp.x == row - 1) continue;
            queue.offer(new Tuple(temp.x + 1, temp.y, matrix[temp.x + 1][temp.y]));
        }
        return queue.poll().val;
    }
    class Tuple {
        int x;
        int y;
        int val;
        public Tuple(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    };
}

解法2：Range version of Binary Search, Time Complexity O(NlogM)

先确定最小值和最大值，知道了范围以后。找出中间点，然后统计有多少数小于他的值，如果总数小于k那么知道k个数一定在右半边。以此类推
O(NlogM): N是行数，M是search range = max - min

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
public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int n = matrix.length;
        int low = matrix[0][0];
        int high = matrix[n - 1][n - 1] + 1;   // [low, high)
        while (low < high) {
            int mid = low + (high - low ) / 2;
            int count = 0, j = matrix[0].length - 1; // seach from the end of the column
            for (int i = 0; i < matrix.length; i++) {
                while (j >= 0 && matrix[i][j] > mid) j--;
                count += (j + 1);   // calcualte in this row, how many elements are smaller than mid
            }
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

发表于 | 分类于

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

You may assume the interval’s end point is always bigger than its start point.
You may assume none of these intervals have the same start point.

Example 1:

1
2
3
4
5
Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5
6
7
Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

1
2
3
4
5
6
Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

解法1：

这里遇到了一种binarysearch的用法，题目要求需要返回原始的index，而又有点像binarysearch
可以先用hashmap记录每一个当前的index，再对数组进行排序
排好序之后得到结果了再取map中找寻原始的index。
C++

1

Java

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public int[] findRightInterval(Interval[] intervals) {
        HashMap<Integer, Integer> startMap = new HashMap<Integer, Integer>();
        List<Integer> starts = new ArrayList<Integer>();
        for (int i = 0; i < intervals.length; i++) {
            startMap.put(intervals[i].start, i);
            starts.add(intervals[i].start);
        }        
        Collections.sort(starts);   // sort the array of start
        int[] res = new int[starts.size()];
        for (int i = 0; i < intervals.length; i++) {
            int end = intervals[i].end;
            int temp = binarySearch(starts, end);
            if (temp == -1) {
                res[i] = -1;
            } else {
                res[i] = startMap.get(starts.get(temp));
            }
        }
        return res;        
    }
    private int binarySearch(List<Integer> list, int target) {
        // find first that is larger than end
        int start = 0, end = list.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (list.get(mid) < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (list.get(start) >= target) {
            return start;
        }
        if (list.get(end) >= target) {
            return end;
        }
        return -1;  // didn't find a start that is larger than target
    }
}

发表于 | 分类于

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 N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

For example, given citations = [3, 0, 6, 1, 5], which 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, his h-index is 3.

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

解法1：

要注意h的范围是在[0, N]之间。
只需要用一个array记录每一个数字出现的次数，对于数字大于等于N的记录在N
最后从后往前，累加所有的次数，当count >= i的时候说明就是我们要求的h-index
https://discuss.leetcode.com/topic/40765/java-bucket-sort-o-n-solution-with-detail-explanation/2
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        Arrays.sort(citations);
        int max = 0;
        for (int i = 0; i < citations.length; i++) {
            int curr = Math.min(citations[i], citations.length - i);    // [1,4,5]
            max = Math.max(max, curr);
        }
        return max;
    }
}

解法2： Bucket Sort的思想

目标是找寻一个数i，使得比他引用次数多的paper的数量（包括和他一样的）要比i大就可以。统计每一个citation次数出现的次数，然后从大到小找到第一个满足条件的数字就可以了。

lang: java
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
class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        int n = citations.length;
        int[] buckets = new int[n + 1];
        for (int citation : citations) {
            if (citation >= n) {
                buckets[n]++;
            } else {
                buckets[citation]++;
            }
        }
        // move from back to front
        int count = 0;
        for (int i = n; i >= 0; i--) {
            count += buckets[i];
            if (count >= i) {
                return i;
            }
        }
        return 0;
    }
}

发表于 | 分类于

Given two sparse matrices A and B, return the result of AB.

You may assume that A’s column number is equal to B’s row number.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]
B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]
     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

解法1：

只要存下非0的数即可，然后遍历每一对非0的pair，看是否col=row，然后加和到对应的单元格里。
C++

1

Java

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
public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int row_a = A.length;
        int col_a = A[0].length;
        int row_b = B.length;
        int col_b = B[0].length;
        int[][] res = new int[row_a][col_b];    // store the result
        // res[i][j] = sum (A[i][k] .* B[k][j]) ...
        HashMap<Integer, Integer> a = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> b = new HashMap<Integer, Integer>();
        for (int i = 0; i < row_a; i++) {
            for (int j = 0; j < col_a; j++) {
                if (A[i][j] != 0) {
                    int index = i*col_a + j;
                    a.put(index, A[i][j]);
                }
            }
        }
        for (int i = 0; i < row_b; i++) {
            for (int j = 0; j < col_b; j++) {
                if (B[i][j] != 0) {
                    int index = i*col_b + j;
                    b.put(index, B[i][j]);
                }
            }
        }
        for (int index_a : a.keySet()) {
            for (int index_b : b.keySet()) {
                if (index_a % col_a == index_b / col_b) {
                    res[index_a / col_a][index_b % col_b] += a.get(index_a) * b.get(index_b);
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

An abbreviation of a word follows the form . Below are some examples of word abbreviations:

1
2
3
4
5
6
7
8
9
10
11
12
a) it                      --> it    (no abbreviation)
     1
b) d|o|g                   --> d1g
              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n
              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word’s abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Given dictionary = [ "deer", "door", "cake", "card" ]
isUnique("dear") ->
false
isUnique("cart") ->
true
isUnique("cane") ->
false
isUnique("make") ->
true

解法1：

莫名其妙的一题。。
C++

1

Java

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
public class ValidWordAbbr {
    HashMap<String, Integer> map = null;
    HashMap<String, Integer> countMap = null;
    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        countMap = new HashMap<>();
        for (String str : dictionary) {
            String abbr = getAbbr(str);
            map.put(abbr, map.getOrDefault(abbr, 0) + 1);
            countMap.put(str, countMap.getOrDefault(str, 0) + 1);
        }
    }
    private String getAbbr(String str) {
        if (str.length() <= 2) {
            return str;
        }
        return str.substring(0, 1) + Integer.toString(str.length() - 2) + str.substring(str.length() - 1, str.length());
    }
    public boolean isUnique(String word) {
        String key = getAbbr(word);
        int abbrCount = map.getOrDefault(key, 0);
        int count = countMap.getOrDefault(word, 0);
        return abbrCount <= count;
    }
}
/**
 * Your ValidWordAbbr object will be instantiated and called as such:
 * ValidWordAbbr obj = new ValidWordAbbr(dictionary);
 * boolean param_1 = obj.isUnique(word);
 */

发表于 | 分类于

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N’s left subtree root and right subtree root. And N’s original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Input:
A binary tree as following:
       4
     /   \
    2     6
   / \   /
  3   1 5   
v = 1
d = 2
Output:
       4
      / \
     1   1
    /     \
   2       6
  / \     /
 3   1   5

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Input:
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    
v = 1
d = 3
Output:
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

解法1：

先用bfs找到要加的层的上一层。然后对每一个node加上新的node，然后把原来的left assign给left，rightassign给right
C++

1

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        // do a level order traversal
        if (root == null) {
            if (d == 1) {
                return new TreeNode(v);
            }
            return null;
        }
        int depth = 1;
        if (d == 1) {
            TreeNode root_new = new TreeNode(v);
            root_new.left = root;
            return root_new;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        // do level order traversal until reach the level right before depth
        while (!queue.isEmpty() && depth < d - 1) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.poll();
                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }
            }
            depth++;
        }
        // depth == d - 1
        // queue contains all the nodes that is point to depth
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            TreeNode left = current.left;   // original left
            TreeNode right = current.right; // original right
            TreeNode left_new = new TreeNode(v);    // new left
            TreeNode right_new = new TreeNode(v);
            current.left = left_new;
            current.right = right_new;
            left_new.left = left;
            right_new.right = right;
        }
        return root;        
    }
}

发表于 | 分类于

Given n processes, each process has a unique PID (process id) and its PPID (parent process id).

Each process only has one parent process, but may have one or more children processes. This is just like a tree structure. Only one process has PPID that is 0, which means this process has no parent process. All the PIDs will be distinct positive integers.

We use two list of integers to represent a list of processes, where the first list contains PID for each process and the second list contains the corresponding PPID.

Now given the two lists, and a PID representing a process you want to kill, return a list of PIDs of processes that will be killed in the end. You should assume that when a process is killed, all its children processes will be killed. No order is required for the final answer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
pid =  [1, 3, 10, 5]
ppid = [3, 0, 5, 3]
kill = 5
Output: [5,10]
Explanation:
           3
         /   \
        1     5
             /
            10
Kill 5 will also kill 10.

Note:

The given kill id is guaranteed to be one of the given PIDs.
n >= 1.

解法1：

先把问题条件转化为一个图，然后对图做一个BFS就可以了。
C++

1

Java

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
public class Solution {
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        List<Integer> res = new ArrayList<Integer>();
        if (pid == null || ppid == null) {
            return res;
        }
        if (pid.size() != ppid.size()) {
            return res;
        }
        // Convert to a graph
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < pid.size(); i++) {
            int child  = pid.get(i);
            int parent = ppid.get(i);
            if (!map.containsKey(parent)) {
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(child);
                map.put(parent, temp);
            } else {
                map.get(parent).add(child);
            }
        }
        // do a bfs on the graph to get all childs
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(kill);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int id = queue.poll();
                res.add(id);
                List<Integer> children = map.get(id);
                if (children != null) { // important! check if there exists children
                    for (int c : children) {
                        queue.offer(c);
                    }
                }
            }
        }
        return res;        
    }
}

发表于 | 分类于

Given a binary tree, you need to find the length of Longest Consecutive Path in Binary Tree.

Especially, this path can be either increasing or decreasing. For example, [1,2,3,4] and [4,3,2,1] are both considered valid, but the path [1,2,4,3] is not valid. On the other hand, the path can be in the child-Parent-child order, where not necessarily be parent-child order.

Example 1:

1
2
3
4
5
6
Input:
        1
       / \
      2   3
Output: 2
Explanation: The longest consecutive path is [1, 2] or [2, 1].

Example 2:

1
2
3
4
5
6
Input:
        2
       / \
      1   3
Output: 3
Explanation: The longest consecutive path is [1, 2, 3] or [3, 2, 1].

Note: All the values of tree nodes are in the range of [-1e7, 1e7].

解法1：

要先想想思路
一个node，返回已他为起点的最长的decreasing和increasing
那通过root的最长的一个path一定是increase + decrease - 1, 减1是去掉一次root
C++

1

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        int[] temp = helper(root);
        return max;        
    }
    private int[] helper(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int increase = 1, decrease = 1;
        if (root.left != null) {
            int[] left = helper(root.left);
            if (root.val == root.left.val + 1) {
                decrease = left[1] + 1;
            } else if (root.val == root.left.val -1) {
                increase = left[0] + 1;
            }
        }
        if (root.right != null) {
            int[] right = helper(root.right);
            if (root.val == root.right.val + 1) {
                decrease = Math.max(decrease, right[1] + 1);
            } else if (root.val == root.right.val -1) {
                increase = Math.max(increase, right[0] + 1);
            }
        }
        max = Math.max(max, decrease + increase -1);
        return new int[]{increase, decrease};
    }
}

发表于 | 分类于

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:
A subtree must include all of its descendants.
Here’s an example:

1
2
3
4
5
   10
   / \
  5  15
 / \   \
1   8   7

The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree’s size, which is 3.

Follow up:
Can you figure out ways to solve it with O(n) time complexity?

解法1：

C++

1

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    class NodeInfo {
        boolean isBST;
        int count;
        int max;
        int min;
        public NodeInfo (boolean isBST, int count, int max, int min) {
            this.isBST = isBST;
            this.count = count;
            this.max = max;
            this.min = min;
        }
    };
    int res = 0;   // Store the final result
    public int largestBSTSubtree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        NodeInfo dummy = helper(root);
        return res;
    }
    private NodeInfo helper(TreeNode root) {
        if (root == null) {
            return new NodeInfo(true, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        NodeInfo left = helper(root.left);
        NodeInfo right = helper(root.right);
        boolean isBST = false;
        if (root.val > left.max && root.val < right.min) {
            isBST = left.isBST && right.isBST;
        }
        int count = left.count + right.count + 1;
        if (isBST) {
            res = Math.max(res, count);
        }
        int max = Math.max(left.max, Math.max(right.max, root.val));
        int min = Math.min(left.min, Math.min(right.min, root.val));
        return new NodeInfo(isBST, count, max, min);        
    }
}