Binary Search(2)

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

1 2 3

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

• Approach 1

二分法，首先计算前i个元素的和的数组sum，然后对于i在0 - n - 1之间的每一个sum[i]，在sum数组中找第一个大于等于sum[i] + s的数字的下标k，此处对应的即为满足条件的子数组范围[i + 1, k]。

• Approach 2

双指针法，首先将左指针指向0，然后每次右移一位right，判断此时能把left最多左移多少位，然后取最短的长度即可。

• Approach 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int minSubArrayLen(int s, vector<int>& nums) {
    int n = nums.size();
    vector<int> sum(n + 1, 0);
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i - 1] + nums[i - 1];
    }
    int ans = INT_MAX;
    for(int i = 0; i < n; i++){
        auto bound = lower_bound(sum.begin(), sum.end(), sum[i] + s);
        if(bound != sum.end()){
            ans = min(ans, (int)(bound - (sum.begin() + i)));
        }
    }
    return (ans == INT_MAX) ? 0 : ans;
}

• Approach 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int minSubArrayLen(int s, vector<int>& nums) {
    int n = nums.size();
    int ans = INT_MAX;
    int sum = 0;
    int left = 0;
    for(int i = 0; i < n; i++){
        sum += nums[i];
        while(sum >= s){
            ans = min(ans, i - left + 1);
            sum -= nums[left++];
        }
    }
    return (ans == INT_MAX) ? 0 : ans;
}

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1:

1 2 3 4 5 6 7

Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1

Example 2:

1 2 3 4 5 6 7 8 9

Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Constraints:

• The number of elements of the BST is between 1 to 10^4.
• You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

二分 + 递归，根据左子树的节点数目决定找左子树还是右子树

Given an array of citations sorted in ascending order (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.”

Example:

1 2 3 4 5 6

Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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.

Follow up:

• This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
• Could you solve it in logarithmic time complexity?

二分查找

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

1 2 3 4 5 6 7

Given n = 5, and version = 4 is the first bad version. call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version.

二分查找

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1 2 3

Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

• Approach 1

DP，dp[i] = max(dp[j] + 1) 对所有满足nums[j] < nums[i]且j < i的元素

• Approach 2

二分，首先建立一个数组存放最长递增子序列的结果，对于每一个数字，查找这个数组中第一个大于等于当前数字的数组的下标，并用当前数字去替换（这样替换只会使得可能的最长子序列变长而不可能变短），如果没有这样的下标，则说明需要在数组的最后添加一位，最后返回该数组的总长度即可。

• Approach 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(nums[j] < nums[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int res = 0;
    for(int cnt: dp) res = max(res, cnt);
    return res;
}

• Approach 2

1
2
3
4
5
6
7
8
9
10
11
12
13

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp;
    for(int num: nums){
        auto i = lower_bound(dp.begin(), dp.end(), num);
        if(i == dp.end()) dp.push_back(num);
        else{
            int idx = i - dp.begin();
            dp[idx] = num;
        }
    }
    return dp.size();
}

Given two arrays, write a function to compute their intersection.

Example 1:

1 2	Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2]

Example 2:

1 2	Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4]

Note:

• Each element in the result must be unique.
• The result can be in any order.

hash set

Given two arrays, write a function to compute their intersection.

Example 1:

1 2	Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

Example 2:

1 2	Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

类似上一题目，用hash map

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:

1 2 3 4 5

[1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]

Follow up:

What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

添加数字的时候首先求出当前数字在intervals数组中的位置，然后判断其是否和查找到的位置的前一个区间有重叠部分，如果有，则取得前一个区间，从这一个区间开始进行合并。每当遇到当前区间和val可合并，则更新start和end（表示合并后的区间），然后将当前区间移除。最后插入这个一个区间即可。

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note:
Rotation is not allowed.

Example:

1 2 3

Input: [[5,4],[6,4],[6,7],[2,3]] Output: 3 Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

将envelops数组按照第一位递增第二位递减的顺序排好，然后在所有的第二位组成的序列中查找最长递增子序列即可。因为此时只要在第二位上递增，第一位一定比上一个要小。

Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

1 2 3 4

Input: matrix = [[1,0,1],[0,-2,3]], k = 2 Output: 2 Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Note:

1. The rectangle inside the matrix must have an area > 0.
2. What if the number of rows is much larger than the number of columns?

首先对每一列，求这一列到最后某一列处的每一行的和，即sum数组，然后从上往下进行累加。首先设定一个set s存放累加和，对于每一个累加和curSum，查找第一个大于等于curSum - k的值，即这两个curSum对应的下标之间即为要求的最大的矩阵和的范围，如果存在则更新res，最后将当前累加和插入s中。