花花酱 LeetCode 566. Reshape the Matrix

By zxi on August 16, 2018

Problem

In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.

You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

Example 1:

Input: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
Output: 
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.

Example 2:

Input: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
Output: 
[[1,2],
 [3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.

Note:

The height and width of the given matrix is in range [1, 100].
The given r and c are all positive.

Solution1: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {

if (nums.size() == 0) return nums;

int m = nums.size();

int n = nums[0].size();

if (m * n != r * c) return nums;

// new matrix r*c

vector<vector<int>> ans(r, vector<int>(c));

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

int src_y = i / n;

int src_x = i % n;

int dst_y = i / c;

int dst_x = i % c;

ans[dst_y][dst_x] = nums[src_y][src_x];

}

return ans;

}

};

花花酱 LeetCode 174. Dungeon Game

By zxi on August 16, 2018

Problem

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight’s minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Note:

The knight’s health has no upper bound.
Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Solution: DP

Time complexity: O(mn)

Space complexity: O(mn) -> O(n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int calculateMinimumHP(vector<vector<int>>& dungeon) {

const int m = dungeon.size();

const int n = dungeon[0].size();

// hp[y][x]: min hp required to reach bottom right (P).

vector<vector<int>> hp(m + 1, vector<int>(n + 1, INT_MAX));

hp[m][n - 1] = hp[m - 1][n] = 1;

for (int y = m - 1; y >= 0; --y)

for (int x = n - 1; x >= 0; --x)

hp[y][x] = max(1, min(hp[y + 1][x], hp[y][x + 1]) - dungeon[y][x]);

return hp[0][0];

}

};

O(n) space

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int calculateMinimumHP(vector<vector<int>>& dungeon) {

const int m = dungeon.size();

const int n = dungeon[0].size();

// hp[y][x]: min hp required to reach bottom right (P).

vector<int> hp(n + 1, INT_MAX);

hp[n - 1] = 1;

for (int y = m - 1; y >= 0; --y)

for (int x = n - 1; x >= 0; --x)

hp[x] = max(1, min(hp[x], hp[x + 1]) - dungeon[y][x]);

return hp[0];

}

};

花花酱 LeetCode 404. Sum of Left Leaves

By zxi on August 16, 2018

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int sumOfLeftLeaves(TreeNode* root) {

if (!root) return 0;

if (root->left && !root->left->left && !root->left->right)

return root->left->val + sumOfLeftLeaves(root->right);

return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

}

};

Iterative

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int sumOfLeftLeaves(TreeNode* root) {

if (!root) return 0;

queue<TreeNode*> q;

q.push(root);

int sum = 0;

while (!q.empty()) {

TreeNode* n = q.front();

q.pop();

TreeNode* l = n->left;

if (l) {

if (!l->left && !l->right)

sum += l->val;

else

q.push(l);

}

if (n->right) q.push(n->right);

}

return sum;

}

};

花花酱 LeetCode 455. Assign Cookies

By zxi on August 15, 2018

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 g_i, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s_j. If s_j >= g_i, 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:

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:

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.

Solution: Greedy + Two Pointers

Time complexity: O(mlogm + nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int findContentChildren(vector<int>& g, vector<int>& s) {

sort(begin(g), end(g));

sort(begin(s), end(s));

int ans = 0;

int j = 0;

for (int i = 0; i < g.size(); ++i) {

while (j < s.size() && s[j] < g[i]) {

++j;

}

if (j < s.size()) {

++ans;

++j;

continue;

}

return ans;

}

};

花花酱 LeetCode 887. Super Egg Drop

By zxi on August 13, 2018

Problem

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1 <= K <= 100
1 <= N <= 10000

Solution 1: Recursion with Memorization (TLE)

dp[k][n] := min number of moves to test n floors with k eggs.

Base cases:

dp[0][n] = 0 # no eggs left.
dp[1][n] = n # one egg, need to test every floor.

Transition:

dp[k][n] = min(1 + max(dp[k][i – 1], dp[k – 1][n – i])) 1 <= i <= n

Time complexity: O(k*n^2)

Space complexity: O(k*n)

// Author: Huahua

// Running time: TLE (69/121 passed)

class Solution {

public:

int superEggDrop(int K, int N) {

m_ = vector<vector<int>>(K + 1, vector<int>(N + 1, INT_MIN));

return dp(K, N);

}

private:

// m[i][j] := min moves of i eggs and j floors

vector<vector<int>> m_;

int dp(int k, int n) {

if (k <= 0) return 0;

if (k == 1) return n;

if (n <= 1) return n;

if (m_[k][n] != INT_MIN) return m_[k][n];

int ans = INT_MAX;

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

ans = min(ans, 1 + max(dp(k - 1, i - 1), // broken at floor i, need to test i - 1 floors using k - 1 eggs.

dp(k, n - i))); // unbroken at floor i, need to test n - i floors using k eggs.

return m_[k][n] = ans;

}

};

Solution 2: Solution 1 + Binary Search

Time complexity: O(k*n*logn)

Space complexity: O(k*n)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int superEggDrop(int K, int N) {

m_ = vector<vector<int>>(K + 1, vector<int>(N + 1, INT_MIN));

return dp(K, N);

}

private:

// m[i][j] := min moves of i eggs and j floors

vector<vector<int>> m_;

int dp(int k, int n) {

if (k <= 0) return 0;

if (k == 1) return n;

if (n <= 1) return n;

if (m_[k][n] != INT_MIN) return m_[k][n];

// broken[i] = dp(k - 1, i - 1) is incresing with i.

// unbroken[i] = dp(k, n - i) is decresing with i.

// dp[k][n] = 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n

// find the smallest i such that broken[i] >= unbroken[i],

// which minimizes max(broken[i], unbroken[i]).

int l = 1;

int r = n + 1;

while (l < r) {

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

int broken = dp(k - 1, m - 1);

int unbroken = dp(k, n - m);

if (broken >= unbroken)

r = m;

else

l = m + 1;

}

return m_[k][n] = 1 + dp(k - 1, l - 1);

}

};

Huahua's Tech Road

花花酱 LeetCode 566. Reshape the Matrix

Problem

Solution1: Brute Force

花花酱 LeetCode 174. Dungeon Game

Problem

Solution: DP

花花酱 LeetCode 404. Sum of Left Leaves

Solution: Recursion

花花酱 LeetCode 455. Assign Cookies

Problem

Solution: Greedy + Two Pointers

花花酱 LeetCode 887. Super Egg Drop

Problem

Solution 1: Recursion with Memorization (TLE)

Solution 2: Solution 1 + Binary Search