Leetcode 651: 4 Keys Keyboard

 Imagine you have a special keyboard with the following keys:

Key 1: (A): Print one 'A' on screen.

Key 2: (Ctrl-A): Select the whole screen.

Key 3: (Ctrl-C): Copy selection to buffer.

Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.

Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.

Example 1:

Input: N = 3
Output: 3
Explanation: 
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

 

Example 2:

Input: N = 7
Output: 9
Explanation: 
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

 

Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

Notes:

This question can be solved by dp.

Imagine that we have solved all the smaller one than i, now we need to solve dp[i].

dp[i] means the maximum number of A that can be printed.

then dp[i] can be derived from the solved dp's but with a smaller index.

If j is one of them, and dp[j] is solved, and j < i

Then dp[i] could be dp[j] * (i - j -1). Why?

Because we need to Ctr-A and Ctr-C before we can Ctr-V. For example, we have dp[3], then dp[5] could be dp[3]*(5 - 3 -1) = dp[3] (which obviously is not the optimal choice. A different way is that we can simply add two As directly (using key 1) after dp[3] which can give dp[3] + 2 for dp[5].)

Thus, in order to find the optimal choice, one way is that we can go through all the smaller ones by the above two ways:

1): use key2 + key3 + kye4s,  (this could be true for larger i), the formula for this is:

      dp[j] * (i - j -1)

2): use key1 directly, (this could be true for smaller i)

       dp[j] + (i - j)

If we decide to go through all the dp's with indexes smaller than i, then it meas the time complexity is O(N^2). In this question, N <= 50, so it should be Okay.

See the code below:

class Solution {
public:
    /**
     * @param N: an integer
     * @return: return an integer
     */
    int maxA(int N) {
        // write your code here
        vector<int> dp(N+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=N; ++i) {
            for(int j=0; j<i; ++j) {
                dp[i] = max(dp[i], dp[j] + i - j);
                if(j+3<i) dp[i] = max(dp[i], dp[j]*(i-j-1));
            }
        }
        return dp[N];
    }
};

 

Leetcode 358: Rearrange String K Distance Apart

 https://leetcode.com/problems/find-latest-group-of-size-m/description/

Notes:

This question is very similar as another question Leetcode 621 (since I solved that question first...)

The basic idea is the same: we need to find the letter with the largest count (m), then for the first (m-1) we have to place (m-1)*k letters (including the letter with the maximum count). 

Then for the last one letter, we do not need to keep it k distance apart from the next one (since there is no next one...). If there is no letter with the tied maximum counting, we just need to add 1 (the letter itself), but if there are n letters with the maximum counting, then the need to add n more letters, to list all the letter with k distance apart.

The overall letters need are (m-1)*k + n. If this value is larger than the size of the string, then there is not enough letters to maintain k distance apart: means that this is impossible. Otherwise, it is okay to form an valid one.

Since this question requests to return one final string, so we can consider to use a priority queue for valid ones: 

1): every time, we pick up one with the largest counting; 

2): and we keep this until we have pop out k different letters. This will form one valid "k-distance" apart substring; 

3): then we need to put the previous pop-out elements back to the priority queue, if their size still larger than 1 after removing 1.

4): repeat this process until there is no element remaining in the queue.

See the code below:

class Solution {
public:
    string rearrangeString(string str, int k) {
        if (k == 0) return str;
        string res;
        int len = (int)str.size(), mx = 0, rep = 0;
        unordered_map<char, int> m;
        priority_queue<pair<int, char>> q;
        for (auto a : str) ++m[a];
        for (auto it = m.begin(); it != m.end(); ++it) {
            q.push({it->second, it->first});
            // find the maximum counting, and the numer of letters having this 
	    if (it->first > mx) {
                mx = it->first;
                rep = 1;
	    } else if (it->first == mx) {
                ++rep;   
            }
        }
        // if need more letters than itself, then cannot construct an valid one
        if((m-1)*k + rep > len) return "";
        while (!q.empty()) {
            vector<pair<int, int>> v;
            int cnt = min(k, len);
            for (int i = 0; i < cnt; ++i) {
                if (q.empty()) return "";
                auto t = q.top(); q.pop();
                res.push_back(t.second);
                if (--t.first > 0) v.push_back(t);
                --len;
            }
            for (auto a : v) q.push(a);
        }
        return res;
    }
};

 

Facebook Phone Interview 2: Employee Free Time

 We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

 

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

 

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

Notes: 

One straightforward way is to merge all the internals by removing the overlapping, then find the "the empty" intervals.  By using priority_queue to pop up the next available interval, we can solve this problem in O(m*n*log(m)), where m is the size of schedule and n is the size of schedule[i].

Another way is to use the scan-line algorithm: sort all the beginning and ending time, then scan them from the left to right. Use a count to represent how many people are working in that time interval.

Since we have m*n intervals, thus we will have 2*m*n elements (both starting and ending times), then the time complexity is O(2*m*n*log(2*m*n)). But it is easy to code.

class Solution {
public:
    vector<vector<int>> findCommonFreetime(vector<vector<vector<int>>>& mt) {
    	if (!mt.size()) return 0;
        vector<pair<int, int>> data;
        for (auto &a : mt) {
	    for(auto &b : a) {
		data.push_back({b[0], 1});
                data.push_back({b[1], -1});
	    }
        }
	sort(data.begin(), data.end());
	int ct = 0, left = -1;
 	for (int i=0; i<data.size(); ++i) {
	    auto t = data[i];
	    if(t.second == 1) {
                ++ct;
                if (ct == 1 && left != -1 && left < t.first) {
                    vector<int> temp;
                    temp.push_back(left);
                    temp.push_back(t.first);
                    res.push_back(temp);
                    left = -1;
		}
	    else --ct;
            if (ct==0) left = t.first; 
	}
	return res;
    }
}

Leetcode 1088: Confusing Number II

https://leetcode.com › problems › confusing-number-ii

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.(Note that the rotated number can be greater than the original number.)

Given a positive integer N, return the number of confusing numbers between 1 and N inclusive.



Example 1:

Input: 20
Output: 6
Explanation:
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.
Example 2:

Input: 100
Output: 19
Explanation:
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].


Note:

1 <= N <= 10^9


Notes:

The N to this question can be very large, so checking one by one is not a good choice.

As indicated by the question itself, only 0, 1, 6, 8, and 9 are valid numbers. So we just need to check the numbers composed by them.

Since we will compare digits at different positions, so string can be a good choice for easier coding than integer.

Now the question becomes a typical backtracking one: we will try all the possible combinations, then check the qualification. If valid, count +1.

See the code below:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int findAllConfNums(int n);

void dfs(string t, string &s, string &nums, int &res);

int main() {
    int n = 100;
    int num = findAllConfNums(n);
    cout<<num;
    return 0;
}

int findAllConfNums(int n) {
    int res = 0;
    string s = to_string(n);
    string nums = "01689";
    dfs("", s, nums, res);
    return res;
}

void dfs(string t, string &s, string &nums, int &res) {
    if(t.size() > s.size() || t.size() == s.size() && t.compare(s) > 0) return;
    if(t.size() && t[0] == '0') return;
    string temp = t;
    reverse(temp.begin(), temp.end());
    for(int i=0; i<temp.size(); ++i) {
        if(temp[i] == '6') temp[i] = '9';
        else if(temp[i] == '9') temp[i] = '6';
    }
    if(t != temp) ++res;
    for(int i=0; i<nums.size(); ++i) {
        dfs(t + nums.substr(i, 1), s, nums, res);
    }
}

Leetcode 253: Meeting Rooms II

https://leetcode.com › problems › meeting-rooms-ii

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

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

Notes:

This question is a very popular interview question, since that it can be solved by many methods.

However, this question can be solved by a very intuitive and surprisingly very powerful algorithm: sweeping-line algorithm.

The basic idea is that we just need to sort the start time and end time first. Then scan them from left to right.

1): if we meet with a start time, it means we need to start a new meeting; so meeting room needs +1;

2): if we meet with a end time, it means one meeting is over; so meeting room - 1.

Thus, this question is equivalent to ask: what is the maximum number of meeting that are hold at the same time?

See the code below:

class Solution {
public:
    int minMeetingRooms(vector<vector<char>>& intervals) {
        int res = 0;
        vector<pair<int, int>> startEndTimes; //<time, star/end>
        for(auto &a : intervals) {
            startEndTimes.push_back({a[0], 1});//start time
            startEndTimes.push_back({a[0], 0});//end time
        }
        sort(startEndTimes.begin(), startEndTimes.end());
        int count = 0;
        for(auto &a : startEndTimes) {
            if(a.second == 1) ++count;
            else --count;
            res = max(res, count);
        }
        return res;
    }
};

Similar questions: Given fly-time intervals of planes, what is the maximum number of planes flying at the same time?

Leetcode 249: Group Shifted String

https://leetcode.com › problems › group-shifted-strings

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

Note: For the return value, each inner list's elements must follow the lexicographic order.

Notes:

This question is not hard to come up a solution, but it seems not easy to make the code clean.

Below is one way to code. Basically, if two strings belong to the same group, the difference of between all the letters and the first letter are the same for both strings. So we use this as a key to a hash table.

See the code below:

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {
        vector<vector<string>> res;
        unordered_map<string, multiset<string>> m;
        for (auto a : strings) {
            string s = "";
            for (char &c : a) {
                s += to_string((c + 26 - a[0]) % 26) + ",";
            }
            m[s].insert(a);
        }
        for(auto it = m.begin(); it != m.end(); ++it) {
            res.push_back(vector<string>(it->second.begin(), it->second.end()));
        }
        return res;
    }
};

Leetcode 248: Strobogrammatic Number III

https://leetcode.com › problems › strobogrammatic-number-iii

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

Input: low = "50", high = "100"
Output: 3 
Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:
Because the range might be a large number, the lowand high numbers are represented as string.

Notes:

This question can be viewed as a follow-up of Strobogrammatic number I and II.

One way to solve this problem is that we can count the number of each length between low and high (inclusive), and then add them together.

The corner case is when the length is the same as that of the low or high, we need to choose the ones inside the range. For easy coding, we can use string.compare() function.

See the code below:

class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        int res = 0;
        vector<string> ss = {"", "0", "1", "8"};
        for(int i = low.size(); i <= high.size(); ++i) {
            for(auto &s : ss) {
                find(low, high, s, i, res);
            }
        }
        return res;
    }

private:
    void find(string low, string high, string path, int len, int &res) {
        if(path.size() >= len) {
            if(path.size() != len || (len != 1 && path[0] == '0')) return;
            if(len == low.size() && path.compare(low) < 0) return; 
            if(len == high.size() && path.compare(high) > 0) return;
            ++res;
        }
        vector<string> ss1 = {"0", "1", "6", "8", "9"}, ss2 = {"0", "1", "9", "8", "6"};
        for(int i = 0; i<ss1.size(); ++i) {
            find(low, high, ss1[i] + path + ss2[i], len, res);
        }
    }
};

Second Solution:

Apparently, we re-calculate a lot in the above code, since we go over all the possible case (even more than 1 times). For example, for each length, we always start from 0.

There are some rules if we observe carefully.

For example, length = 1, there are 3, "0", "1", and "8", thus dp[1] = 3;
when length  = 2, there are five, "00", "11", "69", "88",  and "96", but the first one does not valid, thus dp[2] = 4;

Now let us look at the dp[3]. After think for a while, it turn out that they can only be formed by inserting a single number in the middle of that with a length of 2. And there are only 3 valid single numbers. Thus, dp[3] = 3*dp[2];

Now let us look at the dp[4]. Similar to dp[3], the one with length of 4 can be formed by inserting the above one of the basic units with a length of 2 in the middle of that with a length of 2. And there are 5 kinds of these basic unites ("00" now is valid since we insert in the middle). Thus dp[4] = 5*dp[2];

Similarly, dp[5] = 3*dp[4], and dp[6] = 5*dp[4], ...

Thus, dp[2n] = 5^(n-1) * dp[2], dp[2n+1] = 3 * 5^(n-1) * dp[2], where n>0.

 So we can just modify the above code to calculate the number of solutions with the same length of low and also no smaller than it; as well as the number of solutions with the same length of high and also no larger than it. To do this, we just need to modify the code for Strobogrammatic Number II a little bit (adding comparison with the low or high, and just recording the valid counts).

The one with lengths in the range can be calculated directly using the above dp table.

See the code below:

class Solution {
public:
    int findStrobogrammatic(string low, string high) {
        if(low > high) return 0;
        if(low == high) return isValid(low) ? 1 : 0;
        int res = 0, ct1 = 0, ct2 = 0, len1 = low.size(), len2 = high.size();
        vector<string> ss = {"0", "1", "8", "69", "96"};
        dfs1(ss, "", low, ct1);
        dfs2(ss, "", high, ct2);
        res += ct1 + ct2;
 vector<int> dp(len2, 0);
        dp[0] = 1;//empty string
        dp[1] = 3;
        dp[2] = 5;
        for(int i=3; i<len2; ++i) {
            if(i & 1) dp[i] = 3 * dp[i-1];
            else dp[i] = 5 * dp[i-2];
        }
        for(int i=len1 + 1; i<len2; ++i) res += dp[i];  
        return res;
    }

private:
    void dfs1(vector<string>& ss, string s, string p, int &res){
        if(s.size() == p.size() && s.compare(p) >= 0) {
            if(s.empty() || s.size()<2 || s[0]!='0') ++res;
            return;
        }
        for(int i=0; i<ss.size(); ++i){
            if(((int)p.size())&1 && s.empty()) {
                if(ss[i].size() == 1) dfs1(ss, s+ss[i], n-1, res);
            }
            else{
                if(ss[i].size()>1) {
                    dfs1(ss, ss[i].substr(0, 1) + s + ss[i].substr(1), n-2, res);
                }
                else dfs1(ss, ss[i]+s+ss[i], n-2, res);
            }
        }
    }

    void dfs2(vector<string>& ss, string s, string p, int &res){
        if(s.size() == p.size() && s.compare(p) <= 0) {
            if(s.empty() || s.size()<2 || s[0]!='0') ++res;
            return;
        }
        for(int i=0; i<ss.size(); ++i){
            if(((int)p.size())&1 && s.empty()) {
                if(ss[i].size()>1) dfs2(ss, s+ss[i], n-1, res);
            }
            else{
                if(ss[i].size()>1) {
                    dfs2(ss, ss[i].substr(0, 1) + s + ss[i].substr(1), n-2, res);
                }
                else dfs2(ss, ss[i]+s+ss[i], n-2, res);
            }
        }
    }

    bool isValid(string s) {
        int i = 0, len = s.size(), j = len - 1;
        while(i<=j) {
            if(s[i] == s[j]) {
                if(s[i] == '0' || s[i] == '1' || s[i] == '8') {
                    ++i;
                    --j;
                }
                else return false;
            }
            else {
                if(s[i] == '6' && s[j] == '9' || s[i] == '9' && s[j] == '6') {
                    ++i;
                    --j;
                }
                else return false;
            }
        }
        return true;
    }
};

Third Solution:

To make the code shorter, we can write a sub-function to calculate the total valid number smaller than a val. Then we just need to call this sub-function twice and calculate the difference.

We still need to figure out whether high itself is valid or not, and it is Srobogrammatic Number I.

See the code below:

Strobogrammatic Number III - LeetCode

class Solution {
public:
    int findStrobogrammatic(string low, string high) {
        if(low > high) return 0;
        int res = 0;
        vector<string> ss = {"0", "1", "8", "69", "96"};
        int ct1 = dfs(ss, "", low), ct2 = dfs(ss, "", high);
        res += ct2 - ct1;  
        return res + isValid(low) ? 1 : 0;
    }

private:
    int dfs(vector<string>& ss, string s, string p){
        if(s.size() == p.size() && p.compare(s) >= 0) {
            if(s.empty() || s.size()<2 || s[0]!='0') return 1;
            return 0;
        }
        int res = 0;
        for(int i=0; i<ss.size(); ++i){
            if(((int)p.size())&1 && s.empty()) {
                if(ss[i].size() == 1) res += 1 + dfs(ss, s+ss[i], n-1, res);
            }
            else{
                if(ss[i].size()>1) {
                    res += 1 + dfs(ss, ss[i].substr(0, 1) + s + ss[i].substr(1), n-2, res);
                }
                else res += 1 + dfs(ss, ss[i]+s+ss[i], n-2, res);
            }
        }
        return res;
    }

    bool isValid(string s) {
        int i = 0, len = s.size(), j = len - 1;
        while(i<=j) {
            if(s[i] == s[j]) {
                if(s[i] == '0' || s[i] == '1' || s[i] == '8') {
                    ++i;
                    --j;
                }
                else return false;
            }
            else {
                if(s[i] == '6' && s[j] == '9' || s[i] == '9' && s[j] == '6') {
                    ++i;
                    --j;
                }
                else return false;
            }
        }
        return true;
    }
};

Leetcode 1152: Analyze User Website Visit Pattern

https://leetcode.com › problems › analyse-user-website-visit-pattern

We are given some website visits: the user with name username[i] visited the website website[i] at time timestamp[i].

A 3-sequence is a list of websites of length 3 sorted in ascending order by the time of their visits.  (The websites in a 3-sequence are not necessarily distinct.)

Find the 3-sequence visited by the largest number of users. If there is more than one solution, return the lexicographically smallest such 3-sequence.

Example 1:

Input: username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
Output: ["home","about","career"]
Explanation: 
The tuples in this example are:
["joe", 1, "home"]
["joe", 2, "about"]
["joe", 3, "career"]
["james", 4, "home"]
["james", 5, "cart"]
["james", 6, "maps"]
["james", 7, "home"]
["mary", 8, "home"]
["mary", 9, "about"]
["mary", 10, "career"]
The 3-sequence ("home", "about", "career") was visited at least once by 2 users.
The 3-sequence ("home", "cart", "maps") was visited at least once by 1 user.
The 3-sequence ("home", "cart", "home") was visited at least once by 1 user.
The 3-sequence ("home", "maps", "home") was visited at least once by 1 user.
The 3-sequence ("cart", "maps", "home") was visited at least once by 1 user.

Note:

1. 3 <= N = username.length = timestamp.length = website.length <= 50
2. 1 <= username[i].length <= 10
3. 0 <= timestamp[i] <= 10^9
4. 1 <= website[i].length <= 10
5. Both username[i] and website[i] contain only lowercase characters.
6. It is guaranteed that there is at least one user who visited at least 3 websites.
7. No user visits two websites at the same time.

Notes:

After reading this question several times, I still cannot get the point of this question. Roughly it is asking for the top 3 rank of three-websites comb visited. One of the requirement is that these three website must be visited by the same person, and then it is counted as 1.

There is no much algorithm involved, and it is question for date structure.

First step, we can built up a map: the key will include the person. And we need to know all the websites the person has visited. A person may visit the same website several times but at different times, so the visiting time can also be used as one part of the key. In this way, we can record the combos composing with the same website but visited at different time.

The next step will be building all the possible three-website combos for the same person.

Then we can save this result using another map, but this time the three-website combo are the key. Thus we cannot use unordered_map if we use a string vector as the key.

We still need to know which person visits this three-website combo, so person can again be one part of the key for labeling.

After this map is finished, we just need to find the one with the largest counting.

See the code below:

vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
    int len = username.size();
    unordered_map<string,map<int,string>> data;
    for(int i=0; i<len; ++i) {
        data[username[i]][timestamp[i]] = website[i];
    }
    map<vector<string>,unordered_map<string,int>> cts;
    for(auto &d : data) {
        if(d.second.size()<3) continue;
        for(auto i=d.second.begin(); i!=d.second.end(); ++i) {
            auto j = i; j++;
            for(; j!=d.second.end(); ++j) {
                auto k = j; k++;
                for(; k!=m.second.end(); ++k) {
                    ++cts[{(*i).second,(*j).second,(*k).second}][d.first];
                }
            }
        }
    }
    vector<string> res;
    int largest = 0;
    for(auto &i : cts){
        if(i.second.size() > largest){
            res = i.first;
            largest = i.second.size();
        }
    }
    return res;
}

A good reference can be found here:

https://github.com/ScientificKnights/Leetcode-Templates-and-Examples/blob/master/code/1152.%20Analyze%20User%20Website%20Visit%20Pattern.h

Leetcode 1199: Minimum Time to Build Blocks

https://leetcode.com/contest/biweekly-contest-9/problems/minimum-time-to-build-blocks/

Notes:

My thinking to this question is using memorization (or dp if you like). There are two keys parameters: one is the un-build blocks and the other one is number of worker.

At each stage, we have two directions to go:

One is that we have w workers, then we can try assign 1 to w workers to the blocks sorted form the largest to the smallest; and we need to figure out which way is the fastest;

The other is that we can do the splitting first. The maximum times of splitting is that when the number of workers is the same as that of the un-build blocks.

But this method received TLE.  Anyway, see the code below:

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        int len = blocks.size();
        vector<vector<int>> memo(len+1, vector<int>(2*len+1, -1));
        sort(blocks.begin(), blocks.end());
        return dfs(blocks, len, 1, split, memo);
    }

private:
    int dfs(vector<int> &bs, int len, int w, int &spt, vector<vector<int>> &memo) {
        if(len<1) return 0;
        if(len <= w) return bs[len-1];
        if(memo[len][w] != -1) return memo[len][w];
        int t = INT_MAX;
        for(int i=1; i<w; ++i) {
            if(bs[len-1] >= t) break;
            t = min(t, max(bs[len-1], dfs(bs, len-i, w-i, spt, memo)));
        }
        for(int i=1; (1<<i)*w<=len*2; ++i) {
            if(spt*i >= t) break;
            t = min(t, spt*i + dfs(bs, len, w*(1<<i), spt, memo));
        }
        return memo[len][w] = t;
    }
};

After searching online, it is found that this question can be solved by using Huffman Tree algorithm. Just opposite to starting with the largest block, we can start with the smallest one.

Each step, we just need to finish the current smallest one, then updated the second smallest one by adding split time. Then continue the iteration process, until only one element remaining, which is the shortest time.

Unbelievable? right. What is the key logic? To be continued...

See the code below:

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto &b : blocks) pq.push(b);
        while(pq.size() > 1) {
            pq.pop();
            int t = pq.top();
            pq.pop();
            pq.push(t + split);
        }
        return pq.top();
    }
};

562 Leetcode: Longest Line of Consecutive One in Matrix

https://leetcode.com › problems › longest-line-of-consecutive-one-in-matrix

Notes:

This question can be solved by dp. (there're other ways of course, counting ones in four directions.., but it is not easy to convert the indexes in diagonal and anti-diagonal directions..., we also need to consider how to label the visiting condition of each 1 node, in order to check each direction of the 1 node only once.)

Let us focus on dp, since it is very straightforward. There are four directions that we need to consider, so we need three 2-D matrix, or one 3-D matrix used as the dp matrix.

dp[i][j][k] representing the maximum number of ones ending with the element at (i, j). k = 0, 1, 2, 3 are for horizontal, vertical, diagonal, and anti-diagonal directions, respectively.

If M[i][j] == 0, we just need to set all dp[i][j][k] = 0; or nothing if they are initialized as 0;

If M[i][j] == 1, we just need to update all dp[i][j][k] by 1 from the previous ones. And we need to save the largest one as the local optimal solution.

After scanning the whole matrix, we should obtained the largest of all the local maximums which is the global maximum.

See the code below:

class Solution {
public:
    int longestLine(vector<vector<int>>& M) {
        if (M.empty() || M[0].empty()) return 0;
        int m = M.size(), n = M[0].size(), res = 0;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(4)));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (M[i][j] == 0) continue;
                for (int k = 0; k < 4; ++k) dp[i][j][k] = 1;
                if (j > 0) dp[i][j][0] += dp[i][j - 1][0]; // horizonal
                if (i > 0) dp[i][j][1] += dp[i - 1][j][1]; // vertical
                if (i > 0 && j < n - 1) dp[i][j][2] += dp[i - 1][j + 1][2]; // diagonal
                if (i > 0 && j > 0) dp[i][j][3] += dp[i - 1][j - 1][3]; // anti-diagonal
                res = max(res, max(dp[i][j][0], dp[i][j][1]));
                res = max(res, max(dp[i][j][2], dp[i][j][3]));
            }
        }
        return res;
    }
};

Leetcode 1066: Campus Bikes II

https://leetcode.com › problems › campus-bikes-ii

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

1. 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
2. All worker and bike locations are distinct.
3. 1 <= workers.length <= bikes.length <= 10

Notes:

It is said that this question is from one of the onsite interviews of Google company.

The naive method is that we try all the possible combinations using backtracking, but apparently we re-calculate a lot of sub-states.

In order to better see this, let us consider two cases. One is that we let worker 1 choose bike 1, and worker 2 pick bike 2, then the rest workers choose the rest bikes (sub-state 1). The other case is that, worker 1 chooses bike 2, and worker 2 chooses bike 1, then the rest workers choose the rest bikes (sub-state 2). Apparently, sub-state 1 is the same as sub-state 2, so we just need to calculate it once, and then re-use the result directly if need it again.

To this question, bit mapping is a naturally choice to label the state. 0 represents un-used and 1 represents used. (The very small values of the number of both workers and bikes are good indicators to this.)

Since both the number of the workers and bikes are no larger than 10, an integer (32 bits) should be enough to record it. Thus, we can use two integers to memorize the combination conditions between workers and bikes. In the following code, integer state1 is for workers, and integer state2 for bikes.

Suppose there are N workers and M bikes, the total possible states is (2^N)*(2^M). So the space  complexity is O((2^N)*(2^M)). Since we only calculate once for each state, the time complexity is the same as the space complexity.

[update on 10/07/2019]: The time complexity is O(N*M*2^N*2^M), since for each substate calculation, or local minimum, we have run all the possible matches between workers and bikes.]

See the code below:

class Solution {
public:
    int minManHaDis(vector<vector<int>> &ws, vector<vector<int>> &bs) {
        int m = ws.size(), n = bs.size();//m <= n based on the question;
        vector<vector<int>> memo(1<<m, vector<int>(1<<n, -1));
        int state1 = 0, state2 = 0;
        int res = dfs(0, ws, state1, bs, state2, memo);
        //cout<<res<<endl;
        return res;
    }

private:
    int dfs(int i, vector<vector<int>> &ws, int st1, vector<vector<int>> &bs, int st2, vector<vector<int>> &memo) {
        if(i==ws.size()) return 0;//all the workers are assigned;
        if(memo[st1][st2] != -1) return memo[st1][st2];//calculated;
        int min_dis = INT_MAX;
        for(int j = 0; j < bs.size(); ++j) {//try all the bikes;
            if((st2>>j) & 1) continue;//if the bike is used;
            int one_dis = abs(ws[i][0] - bs[j][0]) + abs(ws[i][1] - bs[j][1]);
            one_dis += dfs(i+1, ws, st1 | (1<<i), bs, st2 | (1<<j), memo);//total dis in this case;
            min_dis = min(min_dis, one_dis);//min distance;
        }
        return memo[st1][st2] = min_dis;//memorize min distance;
    }
};

Leetcode 325: Maximum Size Subarray Sum Equals K

https://leetcode.com › problems › maximum-size-subarray-sum-equals-k

Notes:

This question can be a very good interview question due to the follow up. The basic idea is that using a hash table to record the index when one unique sum shows up.

if sum[i to j] = sum[0 to j] - sum[0 to i-1] = k, then we just need to check whether (sum[0 to j] - k) is already observed or not, which is sum[0 to i-1]. Thus, we can run this in O(N).

See the code below:

class Solution {
public:
    int maxSubArrayLen(vector<int> &nums, int k) {
        int res = 0, sum = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); ++i) {
            sum += nums[i];
            if(sum == k) res = max(res, i + 1);
            else if (mp.count(sum-k)) res = max(res, i - mp[sum-k]);
            if(!mp.count(sum)) mp[sum] = i;
        }
        return res;
    }
};

Leetcode 276: Paint Fence

https://leetcode.com › problems › paint-fence

Notes:

A nice dp problem.

Let us start with some small number:

at n = 1, there are k ways;

now move on the the second one. If we choose to the same color as before, then there are a = k ways (with the last two having the same colors); if we choose a different color, then there are b = k*(k-1) (with the last two having different colors).

now is the key: let's move on the 3rd one.

If we are at the first case with the last two having the same color, then we have to choose a different color, which gives a*(k-1) ways, now it becomes the case with the last two elements having different colors;

if we are at the second case with the last two having different colors. we have two choices:

1): choose a color which is the same as the last one, and there are b ways to do this; and now it becomes the case with the last two elements with the same color;

2): choose a different color from that of the last element, and there are b*(k-1) ways to do this. After this, it is still the same case as before;

so we can derive the formula as the following:

a is the ways with the last two having the same color;
b is the ways with the last two having different colors.

So for the first place, a = 0, b = k; then

t = b;//save b;
b = (b + a) * (k-1)
a = b;

So this question can be easily to modify to ask: how about at most 3 (or n) adjacent fences having the same color?

See the code below:

class Solution {
public:
    int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0, diff = k;
        for (int i = 2; i <= n; ++i) {
            int t = diff;
            diff = (same + diff) * (k - 1);
            same = t;
        }
        return same + diff;
    }
};

Leetcode 1183: Maximum Number of Ones

https://leetcode.com/problems/maximum-number-of-ones/description/

Notes:

One of the solution is straightforward: we just need to check both horizontal and vertical directions. If the square sub-matrix can be repeated completely, then it simply repeats all the 1s. So the difficulty part is when there are remainders.

For remainders, we need to consider both directions too. Below is a very good resource on how to deal with the remainders.

https://leetcode.com/problems/maximum-number-of-ones/discuss/377033/C++-O(1)-solution-with-explanation-Totally-intuitive



For the remainders partial squares in the two directions, we can essentially "overlap them", as shown in the below figure. The key logic is listed below:

1): If m (the maxOnes) is no larger than lx * ly, we simple place all the 1s in that area, which will give us the maximum number of 1s. And it is (nx + ny + 1) * m;

for example, 10, 10, 4, 4.

then nx = ny = 2; lx=ly = 2. then m = 4 <= lx*ly = 4.

We just need to place the 1s as 2*2. The both vertical and horizontal partial square can repeat all the 1s. And they overlap at the bottom right corner. The overall number is (nx + ny + 1).

2): if m > lx*ly

 After placing 1s in the range I with an area of lx*ly, we still have extra 1s. Now we need to compare nx and ny: how many time are the extra 1s repreated? If nx is larger, we need to place 1s in range II first; otherwise, range III.

3): if we still have extra, we need to place the extra 1s in the unused range (II or III).

4): range IV is never used.


See the code below:

class Solution {
public:
    int maximumNumberOfOnes(int w, int h, int s, int mo) {
        int ans=0, lx=w%s, ly=h%s, nx=w/s, ny=h/s;
        ans=nx*ny*mo;
        if(mo<=lx*ly) ans+=(nx+ny+1)*mo;
        else {
            ans+=(nx+ny+1)*lx*ly;
            mo-=lx*ly;//extra 1s
            if(nx>ny) {
                if(mo<=(s-lx)*ly) ans+=(nx)*mo;
                else {
                    ans+=(s-lx)*ly*(nx);
                    mo-=(s-lx)*ly;//extra 1s
                    ans+=min(mo, (s-ly)*lx )*ny;
                }
            }
            else {
                if(mo<=(s-ly)*lx) ans+=(ny)*mo;
                else {
                    ans+=(s-ly)*lx*(ny);
                    mo-=(s-ly)*lx;//extra 1s
                    ans+=min(mo, (s-lx)*ly )*nx;
                }
            }
        }
        return ans;
    }
};

Another way to think about this question is more abstract:

https://leetcode.com/problems/maximum-number-of-ones/discuss/376911/PythonC++-Solution-with-explanation

"If we create the first square matrix, the big matrix will just be the copies of this one. (translation copies)
The value of each location in the square matrix will appear at multiple locations in the big matrix, count them.
Then assign the ones in the square matrix with more occurrences with 1."

Please see the code below:

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        int res = 0, w = width, h = height, s = sideLength, m = maxOnes;
        vector<int> ct;
        for(int i=0; i<s; ++i) {
            for(int j=0; j<s; ++j) {
                ct.push_back(((w-i-1)/s + 1)*((h-j-1)/s+1));
            }
        }
        sort(ct.begin(), ct.end(), greater<int>());
        for(int i=0; i<m; ++i) res += ct[i];
        return res;
    }
};

There is another way to implement this idea, which seems easier to understand: we just count the frequency of the occurrence of each position in the square. Then choose the top maxOnes positions to fill with 1, which gives us the most 1s in total.

See the code below:

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        int res = 0, w = width, h = height, s = sideLength, m = maxOnes;
        vector<int> ct(s*s, 0);
        for(int i=0; i<w; ++i) {
            for(int j=0; j<h; ++j) {
                int id = (i%s)*s + (j%s);
                ++ct[id];
            }
        }
        sort(ct.begin(), ct.end(), greater<int>());
        for(int i=0; i<m; ++i) res += ct[i];
        return res;
    }
};

Leetcode 1057: Campus Bikes

https://leetcode.com › problems › campus-bikes

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

Our goal is to assign a bike to each worker. Among the available bikes and workers, we choose the (worker, bike) pair with the shortest Manhattan distance between each other, and assign the bike to that worker. (If there are multiple (worker, bike) pairs with the same shortest Manhattan distance, we choose the pair with the smallest worker index; if there are multiple ways to do that, we choose the pair with the smallest bike index). We repeat this process until there are no available workers.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return a vector ans of length N, where ans[i] is the index (0-indexed) of the bike that the i-th worker is assigned to.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]
Explanation: 
Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: [0,2,1]
Explanation: 
Worker 0 grabs Bike 0 at first. Worker 1 and Worker 2 share the same distance to Bike 2, thus Worker 1 is assigned to Bike 2, and Worker 2 will take Bike 1. So the output is [0,2,1].

Note:

1. 0 <= workers[i][j], bikes[i][j] < 1000
2. All worker and bike locations are distinct.
3. 1 <= workers.length <= bikes.length <= 1000

Notes:

This question can be solved greedily.  The total size of the data points are 1000 * 1000. We need to calculate the distances between any pair of (worker, bike), then sort them based on a): distance, b): worker index; c): bike index. Then we assign the (worker, bike) pair from the left to right.

See the code below:

class Solution {
public:
    vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int m = workers.size(), n = bikes.size();
        vector<int> res(m, -1);
        vector<vector<int>> dt;
        for(int i=0; i<m; ++i) {
            for(int j=0; j<n; ++j) {
                int dis = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
                dt.push_back({dis, i, j});
            }
        }
        sort(dt.begin(), dt.end(), [](auto &a, auto &b){return a[0]<=b[0] && a[1]<=b[1] && a[2]<=b[2];});
        vector<int> assignedW(m, 0), assignedB(n, 0);
        int count = 0;
        for(auto &a : dt) {
            if(!assignedW[a[1]] && !assignedB[a[2]]) {
                res[a[1]] = a[2];
                assignedW[a[1]] = 1;
                assignedB[a[2]] = 1;
                ++count;
            }
            if(count == m) break;
        }
        return res;
    }
};