Posts tagged as “hashtable”

花花酱 LeetCode 916. Word Subsets

By zxi on September 30, 2018

Problem

We are given two arrays A and B of words. Each word is a string of lowercase letters.

Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".

Now say a word a from A is universal if for every b in B, b is a subset of a.

Return a list of all universal words in A. You can return the words in any order.

Example 1:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]

Example 3:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]

Example 4:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Example 5:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]

Note:

1 <= A.length, B.length <= 10000
1 <= A[i].length, B[i].length <= 10
A[i] and B[i] consist only of lowercase letters.
All words in A[i] are unique: there isn’t i != j with A[i] == A[j].

Solution: Hashtable

Find the max requirement for each letter from B.

Time complexity: O(|A|+|B|)

Space complexity: O(26)

C++

// Author: Huahua, 104 ms

class Solution {

public:

vector<string> wordSubsets(vector<string>& A, vector<string>& B) {

vector<int> req(26);

for (const string& b : B) {

vector<int> cur(getCount(b));

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

req[i] = max(req[i], cur[i]);

}

vector<string> ans;

for (const string& a : A) {

vector<int> cur(getCount(a));

bool universal = true;

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

if (cur[i] < req[i]) {

universal = false;

break;

}

if (universal) ans.push_back(a);

}

return ans;

}

private:

vector<int> getCount(const string& a) {

vector<int> count(26);

for (char c : a)

++count[c - 'a'];

return count;

}

};

花花酱 LeetCode 911. Online Election

By zxi on September 25, 2018

Problem

n an election, the i-th vote was cast for persons[i] at time times[i].

Now, we would like to implement the following query function: TopVotedCandidate.q(int t) will return the number of the person that was leading the election at time t.

Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Example 1:

Input: ["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
Output: [null,0,1,1,0,0,1]
Explanation: 
At time 3, the votes are [0], and 0 is leading.
At time 12, the votes are [0,1,1], and 1 is leading.
At time 25, the votes are [0,1,1,0,0,1], and 1 is leading (as ties go to the most recent vote.)
This continues for 3 more queries at time 15, 24, and 8.

Note:

1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times is a strictly increasing array with all elements in [0, 10^9].
TopVotedCandidate.q is called at most 10000 times per test case.
TopVotedCandidate.q(int t) is always called with t >= times[0].

Solution: HashTable + Binary Search

Compute the leads for each t in times using a hash table.

binary search the upper bound of t, and return the lead of previous entry.

Time complexity: Constructor O(n), Query: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

class TopVotedCandidate {

public:

TopVotedCandidate(vector<int> persons, vector<int> times) {

vector<int> votes(persons.size() + 1);

int last_lead = persons.front();

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

if (++votes[persons[i]] >= votes[last_lead])

last_lead = persons[i];

leads_[times[i]] = last_lead;

}

int q(int t) {

return prev(leads_.upper_bound(t))->second;

}

private:

map<int, int> leads_; // time -> lead

};

花花酱 LeetCode 904. Fruit Into Baskets

By zxi on September 15, 2018

Problem

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

Add one piece of fruit from this tree to your baskets. If you cannot, stop.
Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

Solution: Hashtable + Sliding window

Time complexity: O(n)

Space complexity: O(1)

Keep track of the last index of each element. If a third type of fruit comes in, the new window starts after the fruit with smaller last index. Otherwise extend the current window.

[1 3 1 3 1 1] 4 1 4 … <- org window, 3 has a smaller last index than 1.

1 3 1 3 [1 1 4] 1 4 … <- new window

C++

// Author: Huahua, 144 ms

class Solution {

public:

int totalFruit(vector<int>& tree) {

map<int, int> idx; // {fruit -> last_index}

int ans = 0;

int cur = 0;

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

int f = tree[i];

if (!idx.count(f)) {

if (idx.size() == 2) {

auto it1 = begin(idx);

auto it2 = next(it1);

if (it1->second > it2->second) swap(it1, it2);

cur = i - it1->second - 1;

idx.erase(it1);

}

idx[f] = i;

ans = max(++cur, ans);

}

return ans;

}

};

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

By zxi on August 26, 2018

Problem

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Example 4:

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Solution: Signature

All Special-Equivalent Strings should have the same signature if we sort all the odd-index characters and all the even-index characters.

E.g. [“abcd”,”cdab”,”adcb”,”cbad”] are all in the same graph.

“abcd”: odd “ac”, even: “bd”
“cdab”: odd “ac”, even: “bd”
“adcb”: odd “ac”, even: “bd”
“cbad”: odd “ac”, even: “bd”

We can concatenate the odd and even strings to create a hashable signature.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int numSpecialEquivGroups(vector<string>& A) {

unordered_set<string> s;

for (const string& a : A) {

string odd;

string even;

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

if (i % 2)

odd += a[i];

else

even += a[i];

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

s.insert(odd + even);

}

return s.size();

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int numSpecialEquivGroups(String[] A) {

Set<String> groups = new HashSet<>();

for (String a: A) {

char[] odd = new char[(a.length() + 1) / 2];

char[] even = new char[(a.length() + 1) / 2];

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

if (i % 2 == 0)

even[i / 2] = a.charAt(i);

else

odd[i / 2] = a.charAt(i);

}

Arrays.sort(odd);

Arrays.sort(even);

String s = new String(odd) + new String(even);

groups.add(s);

}

return groups.size();

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

s = set()

for a in A:

odd = ""

even = ""

for i, c in enumerate(a):

if i % 2 == 0:

odd += c

else:

even += c

s.add(''.join(sorted(odd) + sorted(even)))

return len(s)

Python (1-linear)

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

return len(set([''.join(sorted(a[0::2]) + sorted(a[1::2])) for a in A]))

花花酱 LeetCode 888. Fair Candy Swap

By zxi on August 19, 2018

Problem

Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th bar of candy that Alice has, and B[j] is the size of the j-th bar of candy that Bob has.

Since they are friends, they would like to exchange one candy bar each so that after the exchange, they both have the same total amount of candy. (The total amount of candy a person has is the sum of the sizes of candy bars they have.)

Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.

If there are multiple answers, you may return any one of them. It is guaranteed an answer exists.

Example 1:

Input: A = [1,1], B = [2,2]
Output: [1,2]

Example 2:

Input: A = [1,2], B = [2,3]
Output: [1,2]

Example 3:

Input: A = [2], B = [1,3]
Output: [2,3]

Example 4:

Input: A = [1,2,5], B = [2,4]
Output: [5,4]

Note:

1 <= A.length <= 10000
1 <= B.length <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
It is guaranteed that Alice and Bob have different total amounts of candy.
It is guaranteed there exists an answer.

Solution: HashTable

Time complexity: O(A+B)

Space complexity: O(B)

Clean version

// Author: Huahua

// Running time: 132 ms

class Solution {

public:

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

int sum_a = accumulate(begin(A), end(A), 0);

int sum_b = accumulate(begin(B), end(B), 0);

unordered_set<int> s(begin(B), end(B));

int diff = (sum_b - sum_a) / 2;

for (int a : A)

if (s.count(a + diff)) return {a, a + diff};

}

};

Faster version

// Author: Huahua

// Running time: 68 ms

class Solution {

public:

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

int sum_a = accumulate(begin(A), end(A), 0);

int sum_b = 0;

unordered_set<int> s;

for (int b : B) {

sum_b += b;

s.insert(b);

}

int diff = (sum_b - sum_a) / 2;

for (int a : A)

if (s.count(a + diff)) return {a, a + diff};

}

};