Posts published in “Simulation”

Problem

Given an integer, return its base 7 string representation.

Example 1:

Input: 100
Output: "202"

Example 2:

Input: -7
Output: "-10"

Note: The input will be in range of [-1e7, 1e7].

Solution: Simulation

Time complexity: O(logn)

Space complexity: O(logn)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string convertToBase7(int num) {

bool is_nagetive = num<0;

num = abs(num);

string ans;

do {

ans += ('0' + (num % 7));

num /= 7;

} while (num > 0);

if (is_nagetive)

ans += "-";

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 551. Student Attendance Record I

By zxi on August 17, 2018

Problem

You are given a string representing an attendance record for a student. The record only contains the following three characters:

‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.

A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False

Solution1: Simulation

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

bool checkRecord(string s) {

int a{0};

int l{0};

for(char c: s) {

if (c == 'A') ++a;

if (c == 'L') ++l;

else l=0;

if (a > 1 || l > 2) return false;

}

return true;

}

};

Solution 2: Regex

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

bool checkRecord(string s) {

return !std::regex_search(s, std::regex("A.*A|LLL"));

}

};

花花酱 LeetCode 889. Spiral Matrix III

By zxi on August 13, 2018

Problem

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

Solution: Simulation

We can find out the moving sequence is ESWWNNEEESSSWWWWNNNN.

The pattern is 1,1,2,2,3,3,4,4,… steps in one direction, and turn right for 90 degrees.

directions are E,S,W,N,E,S,W,N…

Time complexity: O(max(R,C)^2)

Space complexity: O(1) or O(RC) if ans included.

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

int k = 0;

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

int d = 0; // E

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

while (++k) {

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

for (int j = 0; j < k; ++j) {

c0 += dirs[d][0];

r0 += dirs[d][1];

if (c0 < 0 || c0 >= C || r0 < 0 || r0 >= R) continue;

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

}

d = (d + 1) % 4;

}

return {};

}

};

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 "";

}

};

Posts published in “Simulation”

花花酱 LeetCode 504. Base 7

Problem

Solution: Simulation

花花酱 LeetCode 551. Student Attendance Record I

Problem

Solution1: Simulation

Solution 2: Regex

花花酱 LeetCode 889. Spiral Matrix III

Problem

Solution: Simulation

花花酱 LeetCode 855. Exam Room

Problem

Solution: BST

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation