花花酱 LeetCode 825. Friends Of Appropriate Ages

By zxi on April 29, 2018

Problem

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]
Output: 
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

Solution: Hashtable

Count how many people at each age i.

Time complexity: O(n)

Space complexity: O(120)

C++

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int numFriendRequests(vector<int>& ages) {

const int kMaxAge = 120;

vector<int> counts(kMaxAge + 1, 0);

for (const int age : ages)

++counts[age];

int ans = 0;

for (int A = 1; A <= kMaxAge; ++A) {

for (int B = 0.5 * A + 7 + 1; B <= A; ++B)

ans += counts[A] * (counts[B] - (A == B));

}

return ans;

}

};

花花酱 LeetCode 824. Goat Latin

By zxi on April 29, 2018

Problem

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to “Goat Latin” (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append "ma" to the end of the word.
For example, the word ‘apple’ becomes ‘applema’.
If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add "ma".
For example, the word "goat" becomes "oatgma".
Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1.
For example, the first word gets "a" added to the end, the second word gets "aa" added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Notes:

S contains only uppercase, lowercase and spaces. Exactly one space between each word.
1 <= S.length <= 100.

Solution: String

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string toGoatLatin(string S) {

const string vowls = "aeiouAEIOU";

string ans;

string word;

int index = 0;

istringstream s(S);

while (s >> word) {

if (vowls.find(word[0]) == string::npos)

word = word.substr(1) + word[0];

ans += " " + word + "ma" + string(++index, 'a');

}

return ans.substr(1);

}

};

花花酱 LeetCode 822. Card Flipping Game

By zxi on April 29, 2018

Problem

题目大意：每张牌的正反面各印着一个数，你可以随便翻牌。找出一个最小的数使得其他牌当前正面的数值都不和它相等。

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card.

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good? If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i.

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3]. We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

Note:

1 <= fronts.length == backs.length <= 1000.
1 <= fronts[i] <= 2000.
1 <= backs[i] <= 2000.

Solution: Hashset

C++

// Author: Huahua

// Running time: 23 ms

class Solution {

public:

int flipgame(vector<int>& fronts, vector<int>& backs) {

unordered_set<int> same;

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

if (fronts[i] == backs[i])

same.insert(fronts[i]);

int ans = INT_MAX;

for (int v : fronts)

if (v < ans && !same.count(v)) ans = v;

for (int v : backs)

if (v < ans && !same.count(v)) ans = v;

return ans == INT_MAX ? 0 : ans;

}

};

花花酱 LeetCode 823. Binary Trees With Factors

By zxi on April 29, 2018

Problem

题目大意：给你一些可以重复使用的数字问能够构成多少种不同的特殊二叉树（根结点的值需为子节点值的乘积）。

https://leetcode.com/problems/binary-trees-with-factors/description/

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3 Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

Solution: DP

Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].

dp[i] = sum(dp[j] * dp[i/j]), 0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.

      A[i]
     /    \
 A[j]  (A[i]/A[j])
  / \     / \
 .....   .....

ans = sum(dp[i]), for all possible i.

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 53 ms

class Solution {

public:

int numFactoredBinaryTrees(vector<int>& A) {

constexpr long kMod = 1000000007;

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

unordered_map<int, long> dp;

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

dp[A[i]] = 1;

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

if (A[i] % A[j] == 0 && dp.count(A[i] / A[j]))

dp[A[i]] += (dp[A[j]] * dp[A[i] / A[j]]) % kMod;

}

long ans = 0;

for (const auto& kv : dp)

ans += kv.second;

return ans % kMod;

}

};

花花酱 LeetCode 820. Short Encoding of Words

By zxi on April 24, 2018

Problem

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

Idea

Remove all the words that are suffix of other words.

Solution

Time complexity: O(n*l^2)

Space complexity: O(n*l)

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int minimumLengthEncoding(vector<string>& words) {

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

for (const string& w : words) {

for (int i = w.length() - 1; i > 0; --i)

s.erase(w.substr(i));

}

int ans = 0;

for (const string& w : s)

ans += w.length() + 1;

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 825. Friends Of Appropriate Ages

Problem

Solution: Hashtable

花花酱 LeetCode 824. Goat Latin

Problem

Solution: String

花花酱 LeetCode 822. Card Flipping Game

Problem

Solution: Hashset

花花酱 LeetCode 823. Binary Trees With Factors

Problem

Solution: DP

花花酱 LeetCode 820. Short Encoding of Words

Problem

Idea

Solution