Posts tagged as “hashtable”

花花酱 LeetCode 992. Subarrays with K Different Integers

By zxi on February 10, 2019

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

Solution: Two pointers + indirection

Let f(x) denote the number of subarrays with x or less distinct numbers.
ans = f(K) – f(K-1)
It takes O(n) Time and O(n) Space to compute f(x)

C++

// Author: Huahua

// vector: 56 ms, 10.1 MB

// Hashtable: 126 ms, 25 MB

class Solution {

public:

int subarraysWithKDistinct(vector<int>& A, int K) {

// Returns the number of subarrays with k or less distinct numbers.

auto subarrys = [&A](int k) {

vector<int> count(A.size() + 1);

int ans = 0;

int i = 0;

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

if (count[A[j]]++ == 0)

--k;

while (k < 0)

if (--count[A[i++]] == 0) ++k;

ans += j - i + 1;

}

return ans;

};

return subarrys(K) - subarrys(K - 1);

}

};

花花酱 LeetCode 982. Triples with Bitwise AND Equal To Zero

By zxi on January 26, 2019

Given an array of integers A, find the number of triples of indices (i, j, k) such that:

0 <= i < A.length
0 <= j < A.length
0 <= k < A.length
A[i] & A[j] & A[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

Note:

1 <= A.length <= 1000
0 <= A[i] < 2^16

Solution: Counting

Time complexity: O(n^2 + n * max(A))
Space complexity: O(max(A))

C++

// Author: Huahua, running time: 60 ms

class Solution {

public:

int countTriplets(vector<int>& A) {

const int n = *max_element(begin(A), end(A));

vector<int> count(n + 1);

for (int a: A)

for (int b: A)

++count[a & b];

int ans = 0;

for (int a : A)

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

if ((a & i) == 0) ans += count[i];

return ans;

}

};

花花酱 LeetCode 981. Time Based Key-Value Store

By zxi on January 26, 2019

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the one with the largest timestamp_prev.
If there are no values, it returns the empty string ("").

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation:   
TimeMap kv;   
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1   
kv.get("foo", 1);  // output "bar"   
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"   
kv.set("foo", "bar2", 4);   
kv.get("foo", 4); // output "bar2"   
kv.get("foo", 5); //output "bar2"

Example 2:

Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Note:

All key/value strings are lowercase.
All key/value strings have length in the range [1, 100]
The timestamps for all TimeMap.set operations are strictly increasing.
1 <= timestamp <= 10^7
TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

Solution: HashTable + Map

C++

// Author: Huahua, running time: 200 ms

class TimeMap {

public:

/** Initialize your data structure here. */

TimeMap() {}

void set(string key, string value, int timestamp) {

s_[key].emplace(timestamp, std::move(value));

}

string get(string key, int timestamp) {

auto m = s_.find(key);

if (m == s_.end()) return "";

auto it = m->second.upper_bound(timestamp);

if (it == begin(m->second)) return "";

return prev(it)->second;

}

private:

unordered_map<string, map<int, string>> s_;

};

花花酱 LeetCode 970. Powerful Integers

By zxi on January 5, 2019

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Note:

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

Solution: Brute Force

Time complexity: O(log(bound) / log(x) * log(bound) / log(y))
Space complexity: O(log(bound) / log(x) * log(bound) / log(y))

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> powerfulIntegers(int x, int y, int bound) {

unordered_set<int> ans;

for (int a = 1; a < bound; a *= x) {

for (int b = 1; a + b <= bound; b *= y) {

ans.insert(a + b);

if (y == 1) break;

}

if (x == 1) break;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 966. Vowel Spellchecker

By zxi on December 30, 2018

Problem

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
- Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
- Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
- Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
Vowel Errors: If after replacing the vowels (‘a’, ‘e’, ‘i’, ‘o’, ‘u’) of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
- Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
- Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
- Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
When the query matches a word up to capitlization, you should return the first such match in the wordlist.
When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
All strings in wordlist and queries consist only of english letters.

Solution: HashTable

Using 3 hashtables: original words, lower cases, lower cases with vowels replaced to “*”

Time complexity: O(|W|+|Q|)
Space complexity: O(|W|)

C++

class Solution {

public:

vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {

vector<string> ans;

unordered_map<string, string> m_org;

unordered_map<string, string> m_low;

unordered_map<string, string> m_vow;

for (const string& w : wordlist) {

// Original word

m_org[w] = w;

// Case-insensitive

string l = toLower(w);

if (!m_low.count(l)) m_low[l] = w;

// Vowel-insensitive

string o = replaceVowels(l);

if (!m_vow.count(o)) m_vow[o] = w;

}

for (const string& q : queries) {

if (m_org.count(q)) {

ans.push_back(q);

continue;

}

string l = toLower(q);

if (m_low.count(l)) {

ans.push_back(m_low[l]);

continue;

}

string o = replaceVowels(l);

if (m_vow.count(o)) {

ans.push_back(m_vow[o]);

continue;

}

ans.push_back("");

}

return ans;

}

private:

string toLower(const string& s) {

string l(s);

std::transform(begin(s), end(s), begin(l), ::tolower);

return l;

}

string replaceVowels(const string& s) {

string o(s);

for (char& c : o)

if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')

c = '*';

return o;

}

};

Python3

class Solution:

def spellchecker(self, wordlist, queries):

org = dict()

low = dict()

vow = dict()

for w in wordlist:

org[w] = w

l = w.lower()

if l not in low: low[l] = w

v = re.sub(r'[aeiou]', '*', l)

if v not in vow: vow[v] = w

ans = []

for q in queries:

if q in org:

ans.append(q)

continue

l = q.lower()

if l in low:

ans.append(low[l])

continue

v = re.sub(r'[aeiou]', '*', l)

if v in vow:

ans.append(vow[v])

continue

ans.append("")

return ans

Posts tagged as “hashtable”

花花酱 LeetCode 992. Subarrays with K Different Integers

Solution: Two pointers + indirection

C++

Related Problems

花花酱 LeetCode 982. Triples with Bitwise AND Equal To Zero

Solution: Counting

C++

花花酱 LeetCode 981. Time Based Key-Value Store

Solution: HashTable + Map

C++

花花酱 LeetCode 970. Powerful Integers

Solution: Brute Force

C++

花花酱 LeetCode 966. Vowel Spellchecker

Problem

Solution: HashTable

C++

Python3