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

}

};

Related Problems:

[解题报告] LeetCode 200. Number of Islands

花花酱 LeetCode 746. Min Cost Climbing Stairs

By zxi on December 17, 2017

Problem:

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]

Output: 15

Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Output: 6

Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

题目大意:

有一个楼梯，要离开i层需要付cost[i]的费用，每次可以爬1层或2层。问你最少花多少钱能够达到顶楼。

Solution:

C++ / Recursion + Memorization 记忆化递归

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> m(cost.size() + 1);

return dp(cost, m, cost.size());

}

private:

// min cost to climb to i-th step

int dp(vector<int>& cost, vector<int>& m, int i) {

if (i <= 1) return 0;

if (m[i] > 0) return m[i];

return m[i] = min(dp(cost, m, i - 1) + cost[i - 1],

dp(cost, m, i - 2) + cost[i - 2]);

}

};

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> m(cost.size() + 1);

return min(dp(cost, m, cost.size() - 1),

dp(cost, m, cost.size() - 2));

}

private:

// min cost before leaving i-th step

int dp(vector<int>& cost, vector<int>& m, int i) {

if (i < 0) return 0;

if (m[i] > 0) return m[i];

return m[i] = min(dp(cost, m, i - 1), dp(cost, m, i - 2)) + cost[i];

}

};

C++ / DP 动态规划

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

const int n = cost.size();

vector<int> dp(n, INT_MAX); // d[i] min cost before leaving i

dp[0] = cost[0];

dp[1] = cost[1];

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

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

// We can reach top from either n - 1, or n - 2

return min(dp[n - 1], dp[n - 2]);

}

};

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

// dp[i] : min cost to climb to n-th step

vector<int> dp(cost.size() + 1, 0);

for (int i = 2; i <= cost.size(); ++i)

dp[i] = min(dp[i - 1] + cost[i - 1],

dp[i - 2] + cost[i - 2]);

return dp[cost.size()];

}

};

O(1) Space

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

int dp1 = 0;

int dp2 = 0;

for (int i = 2; i <= cost.size(); ++i) {

int dp = min(dp1 + cost[i - 1], dp2 + cost[i - 2]);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

花花酱 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 540. Single Element in a Sorted Array

By zxi on December 15, 2017

Problem:

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

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

Example 2:

1 2	Input: [3,3,7,7,10,11,11] Output: 10

Note: Your solution should run in O(log n) time and O(1) space.

Idea:

Binary search.

Time complexity: O(logn)

Space complexity: O(1)

Solution:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int singleNonDuplicate(vector<int>& nums) {

int l = 0;

int r = nums.size();

while (l < r) {

const int m = l + (r - l) / 2;

// int n = m % 2 == 0 ? m + 1 : m - 1;

const int n = m ^ 1;

if (nums[m] == nums[n])

l = m + 1;

else

r = m;

}

return nums[l];

}

};

Huahua's Tech Road

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

花花酱 LeetCode 377. Combination Sum IV

花花酱 LeetCode 540. Single Element in a Sorted Array