Huahua's Tech Road

花花酱 LeetCode 1492. The kth Factor of n

By zxi on June 27, 2020

Given two positive integers n and k.

A factor of an integer n is defined as an integer i where n % i == 0.

Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.

Example 1:

Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.

Example 2:

Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.

Example 3:

Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.

Example 4:

Input: n = 1, k = 1
Output: 1
Explanation: Factors list is [1], the 1st factor is 1.

Example 5:

Input: n = 1000, k = 3
Output: 4
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].

Constraints:

1 <= k <= n <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int kthFactor(int n, int k) {

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

if (n % i == 0 && --k == 0) return i;

return -1;

}

};

花花酱 LeetCode 1491. Average Salary Excluding the Minimum and Maximum Salary

By zxi on June 27, 2020

Given an array of unique integers salary where salary[i] is the salary of the employee i.

Return the average salary of employees excluding the minimum and maximum salary.

Example 1:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000)/2= 2500

Example 2:

Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000)/1= 2000

Example 3:

Input: salary = [6000,5000,4000,3000,2000,1000]
Output: 3500.00000

Example 4:

Input: salary = [8000,9000,2000,3000,6000,1000]
Output: 4750.00000

Constraints:

3 <= salary.length <= 100
10^3 <= salary[i] <= 10^6
salary[i] is unique.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

double average(vector<int>& salary) {

auto [lit, hit] = minmax_element(begin(salary), end(salary));

int sum = accumulate(begin(salary), end(salary), 0);

return (sum - *lit - *hit) * 1.0 / (salary.size() - 2);

}

};

花花酱 LeetCode 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

By zxi on June 26, 2020

Given a weighted undirected connected graph with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional and weighted edge between nodes from_i and to_i. A minimum spanning tree (MST) is a subset of the edges of the graph that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the minimum spanning tree (MST) of the given graph. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. A pseudo-critical edge, on the other hand, is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

Constraints:

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= from_i < to_i < n
1 <= weight_i <= 1000
All pairs (from_i, to_i) are distinct.

Solution: Brute Force?

For each edge
1. exclude it and build a MST, cost increased => critical
2. for a non critical edge, force include it and build a MST, cost remains the same => pseudo critical

Proof of 2, if a non critical / non pseudo critical edge was added into the MST, the total cost must be increased. So if the cost remains the same, must be the other case. Since we know the edge is non-critical, so it has to be pseudo critical.

C++

// Author: Huahua

class UnionFind {

public:

explicit UnionFind(int n): p_(n), r_(n) { iota(begin(p_), end(p_), 0); } // e.g. p[i] = i

int Find(int x) { return p_[x] == x ? x : p_[x] = Find(p_[x]); }

bool Union(int x, int y) {

int rx = Find(x);

int ry = Find(y);

if (rx == ry) return false;

if (r_[rx] == r_[ry]) {

p_[rx] = ry;

++r_[ry];

} else if (r_[rx] > r_[ry]) {

p_[ry] = rx;

} else {

p_[rx] = ry;

}

return true;

}

private:

vector<int> p_, r_;

};

class Solution {

public:

vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {

// Record the original id.

for (int i = 0; i < edges.size(); ++i) edges[i].push_back(i);

// Sort edges by weight.

sort(begin(edges), end(edges), [&](const auto& e1, const auto& e2){

if (e1[2] != e2[2]) return e1[2] < e2[2];

return e1 < e2;

});

// Cost of MST, ex: edge to exclude, in: edge to include.

auto MST = [&](int ex = -1, int in = -1) -> int {

UnionFind uf(n);

int cost = 0;

int count = 0;

if (in >= 0) {

cost += edges[in][2];

uf.Union(edges[in][0], edges[in][1]);

count++;

}

for (int i = 0; i < edges.size(); ++i) {

if (i == ex) continue;

if (!uf.Union(edges[i][0], edges[i][1])) continue;

cost += edges[i][2];

++count;

}

return count == n - 1 ? cost : INT_MAX;

};

const int min_cost = MST();

vector<int> criticals;

vector<int> pseudos;

for (int i = 0; i < edges.size(); ++i) {

// Cost increased or can't form a tree.

if (MST(i) > min_cost) {

criticals.push_back(edges[i][3]);

} else if (MST(-1, i) == min_cost) {

pseudos.push_back(edges[i][3]);

}

return {criticals, pseudos};

}

};

花花酱 LeetCode 1488. Avoid Flood in The City

By zxi on June 20, 2020

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9

Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.

Constraints:

1 <= rains.length <= 10^5
0 <= rains[i] <= 10^9

Solution: Binary Search

Store the days we can dry a lake in a treeset.
Store the last day when a lake becomes full in a hashtable.
Whenever we encounter a full lake, try to find the first available day that we can dry it. If no such day, return no answer.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> avoidFlood(vector<int>& rains) {

const int n = rains.size();

vector<int> ans(n, -1);

unordered_map<int, int> full; // lake -> day

set<int> dry; // days we can dry lakes.

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

const int lake = rains[i];

if (lake > 0) {

if (full.count(lake)) {

// Find the first day we can dry it.

auto it = dry.upper_bound(full[lake]);

if (it == end(dry)) return {};

ans[*it] = lake;

dry.erase(it);

}

full[lake] = i;

} else {

dry.insert(i);

ans[i] = 1;

}

return ans;

}

};

花花酱 LeetCode 1487. Making File Names Unique

By zxi on June 20, 2020

Given an array of strings names of size n. You will create n folders in your file system such that, at the ith minute, you will create a folder with the name names[i].

Since two files cannot have the same name, if you enter a folder name which is previously used, the system will have a suffix addition to its name in the form of (k), where, k is the smallest positive integer such that the obtained name remains unique.

Return an array of strings of length n where ans[i] is the actual name the system will assign to the ith folder when you create it.

Example 1:

Input: names = ["pes","fifa","gta","pes(2019)"]
Output: ["pes","fifa","gta","pes(2019)"]
Explanation: Let's see how the file system creates folder names:
"pes" --> not assigned before, remains "pes"
"fifa" --> not assigned before, remains "fifa"
"gta" --> not assigned before, remains "gta"
"pes(2019)" --> not assigned before, remains "pes(2019)"

Example 2:

Input: names = ["gta","gta(1)","gta","avalon"]
Output: ["gta","gta(1)","gta(2)","avalon"]
Explanation: Let's see how the file system creates folder names:
"gta" --> not assigned before, remains "gta"
"gta(1)" --> not assigned before, remains "gta(1)"
"gta" --> the name is reserved, system adds (k), since "gta(1)" is also reserved, systems put k = 2. it becomes "gta(2)"
"avalon" --> not assigned before, remains "avalon"

Example 3:

Input: names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
Output: ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
Explanation: When the last folder is created, the smallest positive valid k is 4, and it becomes "onepiece(4)".

Example 4:

Input: names = ["wano","wano","wano","wano"]
Output: ["wano","wano(1)","wano(2)","wano(3)"]
Explanation: Just increase the value of k each time you create folder "wano".

Example 5:

Input: names = ["kaido","kaido(1)","kaido","kaido(1)"]
Output: ["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
Explanation: Please note that system adds the suffix (k) to current name even it contained the same suffix before.

Constraints:

1 <= names.length <= 5 * 10^4
1 <= names[i].length <= 20
names[i] consists of lower case English letters, digits and/or round brackets.

Solution: Hashtable

Use a hashtable to store the mapping form base_name to its next suffix index.

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

C++

// Author: Huahua

class Solution {

public:

vector<string> getFolderNames(vector<string>& names) {

vector<string> ans;

unordered_map<string, int> m; // base_name -> next suffix.

for (const string& name : names) {

string unique_name = name;

int j = m[name];

if (j > 0) {

while (m.count(unique_name = name + "(" + to_string(j++) + ")"));

m[name] = j;

}

m[unique_name] = 1;

ans.push_back(unique_name);

}

return ans;

}

};