Posts published in December 2017

花花酱 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 749. Contain Virus

By zxi on December 18, 2017

题目大意：给你一个格子地图上面有一些病毒用1表示，未受感染的格子用0表示。带有病毒的格子每天会向四周的格子传播病毒。在每一天，你必须在最大的病毒（连通区域）的周围建造墙阻挡病毒传播。问你一共需要多少个墙才能阻挡所有病毒传播。

Problems:

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region — the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

Example 2:

Input: grid = 
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output: 4
Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

Example 3:

Input: grid = 
[[1,1,1,0,0,0,0,0,0],
 [1,0,1,0,1,1,1,1,1],
 [1,1,1,0,0,0,0,0,0]]
Output: 13
Explanation: The region on the left only builds two new walls.

Note:

The number of rows and columns of grid will each be in the range [1, 50].
Each grid[i][j] will be either 0 or 1.
Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

Idea:

Use DFS to find virus regions, next affected regions and # of walls needed to block each virus region.

Simulate the virus expansion process.

Solution:

C++ / DFS

Time complexity: O(n^3)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

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

int m = grid.size();

int n = grid[0].size();

int total_walls = 0;

while (true) {

vector<int> visited(m * n, 0);

vector<int> virus_area;

vector<unordered_set<int>> nexts;

int block_index = -1;

int block_walls = -1;

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

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

int key = i * n + j;

if (grid[i][j] != 1 || visited[key]) continue;

vector<int> curr;

unordered_set<int> next;

int walls = 0;

getArea(j, i, m, n, grid, visited, curr, next, walls);

if (next.empty()) continue;

if (nexts.empty() || next.size() > nexts[block_index].size()) {

virus_area.swap(curr);

block_index = nexts.size();

block_walls = walls;

}

nexts.push_back(std::move(next));

}

if (nexts.empty()) break;

total_walls += block_walls;

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

if (i == block_index) {

for (const int key : virus_area) {

int y = key / n;

int x = key % n;

grid[y][x] = 2; // blocked.

}

} else {

for (const int key : nexts[i]) {

int y = key / n;

int x = key % n;

grid[y][x] = 1; // newly affected

}

return total_walls;

}

private:

void getArea(

int x, int y, int m, int n,

vector<vector<int>>& grid,

vector<int>& visited,

vector<int>& curr,

unordered_set<int>& next,

int& walls) {

static int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

if (x < 0 || x >= n || y < 0 || y >= m || grid[y][x] == 2) return;

int key = y * n + x;

// need one wall

if (grid[y][x] == 0) {

++walls;

next.insert(key);

return;

}

if (visited[key]) return;

visited[key] = 1;

curr.push_back(key);

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

getArea(x + dirs[i][0], y + dirs[i][1], m, n, grid, visited, curr, next, walls);

}

};

Posts published in December 2017

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

花花酱 LeetCode 301. Remove Invalid Parentheses

Solution: DFS

C++

花花酱 LeetCode 748. Shortest Completing Word

花花酱 LeetCode 749. Contain Virus

Problems:

Example 1:

Example 2:

Example 3:

Note:

Idea:

Solution:

Related Problems:

花花酱 LeetCode 746. Min Cost Climbing Stairs