Hashtable Archives - Page 21 of 34

花花酱 LeetCode 217. Contains Duplicate

By zxi on July 22, 2019

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution 1: HashTable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 48ms/16.5MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

unordered_set<int> s;

for (int num : nums)

if (!s.insert(num).second) return true;

return false;

}

};

Solution 2: Sorting

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua, 28ms/11.4MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

sort(begin(nums), end(nums));

for (int i = 1; i < nums.size(); ++i)

if (nums[i] == nums[i - 1]) return true;

return false;

}

};

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

By zxi on July 20, 2019

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) – that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Example 1:

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

Constraints:

1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

Solution: HashTable

Count how many times each key occurred so far.

Time complexity: O(n)
Space complexity: O(100)

C++

class Solution {

public:

int numEquivDominoPairs(vector<vector<int>>& dominoes) {

vector<int> m(100);

int ans = 0;

for (const auto& d : dominoes) {

int k1 = d[0] * 10 + d[1];

int k2 = d[1] * 10 + d[0];

ans += m[k1];

if (k1 != k2) ans += m[k2];

++m[k1];

}

return ans;

}

};

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

By zxi on March 16, 2019

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

1 <= time.length <= 60000
1 <= time[i] <= 500

Solution: Two Sum of 60

Time complexity: O(n)
Space complexity: O(60)

C++

// Author: Huahua, running time: 36 ms, 11.6 MB

class Solution {

public:

int numPairsDivisibleBy60(vector<int>& time) {

vector<int> c(60);

int ans = 0;

for (int t : time) {

t %= 60;

ans += c[(60 - t) % 60];

++c[t];

}

return ans;

}

};

花花酱 LeetCode 1002. Find Common Characters

By zxi on March 2, 2019

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1 <= A.length <= 100
1 <= A[i].length <= 100
A[i][j] is a lowercase letter

Solution: Min count for each character

Time complexity: O(n*l)
Space complexity: O(1)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

vector<string> commonChars(vector<string>& A) {

vector<int> min_count(26, INT_MAX);

for (const string& a : A) {

vector<int> count(26, 0);

for (const char ch : a)

++count[ch - 'a'];

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

min_count[i] = min(min_count[i], count[i]);

}

vector<string> ans;

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

if (min_count[i] == INT_MAX) continue;

for (int j = 0; j < min_count[i]; ++j)

ans.push_back(string(1, 'a' + i));

}

return ans;

}

};

花花酱 LeetCode 30. Substring with Concatenation of All Words

By zxi on March 2, 2019

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in sthat is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

Solution1: HashTable + Brute Force

Time complexity: O((|S| – |W|*l) * |W|*l))
Space complexity: O(|W|*l)

C++

// Author: Huahua

// std::string_view running time: 128 ms, 16 MB

// std::string running time: 156 ms, 22.4 MB

class Solution {

public:

vector<int> findSubstring(string s, vector<string>& words) {

if (words.empty() || s.empty()) return {};

const int n = words.size();

const int l = words[0].length();

if (n * l > s.length()) return {};

std::string_view ss(s);

std::unordered_map<std::string_view, int> expected;

for (const string& word : words)

++expected[string_view(word)];

vector<int> ans;

for (int i = 0; i <= ss.length() - n * l; ++i) {

std::unordered_map<std::string_view, int> seen;

int count = 0;

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

std::string_view w = ss.substr(i + j * l, l);

auto it = expected.find(w);

if (it == expected.end()) break;

if (++seen[w] > it->second) break;

++count;

}

if (count == n)

ans.push_back(i);

}

return ans;

}

};

Posts published in “Hashtable”

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

Solution: HashTable

C++

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

Solution: Two Sum of 60

C++

花花酱 LeetCode 1002. Find Common Characters

Solution: Min count for each character

C++

花花酱 LeetCode 30. Substring with Concatenation of All Words

Solution1: HashTable + Brute Force

C++