Posts tagged as “medium”

花花酱 LeetCode 814. Binary Tree Pruning

By zxi on April 7, 2018

Problem:

题目大意：把不含有1的节点的子树全部删除。

https://leetcode.com/problems/binary-tree-pruning/description/

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

The binary tree will have at most 100 nodes.
The value of each node will only be 0 or 1.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

TreeNode* pruneTree(TreeNode* root) {

if (!root) return root;

root->left = pruneTree(root->left);

root->right = pruneTree(root->right);

if (root->val == 1 || root->left || root->right)

return root;

delete root;

return nullptr;

}

};

Java

// Author: Huahua

// Running time: 2 ms

class Solution {

public TreeNode pruneTree(TreeNode root) {

if (root == null) return root;

root.left = pruneTree(root.left);

root.right = pruneTree(root.right);

return (root.val == 1 || root.left != null || root.right != null) ? root : null;

}

Python3

// Author: Huahua

// Running time: 36 ms

class Solution:

def pruneTree(self, root):

if not root: return root

root.left = self.pruneTree(root.left)

root.right = self.pruneTree(root.right)

return root if root.val == 1 or root.left or root.right else None

花花酱 LeetCode 807. Max Increase to Keep City Skyline

By zxi on March 24, 2018

Problem

题目大意：给你一个二维地图和每个坐标的大楼高度，求出总增高的最大值使得城市的天际线（投影）保持不变。

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

1 < grid.length = grid[0].length <= 50.
All heights grid[i][j] are in the range [0, 100].
All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Solution: Greedy

Find the max of each row and column, increase the height of building at i,j to min(max_row[i], max_col[j]).

Time Complexity: O(m*n)

Space complexity: O(m+n)

C++

// Author: Huahua

class Solution {

public:

int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {

int m = grid.size();

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

vector<int> x(n, 0);

vector<int> y(n, 0);

for (int i = 0; i < m; ++i)

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

x[j] = max(x[j], grid[i][j]);

y[i] = max(y[i], grid[i][j]);

}

int ans = 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

ans += min(x[i], y[j]) - grid[i][j];

return ans;

}

};

花花酱 LeetCode 560. Subarray Sum Equals K

By zxi on March 22, 2018

Problem

题目大意：给你一个数组，问有多少子数组的和为k。

https://leetcode.com/problems/subarray-sum-equals-k/description/

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution -1: Brute Force

For every pair of i,j, check sum(nums[i:j]) in O(j-i) = O(n)

Time complexity: O(n^3) TLE

Space complexity: O(1)

Solution 0: Brute Force + Prefix sun

Precompute the prefix sum and check sum of nums[i:j] in O(1)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 490 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> sums(n + 1, 0);

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

sums[i] = sums[i - 1] + nums[i - 1];

int ans = 0;

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

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

if (sums[j + 1] - sums[i] == k) ++ans;

return ans;

}

};

Solution 1: Running Prefix sum

Keep tracking the prefix sums and their counts.

s -> count: how many arrays nums[0:j] (j < i) that has sum of s

cur_sum = sum(nums[0:i])

check how many arrays nums[0:j] (j < i) that has sum (cur_sum – k)

then there are the same number of arrays nums[j+1: i] that have sum k.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

if (nums.empty()) return 0;

unordered_map<int, int> counts{{0,1}};

int cur_sum = 0;

int ans = 0;

for (const int num : nums) {

cur_sum += num;

ans += counts[cur_sum - k];

++counts[cur_sum];

}

return ans;

}

};

花花酱 LeetCode 554. Brick Wall

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/brick-wall/description/

题目大意：从小到下切一刀，最少会切到多少块砖。

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

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

Note:

The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

Solution: HashTable

Count boundaries, cut at the location with most common boundaries.

Time complexity: O(|bricks|)

Space complexity: O(|bricks|)

C++

// Author: Huahua

// Running time: 42 ms

class Solution {

public:

int leastBricks(vector<vector<int>>& wall) {

unordered_map<int, int> count;

int max_count = 0;

for (const auto& bricks : wall) {

int s = 0;

for (int i = 0; i < bricks.size() - 1; ++i) {

s += bricks[i];

max_count = max(max_count, ++count[s]);

}

return wall.size() - max_count;

}

};

花花酱 LeetCode 553. Optimal Division

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/optimal-division/description/

题目大意：给你一个连除的表达式，让你加一些括号使得表达式的值最大。

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant, 
since they don't influence the operation priority. So you should return "1000/(100/10/2)". 

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

Solution: Math

For: X1/X2/X3/…/Xn, X1/(X2/X3/…/Xn) > X1/X2/(X3/…/Xn) > X1/X2/X3/(…/Xn)

X1/(X2/X3/…/Xn) is the max value.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

string optimalDivision(vector<int>& nums) {

string ans = to_string(nums[0]);

if (nums.size() == 1) return ans;

else if (nums.size() == 2) return ans + "/" + to_string(nums[1]);

ans += "/(" + to_string(nums[1]);

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

ans += "/" + to_string(nums[i]);

ans += ")";

return ans;

}

};