Posts tagged as “simulation”

花花酱 LeetCode 1860. Incremental Memory Leak

By zxi on June 1, 2021

You are given two integers memory1 and memory2 representing the available memory in bits on two memory sticks. There is currently a faulty program running that consumes an increasing amount of memory every second.

At the i^th second (starting from 1), i bits of memory are allocated to the stick with more available memory (or from the first memory stick if both have the same available memory). If neither stick has at least i bits of available memory, the program crashes.

Return an array containing [crashTime, memory1_crash, memory2_crash], where crashTime is the time (in seconds) when the program crashed and memory1_crash and memory2_crash are the available bits of memory in the first and second sticks respectively.

Example 1:

Input: memory1 = 2, memory2 = 2
Output: [3,1,0]
Explanation: The memory is allocated as follows:
- At the 1^st second, 1 bit of memory is allocated to stick 1. The first stick now has 1 bit of available memory.
- At the 2^nd second, 2 bits of memory are allocated to stick 2. The second stick now has 0 bits of available memory.
- At the 3^rd second, the program crashes. The sticks have 1 and 0 bits available respectively.

Example 2:

Input: memory1 = 8, memory2 = 11
Output: [6,0,4]
Explanation: The memory is allocated as follows:
- At the 1^st second, 1 bit of memory is allocated to stick 2. The second stick now has 10 bit of available memory.
- At the 2^nd second, 2 bits of memory are allocated to stick 2. The second stick now has 8 bits of available memory.
- At the 3^rd second, 3 bits of memory are allocated to stick 1. The first stick now has 5 bits of available memory.
- At the 4^th second, 4 bits of memory are allocated to stick 2. The second stick now has 4 bits of available memory.
- At the 5^th second, 5 bits of memory are allocated to stick 1. The first stick now has 0 bits of available memory.
- At the 6^th second, the program crashes. The sticks have 0 and 4 bits available respectively.

Constraints:

0 <= memory1, memory2 <= 2³¹ - 1

Solution: Simulation

Time complexity: O(max(memory1, memory2)^0.5)
Space complexity: O(1)

Python3

class Solution:

def memLeak(self, memory1: int, memory2: int) -> List[int]:

for i in range(1, 2**30):

if max(memory1, memory2) < i:

return [i, memory1, memory2]

elif memory1 >= memory2:

memory1 -= i

else:

memory2 -= i

return None

花花酱 LeetCode 1854. Maximum Population Year

By zxi on May 8, 2021

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i^th person.

The population of some year x is the number of people alive during that year. The i^th person is counted in year x‘s population if x is in the inclusive range [birth_i, death_i - 1]. Note that the person is not counted in the year that they die.

Return the earliest year with the maximum population.

Example 1:

Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: The maximum population is 1, and 1993 is the earliest year with this population.

Example 2:

Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation: 
The maximum population is 2, and it had happened in years 1960 and 1970.
The earlier year between them is 1960.

Constraints:

1 <= logs.length <= 100
1950 <= birth_i < death_i <= 2050

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int maximumPopulation(vector<vector<int>>& logs) {

vector<int> pop(2051);

for (const auto& log : logs) {

for (int y = log[0]; y < log[1]; ++y)

++pop[y];

}

int ans = -1;

int max_pop = 0;

for (int y = 1950; y <= 2050; ++y) {

if (pop[y] > max_pop) {

max_pop = pop[y];

ans = y;

}

return ans;

}

};

花花酱 LeetCode 1834. Single-Threaded CPU

By zxi on April 18, 2021

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10⁵
1 <= enqueueTime_i, processingTime_i <= 10⁹

Solution: Simulation w/ Sort + PQ

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getOrder(vector<vector<int>>& tasks) {

const int n = tasks.size();

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

tasks[i].push_back(i);

sort(begin(tasks), end(tasks)); // sort by enqueue_time;

vector<int> ans;

priority_queue<pair<int, int>> q; // {-processing_time, -index}

int i = 0;

long t = 0;

while (ans.size() != n) {

// Advance to next enqueue time if q is empty.

if (i < n && q.empty() && tasks[i][0] > t)

t = tasks[i][0];

// Enqueue all available tasks.

while (i < n && tasks[i][0] <= t) {

q.emplace(-tasks[i][1], -tasks[i][2]);

++i;

}

// Extra the top one.

t -= q.top().first;

ans.push_back(-q.top().second);

q.pop();

}

return ans;

}

};

花花酱 LeetCode 1823. Find the Winner of the Circular Game

By zxi on April 12, 2021

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the i^th friend brings you to the (i+1)^th friend for 1 <= i < n, and moving clockwise from the n^th friend brings you to the 1^st friend.

The rules of the game are as follows:

Start at the 1^st friend.
Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
The last friend you counted leaves the circle and loses the game.
If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

Example 1:

Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.

Example 2:

Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.

Constraints:

1 <= k <= n <= 500

Solution 1: Simulation w/ Queue / List

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

C++/Queue

// Author: Huahua, 56 ms, 24.3 MB

class Solution {

public:

int findTheWinner(int n, int k) {

queue<int> q;

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

q.push(i);

while (q.size() != 1) {

for (int i = 1; i < k; ++i) {

int x = q.front();

q.pop();

q.push(x);

}

q.pop();

}

return q.front();

}

};

C++/List

// Author: Huahua, 12 ms, 6.8 MB

class Solution {

public:

int findTheWinner(int n, int k) {

list<int> l;

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

l.push_back(i);

auto it = l.begin();

while (l.size() != 1) {

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

if (++it == l.end())

it = l.begin();

it = l.erase(it);

if (it == l.end())

it = l.begin();

}

return l.front();

}

};

花花酱 LeetCode 1807. Evaluate the Bracket Pairs of a String

By zxi on March 27, 2021

You are given a string s that contains some bracket pairs, with each pair containing a non-empty key.

For example, in the string "(name)is(age)yearsold", there are two bracket pairs that contain the keys "name" and "age".

You know the values of a wide range of keys. This is represented by a 2D string array knowledge where each knowledge[i] = [key_i, value_i] indicates that key key_i has a value of value_i.

You are tasked to evaluate all of the bracket pairs. When you evaluate a bracket pair that contains some key key_i, you will:

Replace key_i and the bracket pair with the key’s corresponding value_i.
If you do not know the value of the key, you will replace key_i and the bracket pair with a question mark "?" (without the quotation marks).

Each key will appear at most once in your knowledge. There will not be any nested brackets in s.

Return the resulting string after evaluating all of the bracket pairs.

Example 1:

Input: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]
Output: "bobistwoyearsold"
Explanation:
The key "name" has a value of "bob", so replace "(name)" with "bob".
The key "age" has a value of "two", so replace "(age)" with "two".

Example 2:

Input: s = "hi(name)", knowledge = [["a","b"]]
Output: "hi?"
Explanation: As you do not know the value of the key "name", replace "(name)" with "?".

Example 3:

Input: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]
Output: "yesyesyesaaa"
Explanation: The same key can appear multiple times.
The key "a" has a value of "yes", so replace all occurrences of "(a)" with "yes".
Notice that the "a"s not in a bracket pair are not evaluated.

Example 4:

Input: s = "(a)(b)", knowledge = [["a","b"],["b","a"]]
Output: "ba"

Constraints:

1 <= s.length <= 10⁵
0 <= knowledge.length <= 10⁵
knowledge[i].length == 2
1 <= key_i.length, value_i.length <= 10
s consists of lowercase English letters and round brackets '(' and ')'.
Every open bracket '(' in s will have a corresponding close bracket ')'.
The key in each bracket pair of s will be non-empty.
There will not be any nested bracket pairs in s.
key_i and value_i consist of lowercase English letters.
Each key_i in knowledge is unique.

Solution: Hashtable + Simulation

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

C++

// Author: Huahua

class Solution {

public:

string evaluate(string s, vector<vector<string>>& knowledge) {

unordered_map<string, string> m;

for (const auto& p : knowledge)

m[p[0]] = p[1];

string ans;

string cur;

bool in = false;

for (char c : s) {

if (c == '(') {

in = true;

} else if (c == ')') {

if (m.count(cur))

ans += m[cur];

else

ans += "?";

cur.clear();

in = false;

} else {

if (!in) ans += c;

else cur += c;

}

return ans;

}

};