LC315 Remove Duplicate Letters

Problem

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

1
2
Input: "bcabc"
Output: "abc"

Example 2:

1
2
Input: "cbacdcbc"
Output: "acdb"
Think

首先遍历字符串，求得每个字母的出现次数，然后用一个哈希表来存放当前字母是否已经被访问过。

再次遍历字符串，首先将当前字母对应的出现次数-1，如果该字母已经访问过，则说明当前字母已经加入了结果，则继续下一次循环；否则，将当前字母不断的和结果字符串的最后一个字符进行比较，如果比结果字符串的最后一个字母小，而且这个最后一个字母对应的cnt数组大于0，说明之后还会出现这个字母，因此可以从res中删去；最后将当前遍历到的字母分别加入结果字符串和哈希表中。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string removeDuplicateLetters(string s) {
    vector<int> cnt(26, 0);
    unordered_set<char> map;
    for(auto c: s) cnt[c - 'a']++;
    string res = "0";
    for(auto c: s){
        cnt[c - 'a']--;
        if(map.count(c)) continue;
        while(c < res.back() && cnt[res.back() - 'a'] != 0){
            map.erase(res.back());
            res.pop_back();
        }
        res += c;
        map.insert(c);
    }
    return res.substr(1);
}

LC321 Create Maximum Number

Problem

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

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

Example 2:

1
2
3
4
5
6
Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output:
[6, 7, 6, 0, 4]

Example 3:

1
2
3
4
5
6
Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output:
[9, 8, 9]
Think

设两个数组长度分别为m和n，设从第一个数组中取i个数字，则从第二个数组中取k-i个数字。

i的范围的确定：

当i > n的时候，第一个数组至少要取k - n个数字；当i <= n的时候，第一个数组至少取0个数字，因此i的最小值应该为max(0, k - n)；

对应的，在nums1数组中最大只能取k个数和m个数字中的较小值，即i的最大值为min(k, m)；

对于每一种i的情况，判断res和nums1取i个数字，nums2取k-i个数字并merge之后的大小。因此需要解决如下问题：

  • 从一个数组nums中取k个数字所能组成的最大值：

    设nums的长度为n，因此需要删除n - k个数字。采用类似上一题的做法，每次判断是否还有数字要删除(drop > 0)、结果数组不为空(!res.empty())以及当前数字是否大于res数组的尾端的数字(num > res.back())，将所有满足这些条件的数字删除，然后将当前数字push进res数组，最后resize为k(取前k个数)；

  • merge两个数组所能组成的最大值：这里的merge不能单纯比较每个数组的开头的元素的大小，而是需要对数组整体进行大小比较，取较大数组的头元素，然后将这个头元素从数组中删去。

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
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    int m = nums1.size(), n = nums2.size();
    vector<int> res;
    for(int i = max(0, k - n); i <= min(k, m); i++){
        res = max(res, mergeVector(maxNumber(nums1, i), maxNumber(nums2, k - i)));
    }
    return res;
}

vector<int> maxNumber(vector<int>& nums, int k) {
    vector<int> res;
    int drop = (int)nums.size() - k;
    for(auto num: nums){
        while(drop > 0 && !res.empty() && num > res.back()){
            res.pop_back();
            drop--;
        }
        res.push_back(num);
    }
    res.resize(k);
    return res;
}

vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
    vector<int> res;
    while (!nums1.empty() || !nums2.empty()) {
        vector<int> &tmp = (nums1 > nums2) ? nums1 : nums2;
        res.push_back(tmp[0]);
        tmp.erase(tmp.begin());
    }
    return res;
}

LC330 Patching Array

Problem

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

1
2
3
4
5
6
7
Input: nums = [1,3], n = 6
Output: 1 
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:

1
2
3
Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

1
2
Input: nums = [1,2,2], n = 5
Output: 0
Think

初始化当前可计算范围为[1, 1)，进行下列循环：

设当前可计算范围为[1, miss)，也就是miss是无法计算的，那么为了计算miss，我们直接将miss添加进数组即可。在添加之前我们要先判断当前数组内是否存在可以计算出miss值的数字，即后一位的num是否小于等于miss，如果满足，则miss = miss + nums[i]，否则需要添加一个数字miss进数组，然后miss = miss * 2。

  • Initialize the range [1, miss) = [1, 1) = empty

  • While n is not covered yet

    • if the current element nums[i] is less than or equal tomiss

      • extends the range to [1, miss + nums[i])

  • increase i by 1

  • otherwise

    • patch the array with miss, extends the range to [1, miss + miss)

  • increase the number of patches

  • Return the number of patches

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minPatches(vector<int>& nums, int n) {
    long right = 1;
    int i = 0, res = 0;
    while(right <= n){
        if(i < nums.size() && nums[i] <= right){
            right += nums[i];
            i++;
        }
        else{
            right *= 2;
            res++;
        }
    }
    return res;
}

LC392 Is Subsequence

Problem

Given a string s and a string t, check if s is subsequence of t.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Example 1:

1
2
Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

1
2
Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • Both strings consists only of lowercase characters.
Think

双指针，分别从两个字符串开头遍历，相同则同时后移，不同则后移t对应的指针，最后判断s是否遍历完即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i = 0, j = 0;
        while(i < m && j < n){
            if(s[i] == t[j]){
                i++;
                j++;
            }
            else{
                j++;
            }
        }
        return i == m;
    }

LC402 Remove K Digits

Problem

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

1
2
3
>Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3
>Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3
>Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Think

Greedy+Stack

建立一个栈，然后遍历num，如果当前num[i]比栈顶的数值小，而且k>0(说明还可以删数字)，则将栈顶的数字pop出来，将num[i]push进去。然后将栈的前n - k个数字提取出来，形成字符串，并将前缀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
string removeKdigits(string num, int k) {
    stack<char> s;
    int drop = 0;
    int n = num.size();
    for(auto digit: num){
        while(!s.empty() && k > 0 && s.top() > digit){
            k--;
            s.pop();
        }
        s.push(digit);
    }
    for(int i = 0; i < k; i++){
        s.pop();
    }
    string res;
    while(!s.empty()){
        res = s.top() + res;
        s.pop();
    }
    int left = 0;
    while(res[left] == '0'){
        left++;
    }
    res = res.substr(left);
    return res == "" ? "0": res;
}

LC406 Queue Reconstruction by Height

Problem

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

1
2
3
4
5
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
Think

首先对所有的people进行排序，排序规则为，第一位降序，第二位升序，然后按顺序将每一个p插入在res.begin() + p[1]的部分。

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
struct{
    bool operator()(vector<int>& p1, vector<int>& p2) const{
        if(p1[0] > p2[0]){
            return true;
        }
        else if(p1[0] < p2[0]){
            return false;
        }
        else{
            if(p1[1] > p2[1]){
                return false;
            }
            else{
                return true;
            }
        }
    }
} cmp;
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> res;
        for(auto p: people){
            res.insert(res.begin() + p[1], p);
        }
        return res;
    }
};

LC435 Non-overlapping Intervals

Problem

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

1
2
3
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

1
2
3
Input: [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

1
2
3
Input: [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. Intervals like [1,2] and [2,3] have borders “touching” but they don’t overlap each other.
Think

Greedy，首先对所有intervals按照结束时间进行排序，然后遍历intervals，判断如果两个interval有重叠，则保留结束时间在前的那一个（需要更新prev和cnt）。

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
struct{
    bool operator()(vector<int> a, vector<int> b){
        return a[1] < b[1];
    }
}comp;
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        sort(intervals.begin(), intervals.end(), comp);
        int n = intervals.size();
        int end = intervals[0][1], prev = 0, cnt = 0;
        for(int i = 1; i < n; i++){
            if(intervals[prev][1] > intervals[i][0]){
                if(intervals[prev][1] > intervals[i][1]){
                    prev = i;
                }
                cnt++;
            }else{
                prev = i;
            }
        }
        return cnt;
    }
};

LC452 Minimum Number of Arrows to Burst Balloons

Problem

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

1
2
3
4
5
6
7
8
Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).
Think

首先对数组进行排序，设置当前的重叠区间cur为points[0]，然后遍历points数组，如果和下一个区间有重叠部分，则说明可以在这个重叠区间里射击即可打穿气球，因此不需要更多一次的次数，因此cur设置为新的重叠区间；如果没有重叠部分，则说明需要更多一次的次数来射击气球，因此次数需要+1，当前重叠区间设置为当前points的区间即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findMinArrowShots(vector<vector<int>>& points) {
    if(points.empty()) return 0;
    sort(points.begin(), points.end());
    vector<int> cur = points[0];
    int res = 1;
    for(int i = 1; i < points.size(); i++){
        if(cur[1] < points[i][0]){
            cur = points[i];
            res++;
        }
        else{
            cur[0] = max(cur[0], points[i][0]);
            cur[1] = min(cur[1], points[i][1]);
        }
    }
    return res;
}

LC455 Assign Cookies

Problem

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:

1
2
3
4
5
6
7
Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3. 
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.

Example 2:

1
2
3
4
5
6
7
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.
Think

首先将g和s排序，设置i和j初始为0，对每一个饼干j，如果s[j] >= g[i]，即饼干j可以满足第i个人的要求，就跳到下一个人(i++)，且res++

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findContentChildren(vector<int> &g, vector<int> &s)
{
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());
    int i = 0, j = 0, res = 0;
    while(i < g.size() && j < s.size()){
        if(g[i] <= s[j]){
            i++;
            res++;
        }
        j++;
    }
    return res;
}

LC502 IPO

Problem

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given several projects. For each project i, it has a pure profit Pi and a minimum capital of Ci is needed to start the corresponding project. Initially, you have Wcapital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

To sum up, pick a list of at most k distinct projects from given projects to maximize your final capital, and output your final maximized capital.

Example 1:

1
2
3
4
5
6
7
8
9
Input: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].

Output: 4

Explanation: Since your initial capital is 0, you can only start the project indexed 0.
             After finishing it you will obtain profit 1 and your capital becomes 1.
             With capital 1, you can either start the project indexed 1 or the project indexed 2.
             Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
             Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Note:

  1. You may assume all numbers in the input are non-negative integers.
  2. The length of Profits array and Capital array will not exceed 50,000.
  3. The answer is guaranteed to fit in a 32-bit signed integer.
Think

首先判断是否所有的项目都立刻可以做，如果是的话就直接取利润最大的k个项目就可以了；否则：

建立一个最小堆，将每一个capital和profit对在堆中按capital升序排列；

建立一个最大堆，存放当前所有可以做的项目，按profit降序排列；

如果k>0，则说明还可以完成任务，因此将当前所有可以完成的任务加入available堆中，然后取出其中profit最大的任务即可。重复这个过程直到k=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
28
29
30
31
32
33
34
35
36
37
38
39
40
int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
    bool speedUp = true;
    for(auto c: Capital){
        if(W < c){
            speedUp = false;
            break;
        }
    }
    if(speedUp){
        priority_queue<int> q;
        for(auto p: Profits){
            q.push(p);
        }
        for(int i = 0; i < k; i++){
            W += q.top();
            q.pop();
        }
        return W;
    }

    int n = Profits.size();
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> projects;
    for(int i = 0; i < n; i++){
        projects.push({Capital[i], Profits[i]});
    }
    priority_queue<int> available;
    while(k > 0){
        while(!projects.empty() && projects.top()[0] <= W){
            available.push(projects.top()[1]);
            projects.pop();
        }
        if(!available.empty()){
            W += available.top();
            available.pop();
        }
        else break;
        k--;
    }
    return W;
}

LC621 Task Scheduler

Problem

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example:

1
2
3
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Constraints:

  • The number of tasks is in the range [1, 10000].
  • The integer n is in the range [0, 100].
Think
  • Approach 1

首先统计各个字母的出现次数，然后排序，取出现次数最多的那一个，即从这一个开始需要进入一个小循环，长度为n，在这个循环里不能有重复的task出现，而只有当第25-i类task存在的时候才会对其次数减一，否则相当于idle；然后再对出现次数数组进行排序，继续下一次循环。

  • Approach 2

首先统计各个字母的出现次数，然后排序，从出现次数最多的那一个开始，将其放在所有时间循环的开头，然后一次将后面的task放在循环的下一个位置，也就是idle的位置每一次都会减少times[i]，最后直接计算idle + tasks.size()即可。

621

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int leastInterval(vector<char>& tasks, int n) {
    vector<int> times(26, 0);
    for(auto c: tasks){
        times[c - 'A']++;
    }
    sort(times.begin(), times.end());
    int res = 0;
    while(times.back() > 0){
        int i = 0;
        while(i <= n){
            if(times[25] == 0) break;
            if(i < 26 && times[25 - i] > 0) times[25 - i]--;
            i++;
            res++;
        }
        sort(times.begin(), times.end());
    }
    return res;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
int leastInterval(vector<char>& tasks, int n) {
    vector<int> times(26, 0);
    for(auto c: tasks){
        times[c - 'A']++;
    }
    sort(times.begin(), times.end());
    int max_val = times[25] - 1, idle = max_val * n;
    for(int i = 24; i >= 0 && times[i] > 0; i--){
        idle -= min(times[i], max_val);
    }
    return idle > 0 ? idle + tasks.size() : tasks.size();
}

Review

Greedy的题目都不简单，主要不同的贪心算法的贪的地方不一样，而且很多时候也很难证明贪心算法的正确性，因此面对可能是贪心算法的题目，首先要先确定贪心算法是否有合理性，一般情况先可以通过反证法来略微思考一下，或者举几个例子试一下；在确定了是采用贪心算法的时候，我们就需要判断应该在何处“贪”，一般情况下是出现次数、利润、价格、单位利润率等方向，必要时除了使用sort之外，还可以考虑使用堆(priority_queue)。