Posts tagged as “hashtable”

花花酱 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;

}

};

花花酱 LeetCode 1001. Grid Illumination

By zxi on February 24, 2019

On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.

Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)

Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].

Example 1:

Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: 
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the cell is no longer lit.

Note:

1 <= N <= 10^9
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == queries[i].length == 2

Solution: HashTable

use lx, ly, lp, lq to track the # of lamps that covers each row, col, diagonal, antidiagonal

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

C++

// Author: Huahua, running time: 460 ms, 82.2 MB

class Solution {

public:

vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

unordered_set<long> s;

unordered_map<int, int> lx, ly, lp, lq;

for (const auto& lamp : lamps) {

const int x = lamp[0];

const int y = lamp[1];

s.insert(static_cast<long>(x) << 32 | y);

++lx[x];

++ly[y];

++lp[x + y];

++lq[x - y];

}

vector<int> ans;

for (const auto& query : queries) {

const int x = query[0];

const int y = query[1];

if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

ans.push_back(1);

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty) {

if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

const long key = static_cast<long>(tx) << 32 | ty;

if (!s.count(key)) continue;

s.erase(key);

if (--lx[tx] == 0) lx.erase(tx);

if (--ly[ty] == 0) ly.erase(ty);

if (--lp[tx + ty] == 0) lp.erase(tx + ty);

if (--lq[tx - ty] == 0) lq.erase(tx - ty);

}

} else {

ans.push_back(0);

}

return ans;

}

};

C++ v2

// Author: Huahua, running time: 444 ms, 82.2 MB

class Solution {

public:

vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

unordered_set<long> s;

unordered_map<int, int> lx, ly, lp, lq;

for (const auto& lamp : lamps) {

const int x = lamp[0];

const int y = lamp[1];

s.insert(static_cast<long>(x) << 32 | y);

++lx[x];

++ly[y];

++lp[x + y];

++lq[x - y];

}

vector<int> ans;

auto dec = [](unordered_map<int, int>& m, int key) {

auto it = m.find(key);

if (it->second == 1)

m.erase(it);

else

--it->second;

};

for (const auto& query : queries) {

const int x = query[0];

const int y = query[1];

if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

ans.push_back(1);

for (int tx = x - 1; tx <= x + 1; ++tx)

for (int ty = y - 1; ty <= y + 1; ++ty) {

if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

const long key = static_cast<long>(tx) << 32 | ty;

auto it = s.find(key);

if (it == s.end()) continue;

s.erase(it);

dec(lx, tx);

dec(ly, ty);

dec(lp, tx + ty);

dec(lq, tx - ty);

}

} else {

ans.push_back(0);

}

return ans;

}

};

花花酱 LeetCode 133. Clone Graph

By zxi on February 13, 2019

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):

Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.

Solution: Queue + Hashtable

Time complexity: O(V+E)
Space complexity: O(V+E)

C++

// Author: Huahua, 44ms, 16.8MB

class Solution {

public:

UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {

if (!node) return nullptr;

typedef UndirectedGraphNode Node;

unordered_set<Node*> done;

unordered_map<Node*, Node*> m;

queue<Node*> q;

q.push(node);

while (!q.empty()) {

Node* s = q.front(); q.pop();

if (done.count(s)) continue;

done.insert(s);

if (!m.count(s))

m[s] = new Node(s->label);

Node* t = m[s];

for (Node* ss : s->neighbors) {

if (!m.count(ss))

m[ss] = new Node(ss->label);

q.push(ss);

t->neighbors.push_back(m[ss]);

}

return m[node];

}

};