花花酱 LeetCode 561. Array Partition I

By zxi on August 16, 2018

Problem

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), …, (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

Solution 1: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

std::sort(nums.begin(), nums.end());

int ans = 0;

for(int i = 0; i < nums.size(); i += 2)

ans += nums[i];

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n + max(nums) – min(nums))

Space complexity: O(max(nums) – min(nums))

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

const int max_val = *max_element(begin(nums), end(nums));

const int min_val = *min_element(begin(nums), end(nums));

const int offset = -min_val;

vector<int> c(max_val - min_val + 1);

for (int num : nums)

++c[num + offset];

int ans = 0;

int index = 0;

int n = min_val;

while (n <= max_val) {

if (c[n + offset] == 0) {

++n;

continue;

}

ans += (++index & 1) ? n : 0;

--c[n + offset];

}

return ans;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 561. Array Partition I

Problem

Solution 1: Sorting

Solution 2: HashTable

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