Posts published in “Difficulty”

花花酱 LeetCode 758. Bold Words in String

By zxi on January 8, 2018

题目大意：给你一个字符串和一些要加粗的单词，返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between  and  tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "aabcd". Note that returning "aabcd" would use more tags, so it is incorrect.

Note:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string boldWords(vector<string>& words, string S) {

const int kMaxWordLen = 10;

unordered_set<string> dict(words.begin(), words.end());

int n = S.length();

vector<int> bolded(n, 0);

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

for (int l = 1; l <= min(n - i, kMaxWordLen); ++l)

if (dict.count(S.substr(i, l)))

std::fill(bolded.begin() + i, bolded.begin() + i + l, 1);

string ans;

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

if (bolded[i] && (i == 0 || !bolded[i - 1])) ans += "";

ans += S[i];

if (bolded[i] && (i == n - 1 || !bolded[i + 1])) ans += "";

}

return ans;

}

};

花花酱 LeetCode 760. Find Anagram Mappings

By zxi on January 8, 2018

题目大意：输出数组A中每个元素在数组B中的索引。

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

1 2	A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]

We should return

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

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of Aappears at B[4], and so on.

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, int> indices;

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

indices[B[i]] = i;

vector<int> ans;

for (const int a : A)

ans.push_back(indices[a]);

return ans;

}

};

C++ / No duplication

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> anagramMappings(vector<int>& A, vector<int>& B) {

map<int, vector<int>> indices;

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

indices[B[i]].push_back(i);

vector<int> ans;

for (const int a : A) {

ans.push_back(indices[a].back());

indices[a].pop_back();

}

return ans;

}

};

花花酱 LeetCode 322. Coin Change

By zxi on January 2, 2018

题目大意：给你一些不同币值的硬币，问你最少需要多少个硬币才能组成amount，假设每种硬币有无穷多个。

Problem:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Idea:

DP /knapsack

Solution1:

C++ / DP

Time complexity: O(n*amount^2)

Space complexity: O(amount)

// Author: Huahua

// Running time: 189 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (auto coin : coins) {

for (int i = amount - coin; i >= 0; --i)

if (dp[i] != INT_MAX)

for (int k = 1; k * coin + i <= amount; ++k)

dp[i + k * coin] = min(dp[i + k * coin], dp[i] + k);

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Solution2:

C++ / DP

Time complexity: O(n*amount)

Space complexity: O(amount)

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// dp[i] = min coins to make up to amount i

vector<int> dp(amount + 1, INT_MAX);

dp[0] = 0;

for (int coin : coins) {

for (int i = coin; i <= amount; ++i)

if (dp[i - coin] != INT_MAX)

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

}

return dp[amount] == INT_MAX ? -1 : dp[amount];

}

};

Python3

"""

Author: Huahua

Running time: 632 ms beats 90.27%

"""

class Solution:

def coinChange(self, coins, amount):

INVALID = 2**32

dp = [INVALID] * (amount + 1)

dp[0] = 0

for coin in coins:

for i in range(coin, amount + 1):

if dp[i - coin] >= dp[i]: continue

dp[i] = dp[i - coin] + 1

return -1 if dp[amount] == INVALID else dp[amount]

Solution3:

C++ / DFS

Time complexity: O(amount^n/(coin_0*coin_1*…*coin_n))

Space complexity: O(n)

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int coinChange(vector<int>& coins, int amount) {

// Sort coins in desending order

std::sort(coins.rbegin(), coins.rend());

int ans = INT_MAX;

coinChange(coins, 0, amount, 0, ans);

return ans == INT_MAX ? -1 : ans;

}

private:

void coinChange(const vector<int>& coins,

int s, int amount, int count, int& ans) {

if (amount == 0) {

ans = min(ans, count);

return;

}

if (s == coins.size()) return;

const int coin = coins[s];

for (int k = amount / coin; k >= 0 && count + k < ans; k--)

coinChange(coins, s + 1, amount - k * coin, count + k, ans);

}

};

Python3

"""

Author: Huahua

Running time: 200ms

"""

class Solution:

def coinChange(self, coins, amount):

coins.sort(reverse=True)

INVALID = 10**10

self.ans = INVALID

def dfs(s, amount, count):

if amount == 0:

self.ans = count

return

if s == len(coins): return

coin = coins[s]

for k in range(amount // coin, -1, -1):

if count + k >= self.ans: break

dfs(s + 1, amount - k * coin, count + k)

dfs(0, amount, 0)

return -1 if self.ans == INVALID else self.ans

花花酱 LeetCode 652. Find Duplicate Subtrees

By zxi on December 31, 2017

652. Find Duplicate SubtreesMedium730151FavoriteShare

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Example 1:

The following are two duplicate subtrees:

2
/
4

and

Therefore, you need to return above trees’ root in the form of a list.

Solution 1: Serialization

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

// Runtime: 29 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<string, int> counts;

vector<TreeNode*> ans;

serialize(root, counts, ans);

return ans;

}

private:

string serialize(TreeNode* root, unordered_map<string, int>& counts, vector<TreeNode*>& ans) {

if (!root) return "#";

string key = to_string(root->val) + ","

+ serialize(root->left, counts, ans) + ","

+ serialize(root->right, counts, ans);

if (++counts[key] == 2)

ans.push_back(root);

return key;

}

};

Solution 2: int id for each unique subtree

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 8 ms

class Solution {

public:

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

unordered_map<long, pair<int,int>> counts;

vector<TreeNode*> ans;

getId(root, counts, ans);

return ans;

}

private:

int getId(TreeNode* root,

unordered_map<long, pair<int,int>>& counts,

vector<TreeNode*>& ans) {

if (!root) return 0;

long key = (static_cast<long>(static_cast<unsigned>(root->val)) << 32) +

(getId(root->left, counts, ans) << 16) +

getId(root->right, counts, ans);

auto& p = counts[key];

if (p.second++ == 0)

p.first = counts.size();

else if (p.second == 2)

ans.push_back(root);

return p.first;

}

};

花花酱 LeetCode 416. Partition Equal Subset Sum

By zxi on December 31, 2017

题目大意：

给你一个正整数的数组，问你能否把元素划分成元素和相等的两组。

Problem:

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Idea:

DP 动态规划

Solution:

Time complexity: O(n*sum)

Space complexity: O(sum)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

bool canPartition(vector<int>& nums) {

const int sum = std::accumulate(nums.begin(), nums.end(), 0);

if (sum % 2 != 0) return false;

vector<int> dp(sum + 1, 0);

dp[0] = 1;

for (const int num : nums) {

for (int i = sum; i >= 0; --i)

if (dp[i]) dp[i + num] = 1;

if (dp[sum / 2]) return true;

}

return false;

}

};