Huahua’s Tech Road

花花酱 LeetCode 1094. Car Pooling

By zxi on June 22, 2019

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true

Example 4:

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

Solution1: Min heap

Sort events by location

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool carPooling(vector<vector<int>>& trips, int capacity) {

priority_queue<int> q;

for (const auto& trip : trips) {

int pick_up = -((trip[1] << 10) | (1 << 9) | trip[0]);

int drop_off = -((trip[2] << 10) | trip[0]);

q.push(pick_up);

q.push(drop_off);

}

while (q.size()) {

int key = -q.top(); q.pop();

int sign = ((key >> 9) & 1) ? 1: -1;

int num = key & 0xFF;

if ((capacity -= sign * num) < 0)

return false;

}

return true;

}

};

Solution 2: Preprocessing

Time complexity: O(n)
Space complexity: O(1000)

C++

// Author: Huahua

class Solution {

public:

bool carPooling(vector<vector<int>>& trips, int capacity) {

vector<int> d(1001);

for (const auto& trip : trips) {

d[trip[1]] -= trip[0];

d[trip[2]] += trip[0];

}

for (const int c : d)

if ((capacity += c) < 0) return false;

return true;

}

};

花花酱 LeetCode 23. Merge k Sorted Lists

By zxi on June 22, 2019

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution 1: Min heap

Time complexity: O(nklogk)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

ListNode dummy(0);

ListNode *tail = &dummy;

auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; };

priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);

for (ListNode* list : lists)

if (list) q.push(list);

while (!q.empty()) {

tail->next = q.top(); q.pop();

tail = tail->next;

if (tail->next) q.push(tail->next);

}

return dummy.next;

}

};

Solution 2: Merge Sort

Time complexity: O(nklogk)
Space complexity: O(logk)

C++

// Author: Huahua

class Solution {

public:

ListNode* mergeKLists(vector<ListNode*>& lists) {

return merge(lists, 0, lists.size() - 1);

}

private:

ListNode* merge(vector<ListNode*>& lists, int l, int r) {

if (l > r) return nullptr;

if (l == r) return lists[l];

if (l + 1 == r) return mergeTwoLists(lists[l], lists[r]);

int m = l + (r - l) / 2;

auto l1 = merge(lists, l, m);

auto l2 = merge(lists, m + 1, r);

return mergeTwoLists(l1, l2);

}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

if (l1) tail->next = l1;

if (l2) tail->next = l2;

return dummy.next;

}

};

花花酱 LeetCode 1092. Shortest Common Supersequence

By zxi on June 16, 2019

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywherefrom T) results in the string S.)

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a substring of "cabac" because we can delete the first "c".
str2 = "cab" is a substring of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Note:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of lowercase English letters.

Solution: LCS

Find the LCS (longest common sub-sequence) of two strings, and insert unmatched characters into the LCS.

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua, running time: 16 ms, 15.3 MB

class Solution {

public:

string shortestCommonSupersequence(string str1, string str2) {

int l1 = str1.length();

int l2 = str2.length();

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

for (int i = 1; i <= l1; ++i)

for (int j = 1; j <= l2; ++j)

dp[i][j] = str1[i - 1] == str2[j - 1] ?

1 + dp[i - 1][j - 1] :

max(dp[i - 1][j], dp[i][j - 1]);

deque<char> ans;

while (l1 || l2) {

char c;

if (l1 == 0) c = str2[--l2];

else if (l2 == 0) c = str1[--l1];

else if (str1[l1 - 1] == str2[l2 - 1]) c = str1[--l1] = str2[--l2];

else if (dp[l1 - 1][l2] == dp[l1][l2]) c = str1[--l1];

else if (dp[l1][l2 - 1] == dp[l1][l2]) c = str2[--l2];

ans.push_front(c);

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 1073. Adding Two Negabinary Numbers

By zxi on June 6, 2019

Given two numbers arr1 and arr2 in base -2, return the result of adding them together.

Each number is given in array format: as an array of 0s and 1s, from most significant bit to least significant bit. For example, arr = [1,1,0,1] represents the number (-2)^3 + (-2)^2 + (-2)^0 = -3. A number arr in array format is also guaranteed to have no leading zeros: either arr == [0] or arr[0] == 1.

Return the result of adding arr1 and arr2 in the same format: as an array of 0s and 1s with no leading zeros.

Example 1:

Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1]
Output: [1,0,0,0,0]
Explanation: arr1 represents 11, arr2 represents 5, the output represents 16.

Note:

1 <= arr1.length <= 1000
1 <= arr2.length <= 1000
arr1 and arr2 have no leading zeros
arr1[i] is 0 or 1
arr2[i] is 0 or 1

Solution: Simulation

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 8 ms, 9.2 MB

class Solution {

public:

vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {

int i = arr1.size();

int j = arr2.size();

int carry = 0;

vector<int> ans;

while (i || j || carry) {

int sum = (i ? arr1[--i] : 0) + (j ? arr2[--j] : 0) + carry;

ans.push_back(sum & 1);

carry = -(sum >> 1);

}

while (ans.back() == 0 && ans.size() > 1) ans.pop_back();

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 1054. Distant Barcodes

By zxi on May 28, 2019

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Example 1:

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

Example 2:

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

Note:

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

Soluton: Sorting

Sort the element by their frequency in descending order. Fill the most frequent element first in even positions, if reach the end of the array, start from position 1 then 3, 5, …

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, 216 ms, 18.2 MB

class Solution {

public:

vector<int> rearrangeBarcodes(vector<int>& barcodes) {

const int n = barcodes.size();

vector<int> f(10001);

for (int v : barcodes) ++f[v];

sort(begin(barcodes), end(barcodes), [&](const int a, const int b){

return f[a] == f[b] ? a > b : f[a] > f[b];

});

vector<int> ans(n);

int pos = 0;

for (int v : barcodes) {

ans[pos] = v;

if ((pos += 2) >= n) pos = 1;

}

return ans;

}

};

Solution 2: Find the most frequent

Actually, we only need to find the most frequent element and put in the even positions, then put the rest of the groups of elements in any order.

e.g. [1, 1, 2, 2, 2, 2, 2, 3, 4]
Can be
5*2 [2 – 2 – 2 – 2 – 2]
4*1 [2 4 2 – 2 – 2 – 2]
3*1 [2 4 2 3 2 – 2 – 2]
1*2 [ 2 3 2 3 2 1 2 1 2]

if we start with any other groups rather than 2, if will become:
[3 2 2 – 2 – 2 – 2 ] which is wrong…

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 172 ms (99.89%), 18 MB (< 100%)

class Solution {

public:

vector<int> rearrangeBarcodes(vector<int>& barcodes) {

constexpr int kMaxV = 10001;

const int n = barcodes.size();

vector<int> f(kMaxV);

int max_f = 0;

int max_v = 0;

for (int v : barcodes)

if (++f[v] > max_f) {

max_f = f[v];

max_v = v;

}

vector<int> ans(n);

int pos = 0;

while (f[max_v]-- > 0) {

ans[pos] = max_v;

if ((pos += 2)>= n) pos = 1;

}

for (int v = 1; v < kMaxV; ++v) {

while (f[v]-- > 0) {

ans[pos] = v;

if ((pos += 2) >= n) pos = 1;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1094. Car Pooling

Solution1: Min heap

C++

Solution 2: Preprocessing

C++

花花酱 LeetCode 23. Merge k Sorted Lists

Solution 1: Min heap

C++

Solution 2: Merge Sort

C++

花花酱 LeetCode 1092. Shortest Common Supersequence

Solution: LCS

C++

花花酱 LeetCode 1073. Adding Two Negabinary Numbers

Solution: Simulation

C++

花花酱 1054. Distant Barcodes

Soluton: Sorting

C++

Solution 2: Find the most frequent

C++