花花酱 LeetCode 887. Super Egg Drop

By zxi on August 13, 2018

Problem

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1 <= K <= 100
1 <= N <= 10000

Solution 1: Recursion with Memorization (TLE)

dp[k][n] := min number of moves to test n floors with k eggs.

Base cases:

dp[0][n] = 0 # no eggs left.
dp[1][n] = n # one egg, need to test every floor.

Transition:

dp[k][n] = min(1 + max(dp[k][i – 1], dp[k – 1][n – i])) 1 <= i <= n

Time complexity: O(k*n^2)

Space complexity: O(k*n)

// Author: Huahua

// Running time: TLE (69/121 passed)

class Solution {

public:

int superEggDrop(int K, int N) {

m_ = vector<vector<int>>(K + 1, vector<int>(N + 1, INT_MIN));

return dp(K, N);

}

private:

// m[i][j] := min moves of i eggs and j floors

vector<vector<int>> m_;

int dp(int k, int n) {

if (k <= 0) return 0;

if (k == 1) return n;

if (n <= 1) return n;

if (m_[k][n] != INT_MIN) return m_[k][n];

int ans = INT_MAX;

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

ans = min(ans, 1 + max(dp(k - 1, i - 1), // broken at floor i, need to test i - 1 floors using k - 1 eggs.

dp(k, n - i))); // unbroken at floor i, need to test n - i floors using k eggs.

return m_[k][n] = ans;

}

};

Solution 2: Solution 1 + Binary Search

Time complexity: O(k*n*logn)

Space complexity: O(k*n)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int superEggDrop(int K, int N) {

m_ = vector<vector<int>>(K + 1, vector<int>(N + 1, INT_MIN));

return dp(K, N);

}

private:

// m[i][j] := min moves of i eggs and j floors

vector<vector<int>> m_;

int dp(int k, int n) {

if (k <= 0) return 0;

if (k == 1) return n;

if (n <= 1) return n;

if (m_[k][n] != INT_MIN) return m_[k][n];

// broken[i] = dp(k - 1, i - 1) is incresing with i.

// unbroken[i] = dp(k, n - i) is decresing with i.

// dp[k][n] = 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n

// find the smallest i such that broken[i] >= unbroken[i],

// which minimizes max(broken[i], unbroken[i]).

int l = 1;

int r = n + 1;

while (l < r) {

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

int broken = dp(k - 1, m - 1);

int unbroken = dp(k, n - m);

if (broken >= unbroken)

r = m;

else

l = m + 1;

}

return m_[k][n] = 1 + dp(k - 1, l - 1);

}

};

花花酱 LeetCode 889. Spiral Matrix III

By zxi on August 13, 2018

Problem

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

Solution: Simulation

We can find out the moving sequence is ESWWNNEEESSSWWWWNNNN.

The pattern is 1,1,2,2,3,3,4,4,… steps in one direction, and turn right for 90 degrees.

directions are E,S,W,N,E,S,W,N…

Time complexity: O(max(R,C)^2)

Space complexity: O(1) or O(RC) if ans included.

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

int k = 0;

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

int d = 0; // E

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

while (++k) {

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

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

c0 += dirs[d][0];

r0 += dirs[d][1];

if (c0 < 0 || c0 >= C || r0 < 0 || r0 >= R) continue;

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

}

d = (d + 1) % 4;

}

return {};

}

};

花花酱 SP5 Binary Search

By zxi on August 12, 2018

Template:

Time complexity: O(log(r-l)) * O(f(m) + g(m))

Space complexity: O(1)

"""

Returns the smallest number m such that g(m) is true.

"""

def binary_search(l, r):

while l < r:

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

if f(m): return m # if m is the answer

if g(m):

r = m # new range [l, m)

else

l = m + 1 # new range [m+1, r)

return l # or not found

Slides:

Lower Bound / Upper Bound

#include <iostream>

#include <vector>

using namespace std;

int upper_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] > val)

r = m;

else

l = m + 1;

}

return l;

}

int lower_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] >= val)

r = m;

else

l = m + 1;

}

return l;

}

int main() {

vector<int> A{1, 2, 2, 2, 4, 4, 5};

cout << lower_bound(A, 0, 0, A.size()) << endl; // 0

cout << lower_bound(A, 2, 0, A.size()) << endl; // 1

cout << lower_bound(A, 3, 0, A.size()) << endl; // 4

cout << upper_bound(A, 2, 0, A.size()) << endl; // 4

cout << upper_bound(A, 4, 0, A.size()) << endl; // 6

cout << upper_bound(A, 5, 0, A.size()) << endl; // 7

}

Mentioned Problems

花花酱 LeetCode 886. Possible Bipartition

By zxi on August 12, 2018

Problem

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Solution: Graph Coloring

Color a node with one color, and color all it’s disliked nodes with another color, if can not finish return false.

Time complexity: O(V+E)

Space complexity: O(V+E)

C++ / DFS

// Author: Huahua

// Running time: 96 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

g_ = vector<vector<int>>(N);

for (const auto& d : dislikes) {

g_[d[0] - 1].push_back(d[1] - 1);

g_[d[1] - 1].push_back(d[0] - 1);

}

colors_ = vector<int>(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors_[i] == 0 && !dfs(i, 1)) return false;

return true;

}

private:

vector<vector<int>> g_;

vector<int> colors_;

bool dfs(int cur, int color) {

colors_[cur] = color;

for (int nxt : g_[cur]) {

if (colors_[nxt] == color) return false;

if (colors_[nxt] == 0 && !dfs(nxt, -color)) return false;

}

return true;

}

};

C++ / BFS

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

vector<vector<int>> g(N);

for (const auto& d : dislikes) {

g[d[0] - 1].push_back(d[1] - 1);

g[d[1] - 1].push_back(d[0] - 1);

}

queue<int> q;

vector<int> colors(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors[i] != 0) continue;

q.push(i);

colors[i] = 1;

while (!q.empty()) {

int cur = q.front(); q.pop();

for (int nxt : g[cur]) {

if (colors[nxt] == colors[cur]) return false;

if (colors[nxt] != 0) continue;

colors[nxt] = -colors[cur];

q.push(nxt);

}

return true;

}

};

Problem

We are given two sentences A and B. (A sentence is a string of space separated words. Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]

Example 2:

Input: A = "apple apple", B = "banana"
Output: ["banana"]

Note:

0 <= A.length <= 200
0 <= B.length <= 200
A and B both contain only spaces and lowercase letters.

Solution: HashTable

Time complexity: O(m+n)

Space complexity: O(m+n)

C++

class Solution {

public:

vector<string> uncommonFromSentences(string A, string B) {

istringstream ss(A + " " + B);

unordered_map<string, int> counts;

string s;

while (ss >> s) ++counts[s];

vector<string> ans;

for (const auto& p : counts)

if (p.second == 1)

ans.push_back(p.first);

return ans;

}

};

花花酱 LeetCode 887. Super Egg Drop

Problem

Solution 1: Recursion with Memorization (TLE)

Solution 2: Solution 1 + Binary Search

花花酱 LeetCode 889. Spiral Matrix III

Problem

Solution: Simulation

花花酱 SP5 Binary Search

Mentioned Problems

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem

花花酱 LeetCode 888. Uncommon Words from Two Sentences

Problem

Solution: HashTable

Huahua's Tech Road

花花酱 LeetCode 887. Super Egg Drop

Problem

Solution 1: Recursion with Memorization (TLE)

Solution 2: Solution 1 + Binary Search

花花酱 LeetCode 889. Spiral Matrix III

Problem

Solution: Simulation

花花酱 SP5 Binary Search

Mentioned Problems

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem

花花酱 LeetCode 888. Uncommon Words from Two Sentences

Problem

Solution: HashTable