Huahua’s Tech Road

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

}

};

花花酱 LeetCode Weekly 123

By zxi on February 10, 2019

Solutions

花花酱 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 991. Broken Calculator

By zxi on February 10, 2019

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 10^9
1 <= Y <= 10^9

Solution: Greedy

Thinking backwards, making Y <= X by adding 1 or dividing 2.

If Y is even, (Y + 1) // 2 == Y // 2, there is no need to do the extra step
If Y is odd (Y + 1) // 2 = (Y // 2) + 1, so only do + 1 when Y is odd

Time complexity: O(log(Y-X))
Space complexity: O(1)

C++

// Author: Huahua, running time: 4 ms, 4.7 MB

class Solution {

public:

int brokenCalc(int X, int Y) {

if (X <= Y) return X - Y;

return 1 + brokenCalc(X, Y % 2 ? Y + 1 : Y / 2);

}

};

花花酱 LeetCode 990. Satisfiability of Equality Equations

By zxi on February 10, 2019

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.

Example 2:

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

Input: ["a==b","b==c","a==c"]
Output: true

Example 4:

Input: ["a==b","b!=c","c==a"]
Output: false

Example 5:

Input: ["c==c","b==d","x!=z"]
Output: true

Note:

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] and equations[i][3] are lowercase letters
equations[i][1] is either '=' or '!'
equations[i][2] is '='

Solution: Union Find

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

C++

// Author: Huahua, running time: 12 ms, 7.1 MB

class Solution {

public:

bool equationsPossible(vector<string>& equations) {

iota(begin(parents_), end(parents_), 0);

for (const auto& eq : equations)

if (eq[1] == '=')

parents_[find(eq[0])] = find(eq[3]);

for (const auto& eq : equations)

if (eq[1] == '!' && find(eq[0]) == find(eq[3]))

return false;

return true;

}

private:

array<int, 128> parents_;

int find(int x) {

if (x != parents_[x])

parents_[x] = find(parents_[x]);

return parents_[x];

}

};

Huahua's Tech Road

花花酱 LeetCode 133. Clone Graph

Solution: Queue + Hashtable

C++

花花酱 LeetCode Weekly 123

Solutions

花花酱 LeetCode 992. Subarrays with K Different Integers

Solution: Two pointers + indirection

C++

Related Problems

花花酱 LeetCode 991. Broken Calculator

Solution: Greedy

C++

花花酱 LeetCode 990. Satisfiability of Equality Equations

Solution: Union Find

C++