Posts tagged as “hashtable”

花花酱 LeetCode 819. Most Common Word

By zxi on April 14, 2018

Problem

题目大意：找出一个段落中出现次数最多的单词。

https://leetcode.com/problems/most-common-word/description/

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:
Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

1 <= paragraph.length <= 1000.
1 <= banned.length <= 100.
1 <= banned[i].length <= 10.
The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
Different words in paragraph are always separated by a space.
There are no hyphens or hyphenated words.
Words only consist of letters, never apostrophes or other punctuation symbols.

Solution: Hashtable

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string mostCommonWord(string paragraph, vector<string>& banned) {

unordered_set<string> b(banned.begin(), banned.end());

unordered_map<string, int> counts;

const string pattern = "!?',;. ";

int best = 0;

string ans;

const int n = paragraph.size();

string word;

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

if (i == n || pattern.find(paragraph[i]) != string::npos) {

if (++counts[word] > best && !b.count(word) && word.size() > 0) {

best = counts[word];

ans = word;

}

word.clear();

} else {

word += tolower(paragraph[i]);

}

return ans;

}

};

花花酱 LeetCode 599. Minimum Index Sum of Two Lists

By zxi on April 2, 2018

Problem

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

Solution

Time complexity: O(n+m)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 103 ms

class Solution {

public:

vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {

unordered_map<string, int> indices;

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

indices[list1[i]] = i;

vector<string> ans;

int best_index = INT_MAX;

string best;

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

if (!indices.count(list2[i])) continue;

int index = indices[list2[i]] + i;

if (index < best_index) ans.clear();

if (index <= best_index) {

best_index = index;

ans.push_back(list2[i]);

}

return ans;

}

};

花花酱 LeetCode 811. Subdomain Visit Count

By zxi on April 1, 2018

Problem

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

Example 1:
Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation: 
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:
Input: 
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: 
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation: 
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 “.” characters.
The input count in any count-paired domain will not exceed 10000.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<string> subdomainVisits(vector<string>& cpdomains) {

unordered_map<string, int> counts;

for (const string& cpdomain : cpdomains) {

size_t index = cpdomain.find(' ');

int count = std::stoi(cpdomain.substr(0, index));

string domain = cpdomain.substr(index + 1);

while (true) {

counts[domain] += count;

size_t i = domain.find('.');

if (i == string::npos) break;

domain = domain.substr(i + 1);

}

vector<string> ans;

for (const auto& kv : counts)

ans.push_back(std::to_string(kv.second) + " " + kv.first);

return ans;

}

};

花花酱 LeetCode 804. Unique Morse Code Words

By zxi on March 24, 2018

Problem

题目大意：给你一些单词，问这些单词的莫斯密码共有几种形式。

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cab” can be written as “-.-.-….-“, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Note:

The length of words will be at most 100.
Each words[i] will have length in range [1, 12].
words[i] will only consist of lowercase letters.

Solution: HashTable

Time Complexity: O(n)

Space Complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int uniqueMorseRepresentations(vector<string>& words) {

vector<string> m{".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

unordered_set<string> s;

for (const string& word : words) {

string code;

for (char c : word)

code += m[c - 'a'];

s.insert(code);

}

return s.size();

}

};

花花酱 LeetCode 447. Number of Boomerangs

By zxi on March 24, 2018

Problem

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Solution: HashTable

For each point, compute the distance to the rest of the points and count.

if there are k points that have the same distance to current point, then there are P(k,2) = k*k-1 Boomerangs.

for example, p1, p2, p3 have the same distance to p0, then there are P(3,2) = 3 * (3-1) = 6 Boomerangs

(p1, p0, p2), (p1, p0, p3)

(p2, p0, p1), (p2, p0, p3)

(p3, p0, p1), (p3, p0, p2)

C++

// Author: Huahua

// Running time: 210 ms (beats 83.33%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

int ans = 0;

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

unordered_map<int, int> dist(points.size());

for (int j = 0; j < points.size(); ++j) {

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

++dist[dx * dx + dy * dy];

}

for (const auto& kv : dist)

ans += kv.second * (kv.second - 1);

}

return ans;

}

};

Solution 2: Sorting

dist = [1, 2, 1, 2, 1, 5]

sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1

ans = 3*(3-1) + 2 * (2 – 1) * 1 * (1 – 1) = 8

Time complexity: O(n*nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 150 ms (beats 98.52%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

const int n = points.size();

int ans = 0;

vector<int> dist(points.size());

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

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

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

dist[j] = dx * dx + dy * dy;

}

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

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

int k = 1;

while (j < n && dist[j] == dist[j - 1]) { ++j; ++k; }

ans += k * (k - 1);

}

return ans;

}

};