Posts tagged as “simulation”

花花酱 LeetCode 838. Push Dominoes

By zxi on May 6, 2019

here are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L‘, 'R' and '.'

Solution: Simulation

Simulate the push process, record the steps from L and R for each domino.
steps(L) == steps(R) => “.”
steps(L) < steps(R) => “L”
steps(L) > steps(R) => “R”

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

C++

// Author: Huahua, running time: 24 ms, 15.2 MB

class Solution {

public:

string pushDominoes(string D) {

const int n = static_cast<int>(D.size());

vector<int> L(n, INT_MAX), R(n, INT_MAX);

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

if (D[i] == 'L') {

L[i] = 0;

for (int j = i - 1; j >= 0 && D[j] == '.'; --j)

L[j] = L[j + 1] + 1;

} else if (D[i] == 'R') {

R[i] = 0;

for (int j = i + 1; j < n && D[j] == '.'; ++j)

R[j] = R[j - 1] + 1;

}

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

if (L[i] < R[i]) D[i] = 'L';

else if (L[i] > R[i]) D[i] = 'R';

return D;

}

};

花花酱 LeetCode 38. Count and Say

By zxi on April 17, 2019

Problem

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the n^th term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Solution: Recursion + Simulation

C++

// Author: Huahua, 4 ms, 8.6 MB

class Solution {

public:

string countAndSay(int n) {

string ans = "1";

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

ans = say(ans);

return ans;

}

private:

string say(const string& n){

string ans;

int s = 0, l = n.length();

for (int e = 1; e <= l; ++e)

if (e == l || n[s] != n[e]) {

int count = e - s;

ans += '0' + count;

ans += n[s];

s = e;

}

return ans;

}

};

花花酱 LeetCode 54. Spiral Matrix

By zxi on April 12, 2019

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Solution: Simulation

Keep track of the current bounds (left, right, top, bottom).

Init: left = 0, right = n – 1, top = 0, bottom = m – 1

Each time we move in one direction and shrink the bounds and turn 90 degrees:
1. go right => –top
2. go down => –right
3. go left => ++bottom
4. go up => ++left

C++

class Solution {

public:

vector<int> spiralOrder(vector<vector<int>>& matrix) {

if (matrix.empty()) return {};

int l = 0;

int t = 0;

int r = matrix[0].size();

int b = matrix.size();

const int total = (r--) * (b--);

int d = 0;

int x = 0;

int y = 0;

vector<int> ans;

while (ans.size() < total - 1) {

if (d == 0) {

while (x < r) ans.push_back(matrix[y][x++]);

++t;

} else if (d == 1) {

while (y < b) ans.push_back(matrix[y++][x]);

--r;

} else if (d == 2) {

while (x > l) ans.push_back(matrix[y][x--]);

--b;

} else if (d == 3) {

while (y > t) ans.push_back(matrix[y--][x]);

++l;

}

d = (d + 1) % 4;

}

if (ans.size() != total) ans.push_back(matrix[y][x]);

return ans;

}

};

花花酱 LeetCode 1011. Capacity To Ship Packages Within D Days

By zxi on March 16, 2019

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Note:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Solution: Binary Search

Find the smallest capacity such that can finish in D days.

Time complexity: O(n * log(sum(weights))
Space complexity: O(1)

C++

// Author: Huahua, running time: 52 ms, 11.9 MB

class Solution {

public:

int shipWithinDays(vector<int>& weights, int D) {

int l = *max_element(begin(weights), end(weights));

int r = accumulate(begin(weights), end(weights), 0) + 1;

while (l < r) {

int m = l + (r - l) / 2;

int d = 1;

int t = 0;

for (int w : weights)

if ((t += w) > m) {

t = w;

++d;

}

d > D ? l = m + 1 : r = m;

}

return l;

}

};

花花酱 LeetCode 1006. Clumsy Factorial

By zxi on March 9, 2019

Normally, the factorial of a positive integer n is the product of all positive integers less than or equal to n. For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.

For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that 10 * 9 / 8 equals 11. This guarantees the result is an integer.

Implement the clumsy function as defined above: given an integer N, it returns the clumsy factorial of N.

Example 1:

Input: 4
Output: 7
Explanation: 7 = 4 * 3 / 2 + 1

Example 2:

Input: 10
Output: 12
Explanation: 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

Note:

1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 (The answer is guaranteed to fit within a 32-bit integer.)

Solution: Simulation

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

C++

// Author: Huahua 4ms 8.2 MB

class Solution {

public:

int clumsy(int N) {

if (N <= 0) return 0;

if (N == 1) return 1;

if (N == 2) return 2 * 1;

if (N == 3) return 3 * 2 / 1;

int ans = N * (N - 1) / (N - 2) + (N - 3);

while ((N -= 4) >= 4)

ans = ans - N * (N - 1) / (N - 2) + (N - 3);

return ans - clumsy(N);

}

};