Posts published in “Hard”

花花酱 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);

}

花花酱 LeetCode 480. Sliding Window Median

By zxi on January 28, 2018

题目大意：让你求移动窗口的中位数。

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 5 [3 6 7] 6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.

Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

Time complexity: O(k*logk + (n – k + 1)*k)

Space complexity: O(k)

C++ / vector

// Author: Huahua

// Running time: 99 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

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

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::find(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

C++ / vector + binary_search for deletion.

// Author: Huahua

// Running time: 84 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

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

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::lower_bound(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 60 ms

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

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

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = 0;

while (i < window.length - 1 && val > window[i]) ++i;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = 0;

while (i < window.length && val != window[i]) ++i;

while (i < window.length - 1) window[i] = window[++i];

}

Java / Binary Search

// Author: Huahua

// Running time: 47 ms (<98.96%)

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

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

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

if (i < 0) i = - i - 1;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

while (i < window.length - 1) window[i] = window[++i];

}

Python

"""

Author: Huahua

Running time: 161 ms (< 93.75%)

"""

class Solution:

def medianSlidingWindow(self, nums, k):

if k == 0: return []

ans = []

window = sorted(nums[0:k])

for i in range(k, len(nums) + 1):

ans.append((window[k // 2] + window[(k - 1) // 2]) / 2.0)

if i == len(nums): break

index = bisect.bisect_left(window, nums[i - k])

window.pop(index)

bisect.insort_left(window, nums[i])

return ans

Solution 2: BST

// Author: Huahua

// Running time: 68 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

multiset<int> window(nums.begin(), nums.begin() + k);

auto mid = next(window.begin(), (k - 1) / 2);

for (int i = k; i <= nums.size(); ++i) {

ans.push_back((static_cast<double>(*mid) +

*next(mid, (k + 1) % 2)) / 2.0);

if (i == nums.size()) break;

window.insert(nums[i]);

if (nums[i] < *mid) --mid;

if (nums[i - k] <= *mid) ++mid;

window.erase(window.lower_bound(nums[i - k]));

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 759. Employee Free Time

By zxi on January 8, 2018

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Output: [[3,4]]

Explanation:

There are a total of three employees, and all common

free time intervals would be [-inf, 1], [3, 4], [10, inf].

We discard any intervals that contain inf as they aren't finite.

Example 2:

1 2	Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

schedule and schedule[i] are lists with lengths in range [1, 50].
0 <= schedule[i].start < schedule[i].end <= 10^8.

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

// Author: Huahua

// Running time: 81 ms

class Solution {

public:

vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

vector<Interval> all;

for (const auto intervals : schedule)

all.insert(all.end(), intervals.begin(), intervals.end());

std::sort(all.begin(), all.end(),

[](const Interval& a, const Interval& b){

return a.start < b.start;

});

vector<Interval> ans;

int end = all.front().end;

for (const Interval& busy : all) {

if (busy.start > end)

ans.emplace_back(end, busy.start);

end = max(end, busy.end);

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 752. Open the Lock

By zxi on December 25, 2017

Problem:

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"

Output: 6

Explanation:

A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".

Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,

because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"

Output: 1

Explanation:

We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"

Output: -1

Explanation:

We can't reach the target without getting stuck.

Example 4:

1 2	Input: deadends = ["0000"], target = "8888" Output: -1

Note:

The length of deadends will be in the range [1, 500].
target will not be in the list deadends.
Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities '0000' to '9999'.

题目大意：

给你一个4位密码锁，0可以转到1和9，1可以转到0和2，。。。，9可以转到0和8。

另外给你一些死锁的密码，比如1234，一但转到任何一个死锁的密码，锁就无法再转动了。

给你一个目标密码，问你最少要转多少次才能从0000转到目标密码。

Solution:

C++

// Author: Huahua

// Runtime: 133 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

const string start = "0000";

unordered_set<string> dead(deadends.begin(), deadends.end());

if (dead.count(start)) return -1;

if (start == target) return 0;

queue<string> q;

unordered_set<string> visited{start};

int steps = 0;

q.push(start);

while (!q.empty()) {

++steps;

const int size = q.size();

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

const string curr = q.front();

q.pop();

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

for (int j = -1; j <= 1; j += 2) {

string next = curr;

next[i] = (next[i] - '0' + j + 10) % 10 + '0';

if (next == target) return steps;

if (dead.count(next) || visited.count(next)) continue;

q.push(next);

visited.insert(next);

}

return -1;

}

};

C++ / Bidirectional BFS

// Author: Huahua

// Runtime: 32 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

const string start = "0000";

unordered_set<string> dead(deadends.begin(), deadends.end());

if (dead.count(start)) return -1;

if (target == start) return 0;

queue<string> q1;

queue<string> q2;

unordered_set<string> v1{start};

unordered_set<string> v2{target};

int s1 = 0;

int s2 = 0;

q1.push(start);

q2.push(target);

while (!q1.empty() && !q2.empty()) {

if (!q1.empty()) ++s1;

const int size = q1.size();

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

const string curr = q1.front();

q1.pop();

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

for (int j = -1; j <= 1; j += 2) {

string next = curr;

next[i] = (next[i] - '0' + j + 10) % 10 + '0';

if (v2.count(next)) return s1 + s2;

if (dead.count(next) || v1.count(next)) continue;

q1.push(next);

v1.insert(next);

}

swap(q1, q2);

swap(v1, v2);

swap(s1, s2);

}

return -1;

}

};

C++ / Bidirectional BFS / int state / Array

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int openLock(vector<string>& deadends, string target) {

constexpr int kMaxN = 10000;

const vector<int> bases{1, 10, 100, 1000};

const int start = 0;

const int goal = stoi(target);

queue<int> q1;

queue<int> q2;

vector<int> v1(kMaxN, 0);

vector<int> v2(kMaxN, 0);

for (const string& deadend : deadends)

v1[stoi(deadend)] = v2[stoi(deadend)] = -1;

if (v1[start] == -1) return -1;

if (start == goal) return 0;

v1[start] = 1;

v2[goal] = 1;

int s1 = 0;

int s2 = 0;

q1.push(start);

q2.push(goal);

while (!q1.empty() && !q2.empty()) {

if (!q1.empty()) ++s1;

const int size = q1.size();

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

const int curr = q1.front();

q1.pop();

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

int r = (curr / bases[i]) % 10;

for (int j = -1; j <= 1; j += 2) {

const int next = curr + ((r + j + 10) % 10 - r) * bases[i];

if (v2[next] == 1) return s1 + s2;

if (v1[next]) continue;

q1.push(next);

v1[next] = 1;

}

swap(q1, q2);

swap(v1, v2);

swap(s1, s2);

}

return -1;

}

};

Java

// Author: Huahua

// Runtime: 132 ms

class Solution {

public int openLock(String[] deadends, String target) {

String start = "0000";

Set<String> dead = new HashSet();

for (String d: deadends) dead.add(d);

if (dead.contains(start)) return -1;

Queue<String> queue = new LinkedList();

queue.offer(start);

Set<String> visited = new HashSet();

visited.add(start);

int steps = 0;

while (!queue.isEmpty()) {

++steps;

int size = queue.size();

for (int s = 0; s < size; ++s) {

String node = queue.poll();

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

for (int j = -1; j <= 1; j += 2) {

char[] chars = node.toCharArray();

chars[i] = (char)(((chars[i] - '0') + j + 10) % 10 + '0');

String next = new String(chars);

if (next.equals(target)) return steps;

if (dead.contains(next) || visited.contains(next))

continue;

visited.add(next);

queue.offer(next);

}

return -1;

}

Python

"""

Author: Huahua

Runtime: 955 ms

"""

class Solution:

def openLock(self, deadends, target):

from collections import deque

deads = set(deadends)

start = '0000'

if start in deads: return -1

q = deque([(start, 0)])

visited = set(start)

while q:

node, step = q.popleft()

for i in range(0, 4):

for j in [-1, 1]:

nxt = node[:i] + str((int(node[i]) + j + 10) % 10) + node[i+1:]

if nxt == target: return step + 1

if nxt in deads or nxt in visited: continue

q.append((nxt, step + 1))

visited.add(nxt)

return -1

Python / Int state

"""

Author: Huahua

Runtime: 568 ms

"""

class Solution:

def openLock(self, deadends, target):

from collections import deque

bases = [1, 10, 100, 1000]

deads = set(int(x) for x in deadends)

start, goal = int('0000'), int(target)

if start in deads: return -1

if start == goal: return 0

q = deque([(start, 0)])

visited = set([start])

while q:

node, step = q.popleft()

for i in range(0, 4):

r = (node // bases[i]) % 10

for j in [-1, 1]:

nxt = node + ((r + j + 10) % 10 - r) * bases[i]

if nxt == goal: return step + 1

if nxt in deads or nxt in visited: continue

q.append((nxt, step + 1))

visited.add(nxt)

return -1

花花酱 LeetCode 301. Remove Invalid Parentheses

By zxi on December 21, 2017

Problem:

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:

"()())()" -> ["()()()", "(())()"]

"(a)())()" -> ["(a)()()", "(a())()"]

")(" -> [""]

题目大意：给你一个字符串，由”(” “)”和其他字符构成。让你删除数量最少的括号使得表达式合法（括号都匹配）。输出所有的合法表达式。

Idea:

Solution: DFS

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<string> removeInvalidParentheses(const string& s) {

int l = 0;

int r = 0;

for (const char ch : s) {

l += (ch == '(');

if (l == 0)

r += (ch == ')');

else

l -= (ch == ')');

}

vector<string> ans;

dfs(s, 0, l, r, ans);

return ans;

}

private:

bool isValid(const string& s) {

int count = 0;

for (const char ch : s) {

if (ch == '(') ++count;

if (ch == ')') --count;

if (count < 0) return false;

}

return count == 0;

}

// l/r: number of left/right parentheses to remove.

void dfs(const string& s, int start, int l, int r, vector<string>& ans) {

// Nothing to remove.

if (l == 0 && r == 0) {

if (isValid(s)) ans.push_back(s);

return;

}

for (int i = start; i < s.length(); ++i) {

// We only remove the first parenthes if there are consecutive ones to avoid duplications.

if (i != start && s[i] == s[i - 1]) continue;

if (s[i] == '(' || s[i] == ')') {

string curr = s;

curr.erase(i, 1);

if (r > 0 && s[i] == ')')

dfs(curr, i, l, r - 1, ans);

else if (l > 0 && s[i] == '(')

dfs(curr, i, l - 1, r, ans);

}

};