Posts published in July 2018

花花酱 LeetCode 875. Koko Eating Bananas

By zxi on July 22, 2018

Problem

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

Solution: Binary Search

search for the smallest k [1, max_pile_height] such that eating time h <= H.

Time complexity: O(nlogh)

Space complexity: O(1)

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

int minEatingSpeed(vector<int>& piles, int H) {

int l = 1;

int r = *max_element(begin(piles), end(piles)) + 1;

while (l < r) {

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

int h = 0;

for (int p : piles)

h += (p + m - 1) / m;

if (h <= H)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 874. Walking Robot Simulation

By zxi on July 22, 2018

Problem

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 60 ms

class Solution {

public:

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {

int x = 0;

int y = 0;

int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // WNES

int d = 1;

unordered_map<int, unordered_set<int>> o;

for (const auto obstacle : obstacles)

o[obstacle[0]].insert(obstacle[1]);

int ans = 0;

for (int c : commands) {

if (c == -2)

d = (d - 1 + 4) % 4;

else if (c == -1)

d = (d + 1) % 4;

else {

while (c--) {

int tx = x + dirs[d][0];

int ty = y + dirs[d][1];

if (o.count(tx) && o.at(tx).count(ty))

break;

x = tx;

y = ty;

ans = max(ans, x * x + y * y);

}

return ans;

}

};

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

By zxi on July 22, 2018

Problem

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:

Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Solution 1: DP

C++

// Author: Huahua

// Running time: 68 ms

// w/ Hashtable

// Time complexity: O(n^2)

// Space complexity: O(n^2)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_map<int, int> m;

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

m[A[i]] = i;

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break; // pruning 168 ms -> 68 ms

auto it = m.find(a_i);

if (it == end(m)) continue;

int i = it->second;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 96 ms

// w / Binary Search

// Time complexity: O(n^2logn)

// Space complexity: O(n)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break;

auto it = lower_bound(begin(A), begin(A) + j, a_i);

int i = it - begin(A);

if (A[i] != a_i) continue;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n^3)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 172 ms

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_set<int> m(begin(A), end(A));

int ans = 0;

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

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

int a = A[i];

int b = A[j];

int c = a + b;

int l = 2;

while (m.count(c)) {

a = b;

b = c;

c = a + b;

ans = max(ans, ++l);

}

return ans;

}

};

花花酱 LeetCode 872. Leaf-Similar Trees

By zxi on July 21, 2018

Problem

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes.

Solution: Recursion

Time complexity: O(n1 + n2)

Space complexity: O(n1 + n2)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool leafSimilar(TreeNode* root1, TreeNode* root2) {

vector<int> leafs1;

vector<int> leafs2;

getLeafs(root1, leafs1);

getLeafs(root2, leafs2);

return leafs1 == leafs2;

}

private:

void getLeafs(TreeNode* root, vector<int>& leafs) {

if (root == nullptr) return;

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

leafs.push_back(root->val);

getLeafs(root->left, leafs);

getLeafs(root->right, leafs);

}

};

Python

"""

Author: Huahua

Running time: 24 ms

"""

class Solution(object):

def leafSimilar(self, root1, root2):

def getLeafs(root):

if not root: return []

if not root.left and not root.right: return [root.val]

return getLeafs(root.left) + getLeafs(root.right)

return getLeafs(root1) == getLeafs(root2)

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

By zxi on July 20, 2018

Problem

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.

Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

0 < s1.length, s2.length <= 1000.
All elements of each string will have an ASCII value in [97, 122].

Solution: DP

Time complexity: O(l1 * l2)

Space complexity: O(l1 * l2)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int minimumDeleteSum(string s1, string s2) {

const int l1 = s1.length();

const int l2 = s2.length();

// dp[i][j] := min delete sum of (s1.substr(0, i), s2.substr(0, j))

vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));

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

dp[i][0] = dp[i - 1][0] + s1[i - 1];

for (int j = 1; j <= l2; ++j)

dp[0][j] = dp[0][j - 1] + s2[j - 1];

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

for (int j = 1; j <= l2; ++j)

if (s1[i - 1] == s2[j - 1])

// keep s1[i - 1] and s2[j - 1]

dp[i][j] = dp[i - 1][j - 1];

else

dp[i][j] = min(dp[i - 1][j] + s1[i - 1], // delete s1[i - 1]

dp[i][j - 1] + s2[j - 1]); // delete s2[j - 1]

return dp[l1][l2];

}

};

Solution2: Recursion + Memorization

Time complexity: O(l1 * l2)

Space complexity: O(l1 * l2)

C++

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

int minimumDeleteSum(string s1, string s2) {

const int l1 = s1.length();

const int l2 = s2.length();

m_ = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, INT_MAX));

return dp(s1, l1, s2, l2);

}

private:

int dp(const string& s1, int i, const string& s2, int j) {

if (i == 0 && j == 0) return 0;

if (m_[i][j] != INT_MAX) return m_[i][j];

if (i == 0) // s1 is empty.

return m_[i][j] = dp(s1, i, s2, j - 1) + s2[j - 1];

if (j == 0) // s2 is empty

return m_[i][j] = dp(s1, i - 1, s2, j) + s1[i - 1];

if (s1[i - 1] == s2[j - 1]) // skip s1[i-1] / s2[j-1]

return m_[i][j] = dp(s1, i - 1, s2, j - 1);

return m_[i][j] = min(dp(s1, i - 1, s2, j) + s1[i - 1], // del s1[i-1]

dp(s1, i, s2, j - 1) + s2[j - 1]); // del s2[j-1]

}

vector<vector<int>> m_;

};

Posts published in July 2018

花花酱 LeetCode 875. Koko Eating Bananas

Problem

Solution: Binary Search

花花酱 LeetCode 874. Walking Robot Simulation

Problem

Solution: Simulation

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

Problem

<img class="alignnone size-full wp-image-3274" src="http://zxi.mytechroad.com/blog/wp-content/uploads/2018/07/873-ep210.png" alt="" width="960" height="540"/>

Solution 1: DP

C++

C++ V2

Solution 2: HashTable

C++

花花酱 LeetCode 872. Leaf-Similar Trees

Problem

Solution: Recursion

花花酱 LeetCode 712. Minimum ASCII Delete Sum for Two Strings

Problem

Solution: DP

Solution2: Recursion + Memorization

Related Problems