LC23 Merge k Sorted Lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
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
35
36
37
38
ListNode* merge2Lists(ListNode* cur1, ListNode* cur2){
    ListNode* cur = new ListNode();
    ListNode* node = cur;
    while(cur1 && cur2){
        if(cur1->val < cur2->val){
            cur->next = new ListNode(cur1->val);
            cur1 = cur1->next;
            cur = cur->next;
        }
        else{
            cur->next = new ListNode(cur2->val);
            cur2 = cur2->next;
            cur = cur->next;
        }
    }
    if(cur1){
        cur->next = cur1;
    }

    if(cur2){
        cur->next = cur2;
    }
    
    return node->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.empty()) return NULL;
    int n = lists.size();
    int interval = 1;
    while (interval < n)
    {
        for(int i = 0; i < n - interval; i += interval * 2){
            lists[i] = merge2Lists(lists[i], lists[i + interval]);
        }
        interval *= 2;
    }
    return lists[0];
}

LC169 Majority Element

Problem

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2
Think

投票法

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
int majorityElement(vector<int>& nums) {
    int res = nums[0];
    int cnt = 1;
    for(int i = 1; i < nums.size(); i++){
        if(nums[i] != res) cnt--;
        else cnt++;
        if(cnt == 0){
            res = nums[i];
            cnt = 1;
        }
    }
    return res;
}

LC215 Kth Largest Element in an Array

Problem

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Think

最大堆

Code 
1
2
3
4
5
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int> q(nums.begin(), nums.end());
    for(int i = 0; i < k - 1; i++) q.pop();
    return q.top();
}

LC218 The Skyline Problem

Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Buildings Skyline Contour

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
Think

归并，首先计算左边n/2的部分的skyline，然后计算右边n/2部分的skyline，然后将它们两个合并，合并的主要方法如下：

  • 取得当前最左的那个节点
  • 判断当前的最大高度应该为多少，即取此时的leftY和rightY的最大值
  • 如果最大值发生变化，则需要一个点去表明，需要添加一个点，否则不需要
  • 添加点的时候需要判断结果数组里是否已经存在当前的横坐标，如果存在则直接更新对应的高度即可，否则需要添加进结果数组
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
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    if(buildings.empty()) return {};
    sort(buildings.begin(), buildings.end());
    return helper(buildings, 0, buildings.size() - 1);
}
vector<vector<int>> helper(vector<vector<int>>& buildings, int start, int end) {
    if(start == end) return {{buildings[start][0], buildings[start][2]}, {buildings[start][1], 0}};
    int mid = start + (end - start) / 2;
    vector<vector<int>> left = helper(buildings, start, mid);
    vector<vector<int>> right = helper(buildings, mid + 1, end);
    vector<vector<int>> res;
    int nL = left.size(), nR = right.size();
    int leftY = 0, rightY = 0, curY = 0, maxY = 0;
    int pL = 0, pR = 0, x = 0;
    while(pL < nL && pR < nR){
        vector<int> pointL = left[pL];
        vector<int> pointR = right[pR];
        if(pointL[0] < pointR[0]){
            x = pointL[0];
            leftY = pointL[1];
            pL++;
        }
        else{
            x = pointR[0];
            rightY = pointR[1];
            pR++;
        }

        maxY = max(leftY, rightY);
        if(curY != maxY){
            if(res.empty() || res.back()[0] != x) res.push_back({x, maxY});
            else res.back()[1] = maxY;
            curY = maxY;
        }
    }

    while(pL < nL){
        vector<int> point = left[pL++];
        x = point[0];
        leftY = point[1];
        if(curY != leftY){
            if(res.empty() || res.back()[0] != x) res.push_back({x, leftY});
            else res.back()[1] = leftY;
            curY = leftY;
        }
    }

    while(pR < nR){
        vector<int> point = right[pR++];
        x = point[0];
        rightY = point[1];
        if(curY != rightY){
            if(res.empty() || res.back()[0] != x) res.push_back({x, rightY});
            else res.back()[1] = rightY;
            curY = rightY;
        }
    }
    return res;
}

LC240 Search a 2D Matrix II

Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

Think

从左下角开始查找，偏小则向右，偏大则向上

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if(matrix.empty() || matrix[0].empty()) return false;
    int m = matrix.size(), n = matrix[0].size();
    int i = m - 1, j = 0;
    int cur;
    while(i >= 0 && j < n){
        cur = matrix[i][j];
        if(cur < target) j++;
        else if(cur > target) i--;
        else return true;
    }
    return false;
}

LC241 Different Ways to Add Parentheses

Problem

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

1
2
3
4
5
Input: "2-1-1"
Output: [0, 2]
Explanation: 
((2-1)-1) = 0 
(2-(1-1)) = 2

Example 2:

1
2
3
4
5
6
7
8
Input: "2*3-4*5"
Output: [-34, -14, -10, -10, 10]
Explanation: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10
Think

遍历input，对每一个符号两端的字符串进行计算，得出所有可能的值

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> diffWaysToCompute(string input) {
    vector<int> res;
    int n = input.size();
    for(int i = 0; i < n; i++){
        if(ispunct(input[i])){
            for(auto first: diffWaysToCompute(input.substr(0, i))){
                for(auto second: diffWaysToCompute(input.substr(i + 1))){
                    if(input[i] == '+') res.push_back(first + second);
                    else if(input[i] == '-') res.push_back(first - second);
                    else res.push_back(first * second);
                }
            }
        }
    }
    return res.empty() ? vector<int>{stoi(input)}: res;
}

LC282 Expression Add Operators

Problem

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

1
2
Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Example 2:

1
2
Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]

Example 3:

1
2
Input: num = "105", target = 5
Output: ["1*0+5","10-5"]

Example 4:

1
2
Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

1
2
Input: num = "3456237490", target = 9191
Output: []
Think

递归，分三种情况，如果是乘法的话使用prevDiff即可，curNum = curNum - prevDiff + prevDiff * val

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
vector<string> addOperators(string num, int target) {
    vector<string> res;
    string each = "";
    dfs(num, target, 0, 0, 0, each, res);
    return res;
}
void dfs(string& num, int& target, int at, ll total, ll lastop, string& each, vector<string>& res){
    if(at >= num.size()){
        if(total == target){
            res.push_back(each);
            return;
        }
    }
    for(int i = at; i < num.size(); i++){
        string val = num.substr(at, i - at + 1);
        if(val[0] == '0' && val.size() > 1) break;  
        if(at == 0){
            each = val;
            dfs(num, target, i + 1, stol(val), stol(val), each, res);
            each = "";
        }else{
            int len = each.size();
            each += "+" + val;
            dfs(num, target, i + 1, total + stol(val), stol(val), each, res);
            each.resize(len);
            each += "-" + val;
            dfs(num, target, i + 1, total - stol(val), stol(val) * -1, each, res);
            each.resize(len);
            each += "*" + val;
            dfs(num, target, i + 1, total - lastop + lastop * stol(val), lastop * stol(val), each, res);
            each.resize(len);
        }
    }
}

LC312 Burst Balloons

Problem

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

  • You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

1
2
3
4
Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
Think

DP，设dp[i, j]表示nums[i, j]部分的最大结果，则有

dp[i, j] = max(dp[i, k - 1] + dp[k + 1, j] + nums[k] * nums[i - 1] * nums[j + 1]), for all k <= j and k >= i

p.s. 遍历顺序，需要先遍历小区间，再遍历大区间，所以遍历顺序应当是区间j - i + 1的从小到大的顺序。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxCoins(vector<int>& nums) {
    int n = nums.size();
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    vector<vector<int>> dp(n + 2, vector<int>(n + 2));
    for(int len = 1; len <= n; len++){
        for(int i = 1; i <= n - len + 1; i++){
            int j = i + len - 1;
            for(int k = i; k <= j; k++){
                dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + nums[i - 1] * nums[k] * nums[j + 1]);
            }
        }
    }
    return dp[1][n];
}

LC315 Count of Smaller Numbers After Self

Problem

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

1
2
3
4
5
6
7
Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Think

二分搜索法，从数组最后开始遍历，遍历的时候将当前值插入新数组中，使得新数组有序，则插入的位置就是这一位数字对应的结果，因为此时数组内的所有数字都是在这位数字之后的，只要比这个数字小的都会在新数组中排在这个数组之前。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> countSmaller(vector<int>& nums) {
    int n = nums.size();
    vector<int> t, res(n, 0);
    for(int i = n - 1; i >= 0; i--){
        int left = 0, right = t.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[i] > t[mid]) left = mid + 1;
            else right = mid;
        }
        res[i] = left;
        t.insert(t.begin() + left, nums[i]);
    }
    return res;
}

LC327 Count of Range Sum

Problem

Given an integer array nums, return the number of range sums that lie in [lower, upper]inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j(i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:

1
2
3
Input: nums = [-2,5,-1], lower = -2, upper = 2,
Output: 3 
Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.
Think

首先建立multiset对所有sums[0…i]进行排序，同时查找满足0<=j<i和sums[i] - upper <= sums[j] <= sums[i] - lower的j的所有取值。前者可以用lower_bound查找第一满足条件的j，后者可以用upper_bound查找第一个不满足条件的j，两者相减就是该sums[i]对应的j的个数。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
int countRangeSum(vector<int>& nums, int lower, int upper) {
    int n = nums.size();
    multiset<long> sums;
    long sum = 0;
    int res = 0;
    sums.insert(0);
    for(int i = 0; i < n; i++){
        sum += nums[i];
        res += distance(sums.lower_bound(sum - upper), sums.upper_bound(sum - lower));
        sums.insert(sum);
    }
    return res;
}

LC493 Reverse Pairs

Problem

Given an array nums, we call (i, j) an *important reverse pair* if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

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

Example2:

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

Note:

  1. The length of the given array will not exceed 50,000.
  2. All the numbers in the input array are in the range of 32-bit integer.
Think
  • Approach 1

BIT - 树状数组，即将上一题中的multiset改为BIT，然后将求距离变成getSum，插入数组变成update

  • Approach 2 - TLE

D&C，类似merge sort，每次先求左半部分和右半部分的结果，然后求i在左半部分，j在右半部分的结果数目，通过遍历左半部分查找右半部分来实现。

Code
  • Approach 1
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
int reversePairs(vector<int>& nums) {
    int res = 0, n = nums.size();
    vector<int> v = nums, bits(n + 1);
    sort(v.begin(), v.end());
    unordered_map<int, int> m;
    for(int i = 0; i < n; i++) m[v[i]] = i + 1;
    for(int i = n - 1; i >= 0; i--){
        res += getSum(lower_bound(v.begin(), v.end(), nums[i] / 2.0) - v.begin(), bits);
        update(m[nums[i]], bits);
    }
    return res;
}
int getSum(int i, vector<int> &bits){
    int sum = 0;
    while(i > 0){
        sum += bits[i];
        i -= (i & -i);
    }
    return sum;
}

void update(int i, vector<int> &bits){
    while(i < bits.size()){
        bits[i] += 1;
        i += (i & -i);
    }
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int reversePairs(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
    int helper(vector<int>& nums, int left, int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;
        int res = helper(nums, left, mid) + helper(nums, mid + 1, right);
        for(int i = left; i <= mid; i++){
            int j = mid + 1;
            while(j <= right && nums[i] / 2.0 > nums[j]) j++;
            res += j - mid - 1;
        }
        sort(nums.begin() + left, nums.begin() + right + 1);
        return res;
    }

Review

分治法主要和递归与二分相结合，对于分治法，主要有三种形式：

  • Binary Search Tree-based

  • Binary Indexed Tree-based

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 从节点i到数组尾端节点的所有节点的和
    int getSum(int[] bit, int i) {
        int sum = 0;
        while (i < bit.length) {
            sum += bit[i];
            i += i & -i;
        }
        return sum;
    }
    //在位置i插入一个数字k
    void insert(int[] bit, int i, int k) {
        while (i > 0) {
            bit[i] += k;
            i -= i & -i;
        }
    }

  • Merge Sort-based

其主要思想就是：分解数组，通过解决子数组上的子问题来解决整个问题

设数组为nums，nums[i, j]表示nums数组中i到j的部分（包含i和j），T(i, j)表示在子数组nums[i, j]上的子问题的解，则我们最终要解决的问题为T(0, n - 1)。一般有两种可能的情况：

  • Sequential recurrence relation

    T(i, j) = T(i, j - 1) + C

  • Partition recurrence relation

    T(i, j) = T(i, m) + T(m + 1, j) + C, where m = (i + j) / 2

如果不同的子问题之间存在重叠的话，则需要保存所有子问题的结果，类似于DP。