Posts tagged as “hard”

花花酱 LeetCode 980. Unique Paths III

By zxi on January 20, 2019

On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Example 1:

Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:

Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.

Note:

1 <= grid.length * grid[0].length <= 20

count how many empty blocks there are and try all possible paths to end point and check whether we visited every empty blocks or not.

Solution: Brute force / DP

C++/DFS

class Solution {

public:

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

int sx = -1;

int sy = -1;

int n = 1;

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

for (int j = 0; j < grid[0].size(); ++j)

if (grid[i][j] == 0) ++n;

else if (grid[i][j] == 1) { sx = j; sy = i; }

return dfs(grid, sx, sy, n);

}

private:

int dfs(vector<vector<int>>& grid, int x, int y, int n) {

if (x < 0 || x == grid[0].size() ||

y < 0 || y == grid.size() ||

grid[y][x] == -1) return 0;

if (grid[y][x] == 2) return n == 0;

grid[y][x] = -1;

int paths = dfs(grid, x + 1, y, n - 1) +

dfs(grid, x - 1, y, n - 1) +

dfs(grid, x, y + 1, n - 1) +

dfs(grid, x, y - 1, n - 1);

grid[y][x] = 0;

return paths;

};

C++/DP

class Solution {

public:

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

const int n = grid.size();

const int m = grid[0].size();

const vector<int> dirs{-1, 0, 1, 0, -1};

vector<vector<vector<short>>> cache(n, vector<vector<short>>(m, vector<short>(1 << n * m, -1)));

int sx = -1;

int sy = -1;

int state = 0;

auto key = [m](int x, int y) { return 1 << (y * m + x); };

function<short(int, int, int)> dfs = [&](int x, int y, int state) {

if (cache[y][x][state] != -1) return cache[y][x][state];

if (grid[y][x] == 2) return static_cast<short>(state == 0);

int paths = 0;

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

const int tx = x + dirs[i];

const int ty = y + dirs[i + 1];

if (tx < 0 || tx == m || ty < 0 || ty == n || grid[ty][tx] == -1) continue;

if (!(state & key(tx, ty))) continue;

paths += dfs(tx, ty, state ^ key(tx, ty));

}

return cache[y][x][state] = paths;

};

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

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

if (grid[y][x] == 0 || grid[y][x] == 2) state |= key(x, y);

else if (grid[y][x] == 1) { sx = x; sy = y; }

return dfs(sx, sy, state);

}

};

花花酱 LeetCode 975. Odd Even Jump

By zxi on January 15, 2019

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

During odd numbered jumps (ie. jumps 1, 3, 5, …), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, …), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

Example 1:

Input: [10,13,12,14,15] 
Output: 2

Example 2:

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

Example 3:

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

Note:

1 <= A.length <= 20000
0 <= A[i] < 100000

Solution: Binary Search + DP

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

int oddEvenJumps(vector<int>& A) {

const int n = A.size();

map<int, int> m;

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

dp[n - 1][0] = dp[n - 1][1] = 1;

m[A[n - 1]] = n - 1;

int ans = 1;

for (int i = n - 2; i >= 0; --i) {

auto o = m.lower_bound(A[i]);

if (o != m.end()) dp[i][0] = dp[o->second][1];

auto e = m.upper_bound(A[i]);

if (e != m.begin()) dp[i][1] = dp[prev(e)->second][0];

if (dp[i][0]) ++ans;

m[A[i]] = i;

}

return ans;

}

};

花花酱 LeetCode 972. Equal Rational Numbers

By zxi on January 5, 2019

Given two strings S and T, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

<IntegerPart> (e.g. 0, 12, 123)
<IntegerPart><.><NonRepeatingPart> (e.g. 0.5, 1., 2.12, 2.0001)
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.00(1212))

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1 / 6 = 0.16666666… = 0.1(6) = 0.1666(6) = 0.166(66)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

Example 1:

Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: S = "0.1666(6)", T = "0.166(66)"
Output: true

Example 3:

Input: S = "0.9(9)", T = "1."
Output: true
Explanation: 
"0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

Each part consists only of digits.
The <IntegerPart> will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.)
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution1: Expend the string

Extend the string to 16+ more digits and covert it to double.

0.9(9) => 0.99999999999999
0.(52) => 0.525252525252525
0.5(25) => 0.5252525252525

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

// 0.1234(567)

// 01234567890

// i = 1, p = 6

auto i = s.find('.');

auto p = s.find('(');

if (p != string::npos) {

string r = s.substr(p + 1, s.length() - p - 2);

s = s.substr(0, p);

while (s.length() < 16)

s += r;

}

return stod(s);

};

return abs(convert(S) - convert(T)) < 1e-10;

}

};

Python3

class Solution:

def isRationalEqual(self, S, T):

def convert(s):

i = s.find('.')

p = s.find('(')

if p >= 0:

r = s[p+1:-1]

s = s[0:p]

while len(s) < 16:

s += r

return float(s)

return abs(convert(S) - convert(T)) < 1e-10

Solution 2: Convert to a friction number

C++

// Author: Huahua, running time: 24 ms.

class Friction {

public:

Friction(long n = 0, long d = 1) {

long g = __gcd(n, d);

n_ = n / g;

d_ = d / g;

}

Friction operator+(const Friction& o) const {

return Friction(n_ * o.d_ + d_ * o.n_, d_ * o.d_);

}

bool operator==(const Friction& o) const {

return this->n_ * o.d_ == this->d_ * o.n_;

}

private:

long n_;

long d_;

};

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

std::regex re("(\\d+)\\.?(\\d+)?(\\((\\d+)\\))?");

std::smatch matches;

std::regex_match(s, matches, re);

string int_part = matches[1].str();

string nr_part = matches[2].str();

string r_part = matches[4].str();

Friction f(stoi(int_part), 1);

const int base = pow(10, nr_part.length());

if (nr_part.length())

f = f + Friction(stoi(nr_part), base);

if (r_part.length())

f = f + Friction(stoi(r_part), (pow(10, r_part.length()) - 1) * base);

return f;

};

return convert(S) == convert(T);

}

};

花花酱 LeetCode 968. Binary Tree Cameras

By zxi on December 31, 2018

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

Solution: Greedy + Recursion

Time complexity: O(n)
Space complexity: O(h)

C++

enum class State { NONE = 0, COVERED = 1, CAMERA = 2 };

class Solution {

public:

int minCameraCover(TreeNode* root) {

if (dfs(root) == State::NONE) ++ans_;

return ans_;

}

private:

int ans_ = 0;

State dfs(TreeNode* root) {

if (!root) return State::COVERED;

State l = dfs(root->left);

State r = dfs(root->right);

if (l == State::NONE || r == State::NONE) {

++ans_;

return State::CAMERA;

}

if (l == State::CAMERA || r == State::CAMERA)

return State::COVERED;

return State::NONE;

}

};

花花酱 LeetCode 960. Delete Columns to Make Sorted III

By zxi on December 19, 2018

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = ["babca","bbazb"] and deletion indices {0, 1, 4}, then the final array after deletions is ["bc","az"].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.

Example 2:

Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.

Example 3:

Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100

Solution: DP

dp[i] := max length of increasing sub-sequence (of all strings) ends with i-th letter.
dp[i] = max(dp[j] + 1) if all A[*][j] <= A[*][i], j < i
Time complexity: (n*L^2)
Space complexity: O(L)

C++

// Author: Huahua, running time: 24 ms

class Solution {

public:

int minDeletionSize(vector<string>& A) {

vector<int> dp(A[0].length(), 1);

for (int i = 0; i < A[0].length(); ++i)

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

bool valid = true;

for (const auto& a : A)

if (a[j] > a[i]) {

valid = false;

break;

}

if (valid) dp[i] = max(dp[i], dp[j] + 1);

}

return A[0].length() - *max_element(begin(dp), end(dp));

}

};

Python3

// Author: Huahua, running time: 176 ms

class Solution:

def minDeletionSize(self, A):

n = len(A[0])

dp = [1] * n

for i in range(1, n):

for j in range(i):

valid = True

for a in A:

if a[j] > a[i]:

valid = False

break

if valid:

dp[i] = max(dp[i], dp[j] + 1)

return n - max(dp)