花花酱 LeetCode 655. Print Binary Tree

By zxi on August 17, 2018

Problem

Print a binary tree in an m*n 2D string array following these rules:

The row number m should be equal to the height of the given binary tree.
The column number n should always be an odd number.
The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
Each unused space should contain an empty string "".
Print the subtrees following the same rules.

Example 1:

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

Example 2:

Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

Example 3:

Input:
      1
     / \
    2   5
   / 
  3 
 / 
4 
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

Note: The height of binary tree is in the range of [1, 10].

Solution: Recursion

Compute the layers h of the tree.

shape of the output matrix: h * w (w = 2^h – 1)

pre-order to fill the output matrix

first layer’s root: y1 = 0, x1 = (l1 + r1) / 2 = (0 + w – 1) / 2 (center)

first layer’s left child (2nd layer): y2 = 1, x2 = (l2 + r2) = (l1 + (x1 – 1)) / 2 (center of the left half)

first layer’s right child(2nd layer): y1 = 2, x2 = (l2′ + r2′) = ((x1+1) + r1) / 2 (center of the right half)

…

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<vector<string>> printTree(TreeNode* root) {

int h = getHeight(root);

int w = (1 << h) - 1; // 2 ^ h - 1

vector<vector<string>> ans(h, vector<string>(w, ""));

fill(root, ans, 0, 0, w - 1);

return ans;

}

private:

int getHeight(TreeNode* root) {

if (!root) return 0;

return max(getHeight(root->left), getHeight(root->right)) + 1;

}

void fill(TreeNode* root, vector<vector<string>>& ans, int h, int l, int r){

if (!root) return;

int mid = (l + r) / 2;

ans[h][mid] = std::to_string(root->val);

fill(root->left, ans, h + 1, l, mid - 1);

fill(root->right, ans, h + 1, mid + 1, r);

}

};

Python3

"""

Author: Huahua

Running time: 44 ms

"""

class Solution:

def printTree(self, root):

def height(root):

if not root: return 0

return max(height(root.left), height(root.right)) + 1

def fill(root, h, l, r):

if not root: return

mid = (l + r) // 2

m[h][mid] = str(root.val)

if root.left: fill(root.left, h + 1, l, mid - 1)

if root.right: fill(root.right, h + 1, mid + 1, r)

h = height(root)

w = 2**h - 1

m = [[""] * w for _ in range(h)]

fill(root, 0, 0, w - 1)

return m

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

}

};

Huahua's Tech Road

花花酱 LeetCode 655. Print Binary Tree

Problem

Solution: Recursion

C++

Python3

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