Posts published in March 2018

花花酱 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 805. Split Array With Same Average

By zxi on March 24, 2018

Problem

题目大意：问能否将一个数组分成两部分，每部分的平均值相同。

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

Solution: Search

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 771 ms

class Solution {

public:

bool splitArraySameAverage(vector<int>& A) {

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

sum = std::accumulate(A.begin(), A.end(), 0);

n = A.size();

return dfs(A, 1, 0, 0);

}

private:

int sum;

int n;

bool dfs(const vector<int>& A, int c, int s, int cur) {

if (c > A.size() / 2) return false;

for (int i = s; i < A.size(); ++i) {

cur += A[i];

if (cur * (n - c) == (sum - cur) * c) return true;

if (cur * (n - c) > (sum - cur) * c) break;

if (dfs(A, c + 1, i + 1, cur)) return true;

cur -= A[i];

}

return false;

}

};

花花酱 LeetCode 450. Delete Node in a BST

By zxi on March 24, 2018

Problem

https://leetcode.com/problems/delete-node-in-a-bst/description/

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Solution: Recursion

Time complexity: O(h)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 36 ms

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if (root == nullptr) return root;

if (key > root->val) {

root->right = deleteNode(root->right, key);

} else if (key < root->val) {

root->left = deleteNode(root->left, key);

} else {

TreeNode* new_root = nullptr;

if (root->left == nullptr) {

new_root = root->right;

} else if (root->right == nullptr) {

new_root = root->left;

} else {

// Find the min node in the right sub tree

TreeNode* parent = root;

new_root = root->right;

while (new_root->left != nullptr) {

parent = new_root;

new_root = new_root->left;

}

if (parent != root) {

parent->left = new_root->right;

new_root->right = root->right;

}

new_root->left = root->left;

}

delete root;

return new_root;

}

return root;

}

};

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

TreeNode* deleteNode(TreeNode* root, int key) {

if (root == nullptr) return root;

if (key > root->val) {

root->right = deleteNode(root->right, key);

} else if (key < root->val) {

root->left = deleteNode(root->left, key);

} else {

if (root->left != nullptr && root->right != nullptr) {

TreeNode* min = root->right;

while (min->left != nullptr) min = min->left;

root->val = min->val;

root->right = deleteNode(root->right, min->val);

} else {

TreeNode* new_root = root->left == nullptr ? root->right : root->left;

root->left = root->right = nullptr;

delete root;

return new_root;

}

return root;

}

};

花花酱 LeetCode 443. String Compression

By zxi on March 24, 2018

Problem

题目大意：对一个string进行in-place的run length encoding。

https://leetcode.com/problems/string-compression/description/

Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

After you are done modifying the input array in-place, return the new length of the array.

Follow up:
Could you solve it using only O(1) extra space?

Example 1:

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Example 2:

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Example 3:

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

Note:

All characters have an ASCII value in [35, 126].
1 <= len(chars) <= 1000.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int compress(vector<char>& chars) {

const int n = chars.size();

int p = 0;

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

int count = 1;

while (i < n && chars[i] == chars[i - 1]) { ++i; ++count; }

chars[p++] = chars[i - 1];

if (count == 1) continue;

for (char c : to_string(count))

chars[p++] = c;

}

return p;

}

};

花花酱 LeetCode 447. Number of Boomerangs

By zxi on March 24, 2018

Problem

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Solution: HashTable

For each point, compute the distance to the rest of the points and count.

if there are k points that have the same distance to current point, then there are P(k,2) = k*k-1 Boomerangs.

for example, p1, p2, p3 have the same distance to p0, then there are P(3,2) = 3 * (3-1) = 6 Boomerangs

(p1, p0, p2), (p1, p0, p3)

(p2, p0, p1), (p2, p0, p3)

(p3, p0, p1), (p3, p0, p2)

C++

// Author: Huahua

// Running time: 210 ms (beats 83.33%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

int ans = 0;

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

unordered_map<int, int> dist(points.size());

for (int j = 0; j < points.size(); ++j) {

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

++dist[dx * dx + dy * dy];

}

for (const auto& kv : dist)

ans += kv.second * (kv.second - 1);

}

return ans;

}

};

Solution 2: Sorting

dist = [1, 2, 1, 2, 1, 5]

sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1

ans = 3*(3-1) + 2 * (2 – 1) * 1 * (1 – 1) = 8

Time complexity: O(n*nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 150 ms (beats 98.52%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

const int n = points.size();

int ans = 0;

vector<int> dist(points.size());

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

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

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

dist[j] = dx * dx + dy * dy;

}

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

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

int k = 1;

while (j < n && dist[j] == dist[j - 1]) { ++j; ++k; }

ans += k * (k - 1);

}

return ans;

}

};