Huahua's Tech Road

花花酱 LeetCode 1105. Filling Bookcase Shelves

By zxi on June 29, 2019

We have a sequence of books: the i-th book has thickness books[i][0] and height books[i][1].

We want to place these books in order onto bookcase shelves that have total width shelf_width.

We choose some of the books to place on this shelf (such that the sum of their thickness is <= shelf_width), then build another level of shelf of the bookcase so that the total height of the bookcase has increased by the maximum height of the books we just put down. We repeat this process until there are no more books to place.

Note again that at each step of the above process, the order of the books we place is the same order as the given sequence of books. For example, if we have an ordered list of 5 books, we might place the first and second book onto the first shelf, the third book on the second shelf, and the fourth and fifth book on the last shelf.

Return the minimum possible height that the total bookshelf can be after placing shelves in this manner.

Example 1:

Input: books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
Output: 6
Explanation:
The sum of the heights of the 3 shelves are 1 + 3 + 2 = 6.
Notice that book number 2 does not have to be on the first shelf.

Constraints:

1 <= books.length <= 1000
1 <= books[i][0] <= shelf_width <= 1000
1 <= books[i][1] <= 1000

Solution: DP

dp[i] := min height of placing books[0] ~ books[i]
dp[-1] = 0
dp[j] = min{dp[i-1] + max(h[i] ~ h[j])}, 0 < i <= j, sum(w[i] ~ w[j]) <= shelf_width

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

C++

// Author: Huahua, running time: 0 ms

class Solution {

public:

int minHeightShelves(vector<vector<int>>& books, int sw) {

int n = books.size();

vector<int> dp(n, INT_MAX / 2);

for (int i = 0; i < n; ++i) {

int w = 0;

int h = 0;

for (int j = i; j < n; ++j) {

if ((w += books[j][0]) > sw) break;

h = max(h, books[j][1]);

dp[j] = min(dp[j], (i == 0 ? 0 : dp[i - 1]) + h);

}

return dp.back();

}

};

花花酱 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;

}

};