Posts tagged as “hard”

花花酱 LeetCode 214. Shortest Palindrome

By zxi on February 20, 2018

题目大意：给你一个字符串你可以在它的前面添加一些字符，返回最短的回文字符串。

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++ w/ copy

// Author: Huahua

// Running time: 102 ms (<25.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.substr(0, n - i) == r.substr(i))

return r.substr(0, i) + s;

return "";

}

};

C++ w/o copy

// Author: Huahua

// Running time: 13 ms (<49.74%)

class Solution {

public:

string shortestPalindrome(string s) {

const string r(s.rbegin(), s.rend());

const int n = s.size();

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

if (s.compare(0, n - i, r, i, n - i) == 0)

return r.substr(0, i) + s;

return "";

}

};

花花酱 LeetCode 786. K-th Smallest Prime Fraction

By zxi on February 20, 2018

题目大意：给你一些互质数字，求出它们组成的分数中第K小的分数。

A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q.

What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer[1] = q.

Examples:

Input: A = [1, 2, 3, 5], K = 3

Output: [2, 5]

Explanation:

The fractions to be considered in sorted order are:

1/5, 1/3, 2/5, 1/2, 3/5, 2/3.

The third fraction is 2/5.

Input: A = [1, 7], K = 1

Output: [1, 7]

Note:

A will have length between 2 and 2000.
Each A[i] will be between 1 and 30000.
K will be between 1 and A.length * (A.length + 1) / 2.

Solution 1: Binary Search

Binary search m, 0 < m < 1, such that there are exact k pairs of (i, j) that A[i] / A[j] < m

Time complexity: O(n*C) C <= 31

C++

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {

const int n = A.size();

double l = 0;

double r = 1.0;

while (l < r) {

double m = (l + r) / 2;

double max_f = 0.0;

int total = 0;

int p, q = 0;

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

while (j < n && A[i] > m * A[j]) ++j;

if (n == j) break;

total += (n - j);

const double f = static_cast<double>(A[i]) / A[j];

if (f > max_f) {

p = i;

q = j;

max_f = f;

}

if (total == K)

return {A[p], A[q]};

else if (total > K)

r = m;

else

l = m;

}

return {};

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int[] kthSmallestPrimeFraction(int[] A, int K) {

final int n = A.length;

double l = 0;

double r = 1.0;

while (l < r) {

double m = (l + r) / 2;

double max_f = 0.0;

int total = 0;

int p = 0;

int q = 0;

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

while (j < n && A[i] > m * A[j]) ++j;

if (n == j) break;

total += (n - j);

final double f = (double)A[i] / A[j];

if (f > max_f) {

p = i;

q = j;

max_f = f;

}

if (total == K)

return new int[]{A[p], A[q]};

else if (total > K)

r = m;

else

l = m;

}

return new int[] {};

}

Python3

"""

Author: Huahua

Running time: 172 ms

"""

class Solution:

def kthSmallestPrimeFraction(self, A, K):

n = len(A)

l = 0.0

r = 1.0

while l < r:

m = (l + r) / 2

max_f = 0.0

total = 0

j = 1

for i in range(n - 1):

while j < n and A[i] > m * A[j]: j += 1

if j == n: break

total += n - j

f = A[i] / A[j]

if f > max_f:

p, q, max_f = i, j, f

if total == K:

return [A[p], A[q]]

elif total > K:

r = m

else:

l = m

return []

Related Problems:

花花酱 LeetCode 464. Can I Win

By zxi on February 4, 2018

题目大意：两个人从1到M中每次取出一个数加到当前的总和上，第一个达到或超过T的人获胜。问你第一个玩家能不能获胜。

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:

maxChoosableInteger = 10

desiredTotal = 11

Output:

false

Explanation:

No matter which integer the first player choose, the first player will lose.

The first player can choose an integer from 1 up to 10.

If the first player choose 1, the second player can only choose integers from 2 up to 10.

The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.

Same with other integers chosen by the first player, the second player will always win.

Solution: Recursion with memoization

Time complexity: O(2^M)

Space complexity: O(2^M)

C++

// Author: Huahua

// Running time: 19 ms (<98.70%)

class Solution {

public:

bool canIWin(int M, int T) {

const int sum = M * (M + 1) / 2;

if (sum < T) return false;

if (T <= 0) return true;

m_ = vector<char>(1 << M, 0);

return canIWin(M, T, 0);

}

private:

vector<char> m_; // 0: unknown, 1: won, -1: lost

bool canIWin(int M, int T, int state) {

if (T <= 0) return false;

if (m_[state]) return m_[state] == 1;

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

if (state & (1 << i)) continue; // number i used

// The next player can not win, current player wins

if (!canIWin(M, T - (i + 1), state | (1 << i)))

return m_[state] = 1;

}

// Current player loses.

m_[state] = -1;

return false;

}

};

Java

// Author: Huahua

// Running time: 20 ms

class Solution {

private byte[] m_;

public boolean canIWin(int M, int T) {

int sum = M * (M + 1) / 2;

if (sum < T) return false;

if (T <= 0) return true;

m_ = new byte[1 << M];

return canIWin(M, T, 0);

}

private boolean canIWin(int M, int T, int state) {

if (T <= 0) return false;

if (m_[state] != 0) return m_[state] == 1;

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

if ((state & (1 << i)) > 0) continue;

if (!canIWin(M, T - (i + 1), state | (1 << i))) {

m_[state] = 1;

return true;

}

m_[state] = -1;

return false;

}

Python3

"""

Author: Huahua

Running time: 706 ms

"""

class Solution:

def canIWin(self, M, T):

def win(M, T, m, state):

if T <= 0: return False

if m[state] != 0: return m[state] == 1

for i in range(M):

if (state & (1 << i)) > 0: continue

if not win(M, T - i - 1, m, state | (1 << i)):

m[state] = 1

return True

m[state] = -1

return False

s = M * (M + 1) / 2

if s < T: return False

if T <= 0: return True

if s == T: return (M % 2) == 1

m = [0] * (1 << M)

return win(M, T, m, 0)

花花酱 LeetCode 768. Max Chunks To Make Sorted II

By zxi on February 2, 2018

题目大意：给你一堆数让你分块，每块独立排序后和整个数组排序的结果相同，问你最多能分为几块。

Problem:

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [5,4,3,2,1]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.

Example 2:

Input: arr = [2,1,3,4,4]

Output: 4

Explanation:

We can split into two chunks, such as [2, 1], [3, 4, 4].

However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 2000].
arr[i] will be an integer in range [0, 10**8].

Idea:

Reduce the problem to 花花酱 769. Max Chunks To Make Sorted by creating a mapping from number to index in the sorted array.

arr = [2, 3, 5, 4, 4]

sorted = [2, 3, 4, 4, 5]

indices = [0, 1, 4, 2, 3]

Solution: Mapping

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 19 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

vector<int> v(arr.size());

std::iota(v.begin(), v.end(), 0);

std::sort(v.begin(), v.end(), [&arr](const int i1, const int i2){

return arr[i1] == arr[i2] ? (i1 < i2) : arr[i1] < arr[i2];

});

int ans = 0;

int m = 0;

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

m = max(m, v[i]);

if (m == i) ++ans;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 95 ms

"""

class Solution:

def maxChunksToSorted(self, arr):

v = sorted([(n << 32) | i for i, n in enumerate(arr)])

m = 0

ans = 0

for i, n in enumerate(v):

m = max(m, n & 0xffffffff)

if i == m: ans += 1

return ans

花花酱 LeetCode 282. Expression Add Operators

By zxi on January 30, 2018

题目大意：给你一个字符串，让你在数字之间加上+,-,*使得等式的值等于target。让你输出所有满足条件的表达式。

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"]

"232", 8 -> ["2*3+2", "2+3*2"]

"105", 5 -> ["1*0+5","10-5"]

"00", 0 -> ["0+0", "0-0", "0*0"]

"3456237490", 9191 -> []

Slides:

Solution 1: DFS

Time complexity: O(4^n)

Space complexity: O(n^2) -> O(n)

C++

// Author: Huahua

// Running time: 128 ms (<79.97%)

class Solution {

public:

vector<string> addOperators(string num, int target) {

vector<string> ans;

dfs(num, target, 0, "", 0, 0, &ans);

return ans;

}

private:

void dfs(const string& num, const int target, // input

int pos, const string& exp, long prev, long curr, // state

vector<string>* ans) { // output

if (pos == num.length()) {

if (curr == target) ans->push_back(exp);

return;

}

for (int l = 1; l <= num.size() - pos; ++l) {

string t = num.substr(pos, l);

if (t[0] == '0' && t.length() > 1) break; // 0X...

long n = std::stol(t);

if (n > INT_MAX) break;

if (pos == 0) {

dfs(num, target, l, t, n, n, ans);

continue;

}

dfs(num, target, pos + l, exp + '+' + t, n, curr + n, ans);

dfs(num, target, pos + l, exp + '-' + t, -n, curr - n, ans);

dfs(num, target, pos + l, exp + '*' + t, prev * n, curr - prev + prev * n, ans);

}

};

C++ / SC O(n)

// Author: Huahua

// Running time: 13 ms (< 99.14%)

class Solution {

public:

vector<string> addOperators(string num, int target) {

vector<string> ans;

string exp(num.length() * 2, '\0');

dfs(num, target, 0, exp, 0, 0, 0, &ans);

return ans;

}

private:

void dfs(const string& num, const int target,

int pos, string& exp, int len, long prev, long curr,

vector<string>* ans) {

if (pos == num.length()) {

if (curr == target) ans->push_back(exp.substr(0, len));

return;

}

long n = 0;

int s = pos;

int l = len;

if (s != 0) ++len;

while (pos < num.size()) {

n = n * 10 + (num[pos] - '0');

if (num[s] == '0' && pos - s > 0) break; // 0X... invalid number

if (n > INT_MAX) break; // too long

exp[len++] = num[pos++];

if (s == 0) {

dfs(num, target, pos, exp, len, n, n, ans);

continue;

}

exp[l] = '+'; dfs(num, target, pos, exp, len, n, curr + n, ans);

exp[l] = '-'; dfs(num, target, pos, exp, len, -n, curr - n, ans);

exp[l] = '*'; dfs(num, target, pos, exp, len, prev * n, curr - prev + prev * n, ans);

}

};

Java

// Author: Huahua

// Running time: 16 ms (<99.17%)

class Solution {

private List<String> ans;

private char[] num;

private char[] exp;

private int target;

public List<String> addOperators(String num, int target) {

this.num = num.toCharArray();

this.ans = new ArrayList<>();

this.target = target;

this.exp = new char[num.length() * 2];

dfs(0, 0, 0, 0);

return ans;

}

private void dfs(int pos, int len, long prev, long curr) {

if (pos == num.length) {

if (curr == target)

ans.add(new String(exp, 0, len));

return;

}

int s = pos;

int l = len;

if (s != 0) ++len;

long n = 0;

while (pos < num.length) {

if (num[s] == '0' && pos - s > 0) break; // 0X...

n = n * 10 + (int)(num[pos] - '0');

if (n > Integer.MAX_VALUE) break; // too long

exp[len++] = num[pos++]; // copy exp

if (s == 0) {

dfs(pos, len, n, n);

continue;

}

exp[l] = '+'; dfs(pos, len, n, curr + n);

exp[l] = '-'; dfs(pos, len, -n, curr - n);

exp[l] = '*'; dfs(pos, len, prev * n, curr - prev + prev * n);

}