Huahua’s Tech Road

花花酱 LeetCode 1319. Number of Operations to Make Network Connected

By zxi on January 11, 2020

There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network.

Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2

Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.

Example 4:

Input: n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
Output: 0

Constraints:

1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
There are no repeated connections.
No two computers are connected by more than one cable.

Solution 1: Union-Find

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

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<int> p(n);

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

function<int(int)> find = [&](int x) {

return p[x] == x ? x : p[x] = find(p[x]);

};

for (const auto& c : connections)

p[find(c[0])] = find(c[1]);

unordered_set<int> s;

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

s.insert(find(i));

return s.size() - 1;

}

};

Solution 2: DFS

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

C++

// Author: Huahua

class Solution {

public:

int makeConnected(int n, vector<vector<int>>& connections) {

if (connections.size() < n - 1) return -1;

vector<vector<int>> g(n);

for (const auto& c : connections) {

g[c[0]].push_back(c[1]);

g[c[1]].push_back(c[0]);

}

vector<int> seen(n);

int count = 0;

function<void(int)> dfs = [&](int cur) {

for (int nxt : g[cur])

if (!seen[nxt]++) dfs(nxt);

};

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

if (!seen[i]++ && ++count)

dfs(i);

return count - 1;

}

};

花花酱 LeetCode 1313. Decompress Run-Length Encoded List

By zxi on January 11, 2020

We are given a list nums of integers representing a list compressed with run-length encoding.

Consider each adjacent pair of elements [a, b] = [nums[2*i], nums[2*i+1]] (with i >= 0). For each such pair, there are a elements with value b in the decompressed list.

Return the decompressed list.

Example 1:

Input: nums = [1,2,3,4]
Output: [2,4,4,4]

Constraints:

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

Solution: Simulation

Time complexity: O(sum(n_i))
Space complexity: O(sum(n_i)) or O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> decompressRLElist(vector<int>& nums) {

vector<int> ans;

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

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

ans.push_back(nums[i + 1]);

return ans;

}

};

花花酱 LeetCode 1314. Matrix Block Sum

By zxi on January 11, 2020

Given a m * n matrix mat and an integer K, return a matrix answer where each answer[i][j] is the sum of all elements mat[r][c] for i - K <= r <= i + K, j - K <= c <= j + K, and (r, c) is a valid position in the matrix.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
Output: [[12,21,16],[27,45,33],[24,39,28]]

Example 2:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
Output: [[45,45,45],[45,45,45],[45,45,45]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n, K <= 100
1 <= mat[i][j] <= 100

Solution: 2D range query

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

C++

// Author: Huahua, 20 ms

class Solution {

public:

vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {

const int n = mat.size();

const int m = mat[0].size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1));

for (int y = 1; y <= n; ++y)

for (int x = 1; x <= m; ++x)

dp[y][x] = dp[y - 1][x] + dp[y][x - 1] + mat[y - 1][x - 1] - dp[y - 1][x - 1];

auto ans = mat;

for (int y = 1; y <= n; ++y)

for (int x = 1; x <= m; ++x) {

int x1 = max(1, x - K);

int x2 = min(m, x + K);

int y1 = max(1, y - K);

int y2 = min(n, y + K);

ans[y - 1][x - 1] = dp[y2][x2] - dp[y1 - 1][x2] - dp[y2][x1 - 1] + dp[y1 - 1][x1 - 1];

}

return ans;

}

};

花花酱 LeetCode 1315. Sum of Nodes with Even-Valued Grandparent

By zxi on January 11, 2020

Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A grandparent of a node is the parent of its parent, if it exists.)

If there are no nodes with an even-valued grandparent, return 0.

Example 1:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int sumEvenGrandparent(TreeNode* root, int p = 1, int gp = 1) {

if (!root) return 0;

return sumEvenGrandparent(root->left, root->val, p)

+ sumEvenGrandparent(root->right, root->val, p)

+ (gp & 1 ? 0 : root->val);

}

};

花花酱 LeetCode 1316. Distinct Echo Substrings

By zxi on January 11, 2020

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself.

Example 1:

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

Constraints:

1 <= text.length <= 2000
text has only lowercase English letters.

Solution 1: Brute Force + HashSet

Try all possible substrings

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int distinctEchoSubstrings(string text) {

const int n = text.length();

string_view t(text);

unordered_set<string_view> s;

for (int k = 1; k <= n / 2; ++k)

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

if (t.substr(i, k) == t.substr(i + k, k))

s.insert(t.substr(i, 2 * k));

return s.size();

}

};

Huahua's Tech Road

花花酱 LeetCode 1319. Number of Operations to Make Network Connected

Solution 1: Union-Find

C++

Solution 2: DFS

C++

花花酱 LeetCode 1313. Decompress Run-Length Encoded List

Solution: Simulation

C++

花花酱 LeetCode 1314. Matrix Block Sum

Solution: 2D range query

C++

花花酱 LeetCode 1315. Sum of Nodes with Even-Valued Grandparent

C++

花花酱 LeetCode 1316. Distinct Echo Substrings

Solution 1: Brute Force + HashSet

C++