Posts published in “Hashtable”

花花酱 LeetCode 432. All O`one Data Structure

By zxi on April 6, 2018

Problem

题目大意：设计一种数据结构，支持inc/dec/getmaxkey/getminkey操作，必须都在O(1)时间内完成。

https://leetcode.com/problems/all-oone-data-structure/description/

Implement a data structure supporting the following operations:

Inc(Key) – Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) – If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() – Returns one of the keys with maximal value. If no element exists, return an empty string "".
GetMinKey() – Returns one of the keys with minimal value. If no element exists, return an empty string "".

Challenge: Perform all these in O(1) time complexity.

Solution

Time complexity: O(1)

Space complexity: O(n), n = # of unique keys

// Author: Huahua

// Running time: 32 ms

class AllOne {

public:

/** Initialize your data structure here. */

AllOne() {}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */

void inc(string key) {

auto it = m_.find(key);

if (it == m_.end()) {

if (l_.empty() || l_.front().value != 1)

l_.push_front({1, {key}});

else

l_.front().keys.insert(key);

m_[key] = l_.begin();

return;

}

auto lit = it->second;

auto nit = next(lit);

if (nit == l_.end() || nit->value != lit->value + 1)

nit = l_.insert(nit, {lit->value + 1, {}});

nit->keys.insert(key);

m_[key] = nit;

remove(lit, key);

}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */

void dec(string key) {

auto it = m_.find(key);

if (it == m_.end()) return;

auto lit = it->second;

if (lit->value > 1) {

auto pit = prev(lit);

if (lit == l_.begin() || pit->value != lit->value - 1)

pit = l_.insert(lit, {lit->value - 1, {}});

pit->keys.insert(key);

m_[key] = pit;

} else {

// value == 1, remove from the data structure

m_.erase(key);

}

remove(lit, key);

}

/** Returns one of the keys with maximal value. */

string getMaxKey() {

return l_.empty() ? "" : *l_.back().keys.cbegin();

}

/** Returns one of the keys with Minimal value. */

string getMinKey() {

return l_.empty() ? "" : *l_.front().keys.cbegin();

}

private:

struct Node {

int value;

unordered_set<string> keys;

};

list<Node> l_;

unordered_map<string, list<Node>::iterator> m_;

// Remove from old node.

void remove(list<Node>::iterator it, const string& key) {

it->keys.erase(key);

if (it->keys.empty())

l_.erase(it);

}

};

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;

}

};

Posts published in “Hashtable”

花花酱 LeetCode 432. All O`one Data Structure

Problem

Solution

Related Problems

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

Problem

Solution

花花酱 LeetCode 811. Subdomain Visit Count

Problem

Solution: HashTable

花花酱 LeetCode 804. Unique Morse Code Words

Problem

Solution: HashTable

花花酱 LeetCode 447. Number of Boomerangs

Problem

Solution: HashTable

Solution 2: Sorting