Posts tagged as “medium”

花花酱 LeetCode 1797. Design Authentication Manager

By zxi on March 20, 2021

There is an authentication system that works with authentication tokens. For each session, the user will receive a new authentication token that will expire timeToLive seconds after the currentTime. If the token is renewed, the expiry time will be extended to expire timeToLive seconds after the (potentially different) currentTime.

Implement the AuthenticationManager class:

AuthenticationManager(int timeToLive) constructs the AuthenticationManager and sets the timeToLive.
generate(string tokenId, int currentTime) generates a new token with the given tokenId at the given currentTime in seconds.
renew(string tokenId, int currentTime) renews the unexpired token with the given tokenId at the given currentTime in seconds. If there are no unexpired tokens with the given tokenId, the request is ignored, and nothing happens.
countUnexpiredTokens(int currentTime) returns the number of unexpired tokens at the given currentTime.

Note that if a token expires at time t, and another action happens on time t (renew or countUnexpiredTokens), the expiration takes place before the other actions.

Example 1:

Input
["AuthenticationManager", "renew", "generate", "countUnexpiredTokens", "generate", "renew", "renew", "countUnexpiredTokens"]
[[5], ["aaa", 1], ["aaa", 2], [6], ["bbb", 7], ["aaa", 8], ["bbb", 10], [15]]
Output
[null, null, null, 1, null, null, null, 0]

Explanation AuthenticationManager authenticationManager = new AuthenticationManager(5); // Constructs the AuthenticationManager with timeToLive = 5 seconds. authenticationManager.renew(“aaa”, 1); // No token exists with tokenId “aaa” at time 1, so nothing happens. authenticationManager.generate(“aaa”, 2); // Generates a new token with tokenId “aaa” at time 2. authenticationManager.countUnexpiredTokens(6); // The token with tokenId “aaa” is the only unexpired one at time 6, so return 1. authenticationManager.generate(“bbb”, 7); // Generates a new token with tokenId “bbb” at time 7. authenticationManager.renew(“aaa”, 8); // The token with tokenId “aaa” expired at time 7, and 8 >= 7, so at time 8 the renew request is ignored, and nothing happens. authenticationManager.renew(“bbb”, 10); // The token with tokenId “bbb” is unexpired at time 10, so the renew request is fulfilled and now the token will expire at time 15. authenticationManager.countUnexpiredTokens(15); // The token with tokenId “bbb” expires at time 15, and the token with tokenId “aaa” expired at time 7, so currently no token is unexpired, so return 0.

Constraints:

1 <= timeToLive <= 10⁸
1 <= currentTime <= 10⁸
1 <= tokenId.length <= 5
tokenId consists only of lowercase letters.
All calls to generate will contain unique values of tokenId.
The values of currentTime across all the function calls will be strictly increasing.
At most 2000 calls will be made to all functions combined.

Solution: Hashtable

Use a hashtable to store the token and its expiration time.

Time complexity: at most O(n) per operation
Space complexity: O(n)

C++

// Author: Huahua, 160 ms, 30.1 MB

class AuthenticationManager {

public:

AuthenticationManager(int timeToLive) : ttl_(timeToLive) {}

void generate(string tokenId, int currentTime) {

clear(currentTime);

tokens_[tokenId] = currentTime + ttl_;

}

void renew(string tokenId, int currentTime) {

clear(currentTime);

if (!tokens_.count(tokenId)) return;

tokens_[tokenId] = currentTime + ttl_;

}

int countUnexpiredTokens(int currentTime) {

clear(currentTime);

return tokens_.size();

}

private:

void clear(int currentTime) {

vector<string> ids;

for (const auto& [id, t] : tokens_)

if (t <= currentTime) ids.push_back(id);

for (const string& id : ids)

tokens_.erase(id);

}

unordered_map<string, int> tokens_;

int ttl_;

};

/**

* Your AuthenticationManager object will be instantiated and called as such:

* AuthenticationManager* obj = new AuthenticationManager(timeToLive);

* obj->generate(tokenId,currentTime);

* obj->renew(tokenId,currentTime);

* int param_3 = obj->countUnexpiredTokens(currentTime);

花花酱 LeetCode 1792. Maximum Average Pass Ratio

By zxi on March 13, 2021

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [pass_i, total_i]. You know beforehand that in the i^th class, there are total_i total students, but only pass_i number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10^-5 of the actual answer will be accepted.

Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints:

1 <= classes.length <= 10⁵
classes[i].length == 2
1 <= pass_i <= total_i <= 10⁵
1 <= extraStudents <= 10⁵

Solution: Greedy + Heap

Sort by the ratio increase potential (p + 1) / (t + 1) – p / t.

Time complexity: O((m+n)logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {

const int n = classes.size();

auto ratio = [&](int i, int delta = 0) {

return static_cast<double>(classes[i][0] + delta) /

(classes[i][1] + delta);

};

priority_queue<pair<double, int>> q;

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

q.emplace(ratio(i, 1) - ratio(i), i);

while (extraStudents--) {

const auto [r, i] = q.top(); q.pop();

++classes[i][0];

++classes[i][1];

q.emplace(ratio(i, 1) - ratio(i), i);

}

double total_ratio = 0;

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

total_ratio += ratio(i);

return total_ratio / n;

}

};

Python3

# Author: Huahua

class Solution:

def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:

def ratio(i, delta=0):

return (classes[i][0] + delta) / (classes[i][1] + delta)

q = []

for i, c in enumerate(classes):

heapq.heappush(q, (-(ratio(i, 1) - ratio(i)), i))

for _ in range(extraStudents):

_, i = heapq.heappop(q)

classes[i][0] += 1

classes[i][1] += 1

heapq.heappush(q, (-(ratio(i, 1) - ratio(i)), i))

return mean(ratio(i) for i, _ in enumerate(classes))

花花酱 LeetCode 1791. Find Center of Star Graph

By zxi on March 13, 2021

There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.

You are given a 2D integer array edges where each edges[i] = [u_i, v_i] indicates that there is an edge between the nodes u_i and v_i. Return the center of the given star graph.

Example 1:

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: As shown in the figure above, node 2 is connected to every other node, so 2 is the center.

Example 2:

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

Constraints:

3 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
1 <= u_i, v_i <= n
u_i != v_i
The given edges represent a valid star graph.

Solution: Graph / Hashtable

Count the degree of each node, return the one with n-1 degrees.

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

C++

// Author: Huahua

class Solution {

public:

int findCenter(vector<vector<int>>& edges) {

unordered_map<int, int> degrees;

for (const auto& e : edges) {

++degrees[e[0]];

++degrees[e[1]];

}

const int n = degrees.size();

for (const auto& [id, d] : degrees)

if (d == n - 1) return id;

return -1;

}

};

Since the center node must appear in each edge, we just need to find the mode of edges[0] + edges[1]

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

Python

# Author: Huahua

class Solution:

def findCenter(self, e):

return mode(e[0] + e[1])

花花酱 LeetCode 1786. Number of Restricted Paths From First to Last Node

By zxi on March 6, 2021

There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [u_i, v_i, weight_i] denotes that there is an edge between nodes u_i and v_i with weight equal to weight_i.

A path from node start to node end is a sequence of nodes [z₀, z₁,z₂, ..., z_k] such that z₀= start and z_k = end and there is an edge between z_i and z_i+1 where 0 <= i <= k-1.

The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(z_i) > distanceToLastNode(z_i+1) where 0 <= i <= k-1.

Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

Example 2:

Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
Output: 1
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7.

Constraints:

1 <= n <= 2 * 10⁴
n - 1 <= edges.length <= 4 * 10⁴
edges[i].length == 3
1 <= u_i, v_i <= n
u_i!= v_i
1 <= weight_i <= 10⁵
There is at most one edge between any two nodes.
There is at least one path between any two nodes.

Solution: Dijkstra + DFS w/ memoization

Find shortest path from n to all the nodes.
paths(u) = sum(paths(v)) if dist[u] > dist[v] and (u, v) has an edge
return paths(1)

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

C++

// Author: Huahua

class Solution {

public:

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

constexpr int kMod = 1e9 + 7;

using PII = pair<int, int>;

vector<vector<PII>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Shortest distance from n to x.

vector<int> dist(n + 1, INT_MAX / 2);

dist[n] = 0;

priority_queue<PII, vector<PII>, std::greater<PII>> q;

q.emplace(0, n);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (dist[u] < d) continue;

for (auto [v, w]: g[u]) {

if (dist[u] + w >= dist[v]) continue;

dist[v] = dist[u] + w;

q.emplace(dist[v], v);

}

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

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

if (u == n) return 1;

if (dp[u] != INT_MAX) return dp[u];

int ans = 0;

for (auto [v, w]: g[u])

if (dist[u] > dist[v])

ans = (ans + dfs(v)) % kMod;

return dp[u] = ans;

};

return dfs(1);

}

};

Combined

C++

// Author: Huahua

class Solution {

public:

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

constexpr int kMod = 1e9 + 7;

using PII = pair<int, int>;

vector<vector<PII>> g(n + 1);

for (const auto& e : edges) {

g[e[0]].emplace_back(e[1], e[2]);

g[e[1]].emplace_back(e[0], e[2]);

}

// Shortest distance from n to x.

vector<int> dist(n + 1, INT_MAX);

vector<int> dp(n + 1);

dist[n] = 0;

dp[n] = 1;

priority_queue<PII, vector<PII>, std::greater<PII>> q;

q.emplace(0, n);

while (!q.empty()) {

const auto [d, u] = q.top(); q.pop();

if (d > dist[u]) continue;

if (u == 1) break;

for (auto [v, w]: g[u]) {

if (dist[v] > dist[u] + w)

q.emplace(dist[v] = dist[u] + w, v);

if (dist[v] > dist[u])

dp[v] = (dp[v] + dp[u]) % kMod;

}

return dp[1];

}

};

花花酱 LeetCode 1785. Minimum Elements to Add to Form a Given Sum

By zxi on March 6, 2021

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Return the minimum number of elements you need to add to make the sum of the array equal to goal. The array must maintain its property that abs(nums[i]) <= limit.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: nums = [1,-1,1], limit = 3, goal = -4
Output: 2
Explanation: You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.

Example 2:

Input: nums = [1,-10,9,1], limit = 100, goal = 0
Output: 1

Constraints:

1 <= nums.length <= 10⁵
1 <= limit <= 10⁶
-limit <= nums[i] <= limit
-10⁹ <= goal <= 10⁹

Solution: Math

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

Compute the diff = abs(sum(nums) – goal)
ans = （diff + limit – 1)) / limit

C++

// Author: Huahua

class Solution {

public:

int minElements(vector<int>& nums, int limit, int goal) {

int64_t diff = abs(goal -

accumulate(begin(nums), end(nums), 0LL));

return (diff + limit - 1) / limit;

}

};