Posts published in “Difficulty”

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

By zxi on December 22, 2017

题目大意: 给你一只股票每天的价格，如果只能做一次交易（一次买进一次卖出）问你最多能赚多少钱。

Problem:

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]

Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]

Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Idea:

Solution 1:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

const int n = prices.size();

if (n < 1) return 0;

vector<int> min_prices(n);

vector<int> max_profit(n);

min_prices[0] = prices[0];

max_profit[0] = 0;

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

min_prices[i] = min(min_prices[i - 1],

prices[i]);

max_profit[i] = max(max_profit[i - 1],

prices[i] - min_prices[i - 1]);

}

return max_profit[n - 1];

}

};

C++ / reduce to maximum subarray

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int n = prices.size();

if (n < 2) return 0;

vector<int> gains(n - 1, 0);

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

gains[i - 1] = prices[i] - prices[i - 1];

return max(0, maxSubArray(gains));

}

private:

// From LC 53. Maximum Subarray

int maxSubArray(vector<int>& nums) {

vector<int> f(nums.size());

f[0] = nums[0];

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

f[i] = max(f[i - 1] + nums[i], nums[i]);

return *std::max_element(f.begin(), f.end());

}

};

Related Problems:

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

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

}

};

花花酱 LeetCode 748. Shortest Completing Word

By zxi on December 20, 2017

题目大意: 给你一个由字母和数字组成车牌。另外给你一些单词，让你找一个最短的单词能够覆盖住车牌中的字母（不考虑大小写）。如果有多个解，输出第一个解。

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]

Output: "steps"

Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".

Note that the answer is not "step", because the letter "s" must occur in the word twice.

Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]

Output: "pest"

Explanation: There are 3 smallest length words that contains the letters "s".

We return the one that occurred first.

Note:

licensePlate will be a string with length in range [1, 7].
licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
words will have a length in the range [10, 1000].
Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Idea:

Hashtable

Solution:

C++

Time complexity: 时间复杂度 O(N*26), N is number of words.

Space complexity: 空间复杂度 O(26) = O(1)

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

string shortestCompletingWord(string licensePlate, vector<string>& words) {

vector<int> l(26, 0);

for (const char ch : licensePlate)

if (isalpha(ch)) ++l[tolower(ch) - 'a'];

string ans;

int min_l = INT_MAX;

for (const string& word : words) {

if (word.length() >= min_l) continue;

if (!matches(l, word)) continue;

min_l = word.length();

ans = word;

}

return ans;

}

private:

bool matches(const vector<int>& l, const string& word) {

vector<int> c(26, 0);

for (const char ch : word)

++c[tolower(ch) - 'a'];

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

if (c[i] < l[i]) return false;

return true;

}

};

花花酱 LeetCode 377. Combination Sum IV

By zxi on December 15, 2017

Problem:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]

target = 4

The possible combination ways are:

(1, 1, 1, 1)

(1, 1, 2)

(1, 2, 1)

(1, 3)

(2, 1, 1)

(2, 2)

(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

题目大意：给你一些数和一个目标值，问使用这些数(每个数可以被使用任意次数)加起来等于目标值的组合（其实是不重复的排列）有多少种。

Idea:

Solution:

C++ / Recursion + Memorization

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

m_ = vector<int>(target + 1, -1);

m_[0] = 1;

return dp(nums, target);

}

private:

int dp(const vector<int>& nums, int target) {

if (target < 0) return 0;

if (m_[target] != -1) return m_[target];

int ans = 0;

for (const int num : nums)

ans += dp(nums, target - num);

return m_[target] = ans;

}

vector<int> m_;

};

C++ / DP

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int combinationSum4(vector<int>& nums, int target) {

vector<int> dp(target + 1, 0); // dp[i] # of combinations sum up to i

dp[0] = 1;

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

for (const int num : nums)

if (i - num >= 0)

dp[i] += dp[i - num];

return dp[target];

}

};

Related Problems:

花花酱 LeetCode 210. Course Schedule II

By zxi on December 13, 2017

Problem

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1	2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

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

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.

题目大意：

给你一些课程和它的先修课程，让你输出修课顺序。如果无法修完所有课程，返回空数组。

Idea

Topological sorting

拓扑排序

Solution 1: Topological Sorting

Time complexity: O(V+E)

Space complexity: O(V+E)

C++

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {

vector<vector<int>> graph(numCourses);

for(const auto& p : prerequisites)

graph[p.second].push_back(p.first);

// states: 0 = unkonwn, 1 == visiting, 2 = visited

vector<int> v(numCourses, 0);

vector<int> ans;

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

if (dfs(i, graph, v, ans)) return {};

std::reverse(ans.begin(), ans.end());

return ans;

}

private:

bool dfs(int cur, vector<vector<int>>& graph, vector<int>& v, vector<int>& ans) {

if (v[cur] == 1) return true;

if (v[cur] == 2) return false;

v[cur] = 1;

for (const int t : graph[cur])

if (dfs(t, graph, v, ans)) return true;

v[cur] = 2;

ans.push_back(cur);

return false;

}

};

Java

// Author: Huahua

// Runtime: 83 ms

class Solution {

public int[] findOrder(int numCourses, int[][] prerequisites) {

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

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

graph.add(new ArrayList<Integer>());

for (int i = 0; i < prerequisites.length; ++i) {

int course = prerequisites[i][0];

int prerequisite = prerequisites[i][1];

graph.get(course).add(prerequisite);

}

int[] visited = new int[numCourses];

List<Integer> ans = new ArrayList<Integer>();

Integer index = numCourses;

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

if (dfs(i, graph, visited, ans)) return new int[0];

return ans.stream().mapToInt(i->i).toArray();

}

private boolean dfs(int curr, ArrayList<ArrayList<Integer>> graph, int[] visited, List<Integer> ans) {

if (visited[curr] == 1) return true;

if (visited[curr] == 2) return false;

visited[curr] = 1;

for (int next : graph.get(curr))

if (dfs(next, graph, visited, ans)) return true;

visited[curr] = 2;

ans.add(curr);

return false;

}