Posts published in “Simulation”

花花酱 LeetCode 855. Exam Room

By zxi on July 29, 2018

Problem

In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. (Also, if no one is in the room, then the student sits at seat number 0.)

Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room. It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.

Note:

1 <= N <= 10^9
ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

Solution: BST

Use a BST (ordered set) to track the current seatings.

Time Complexity:

init: O(1)

seat: O(P)

leave: O(logP)

Space complexity: O(P)

// Author: Huahua

// Running time: 24 ms

class ExamRoom {

public:

ExamRoom(int N): N_(N) {}

int seat() {

int p = 0;

int max_dist = s_.empty() ? 0 : *s_.begin();

auto left = s_.begin();

auto right = left;

while (left != s_.end()) {

++right;

int l = *left;

int r = right != s_.end() ? *right : (2 * (N_ - 1) - *left);

int d = (r - l) / 2;

if (d > max_dist) {

max_dist = d;

p = l + d;

}

left = right;

}

s_.insert(p);

return p;

}

void leave(int p) {

s_.erase(p);

}

private:

const int N_;

set<int> s_;

};

花花酱 LeetCode 43. Multiply Strings

By zxi on July 26, 2018

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Simulation

Simulate multiplication one digit at a time.

Time complexity: O(l1*l2)

Space complexity: O(l1 + l2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string multiply(string num1, string num2) {

const int l1 = num1.length();

const int l2 = num2.length();

string ans(l1 + l2, '0');

for (int i = l1 - 1; i >= 0; --i)

for (int j = l2 - 1; j >= 0; --j) {

int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');

ans[i + j + 1] = (sum % 10) + '0';

ans[i + j] += sum / 10;

}

for (int i = 0; i < ans.length(); ++i)

if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);

return "";

}

};

花花酱 LeetCode 874. Walking Robot Simulation

By zxi on July 22, 2018

Problem

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 60 ms

class Solution {

public:

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {

int x = 0;

int y = 0;

int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // WNES

int d = 1;

unordered_map<int, unordered_set<int>> o;

for (const auto obstacle : obstacles)

o[obstacle[0]].insert(obstacle[1]);

int ans = 0;

for (int c : commands) {

if (c == -2)

d = (d - 1 + 4) % 4;

else if (c == -1)

d = (d + 1) % 4;

else {

while (c--) {

int tx = x + dirs[d][0];

int ty = y + dirs[d][1];

if (o.count(tx) && o.at(tx).count(ty))

break;

x = tx;

y = ty;

ans = max(ans, x * x + y * y);

}

return ans;

}

};

花花酱 LeetCode 860. Lemonade Change

By zxi on June 30, 2018

Problem

At a lemonade stand, each lemonade costs $5.

Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills).

Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer, so that the net transaction is that the customer pays $5.

Note that you don’t have any change in hand at first.

Return true if and only if you can provide every customer with correct change.

Example 1:

Input: [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: [5,5,10]
Output: true

Example 3:

Input: [10,10]
Output: false

Example 4:

Input: [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can't give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

Solution: Simulation + Greedy

Always use 10 bill first.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

bool lemonadeChange(vector<int>& bills) {

int fives = 0;

int tens = 0;

for (const int bill : bills) {

if (bill == 5) {

++fives;

} else if (bill == 10) {

if (!fives) return false;

++tens;

--fives;

} else if (bill == 20) {

if (tens && fives) {

--tens;

--fives;

} else if (fives >= 3) {

fives -= 3;

} else {

return false;

}

return true;

}

};

花花酱 LeetCode 605. Can Place Flowers

By zxi on June 28, 2018

Problem

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots – they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

bool canPlaceFlowers(vector<int>& flowerbed, int n) {

int count = 0;

for (size_t i = 0; i < flowerbed.size() && count < n; ++i) {

if (flowerbed[i]) continue;

bool left = i == 0 ? true : !flowerbed[i - 1];

bool right = i == flowerbed.size() - 1 ? true : !flowerbed[i + 1];

if (left && right) {

flowerbed[i++] = 1;

++count;

}

return count == n;

}

};