Posts tagged as “simulation”

花花酱 LeetCode 999. Available Captures for Rook

By zxi on February 24, 2019

On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters ‘R’, ‘.’, ‘B’, and ‘p’ respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move into the same square as other friendly bishops.

Return the number of pawns the rook can capture in one move.

Example 1:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation: 
In this example the rook is able to capture all the pawns.

Example 2:

Input: [[".",".",".",".",".",".",".","."],[".","p","p","p","p","p",".","."],[".","p","p","B","p","p",".","."],[".","p","B","R","B","p",".","."],[".","p","p","B","p","p",".","."],[".","p","p","p","p","p",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 0
Explanation: 
Bishops are blocking the rook to capture any pawn.

Example 3:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]
Output: 3
Explanation: 
The rook can capture the pawns at positions b5, d6 and f5.

Note:

board.length == board[i].length == 8
board[i][j] is either 'R', '.', 'B', or 'p'
There is exactly one cell with board[i][j] == 'R'

Solution: Simulation

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

C++

class Solution {

public:

int numRookCaptures(vector<vector<char>>& board) {

int ans = 0;

auto check = [&board](int x, int y, int dx, int dy) {

x += dx;

y += dy;

while (x >= 0 && x < 8 && y >= 0 && y < 8) {

if (board[y][x] == 'p') return 1;

if (board[y][x] != '.') break;

x += dx;

y += dy;

}

return 0;

};

array<int, 5> dirs{1, 0, -1, 0, 1};

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

for (int j = 0; j < 8; ++j)

if (board[i][j] == 'R')

for (int d = 0; d < 4; ++d)

ans += check(j, i, dirs[d], dirs[d + 1]);

return ans;

}

};

花花酱 LeetCode 989. Add to Array-Form of Integer

By zxi on February 10, 2019

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0

Solution: Simulation

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

C++

// Author: Huahua, running time: 136 ms, 10.1 MB

class Solution {

public:

vector<int> addToArrayForm(vector<int>& A, int K) {

vector<int> ans;

ans.reserve(A.size() + 1);

for (int i = A.size() - 1; i >= 0 || K > 0; --i) {

K += (i >= 0 ? A[i] : 0);

ans.push_back(K % 10);

K /= 10;

}

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

return ans;

}

};

花花酱 LeetCode 985. Sum of Even Numbers After Queries

By zxi on February 2, 2019

Problem

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length

Solution: Simulation

Time complexity: O(n + |Q|)
Space complexity: O(n)

C++

// Author: Huahua, Running time: 100 ms / 6.5 MB

class Solution {

public:

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {

int sum = 0;

for (int i = 0; i < A.size(); ++i)

if (A[i] % 2 == 0)

sum += A[i];

vector<int> ans;

for (const auto& query : queries) {

int& a = A[query[1]];

if (a % 2 == 0)

sum -= a;

a += query[0];

if (a % 2 == 0)

sum += a;

ans.push_back(sum);

}

return ans;

}

};

Python3

# Author: Huahua, running time: 188 ms / 16.4MB

class Solution:

def sumEvenAfterQueries(self, A: 'List[int]', queries: 'List[List[int]]') -> 'List[int]':

s = sum(x for x in A if x % 2 == 0)

ans = []

for val, index in queries:

if A[index] % 2 == 0: s -= A[index]

A[index] += val

if A[index] % 2 == 0: s += A[index]

ans.append(s)

return ans

花花酱 LeetCode 936. Stamping The Sequence

By zxi on December 8, 2018

Problem

You want to form a target string of lowercase letters.

At the beginning, your sequence is target.length '?' marks. You also have a stamp of lowercase letters.

On each turn, you may place the stamp over the sequence, and replace every letter in the sequence with the corresponding letter from the stamp. You can make up to 10 * target.length turns.

For example, if the initial sequence is “?????”, and your stamp is "abc", then you may make “abc??”, “?abc?”, “??abc” in the first turn. (Note that the stamp must be fully contained in the boundaries of the sequence in order to stamp.)

If the sequence is possible to stamp, then return an array of the index of the left-most letter being stamped at each turn. If the sequence is not possible to stamp, return an empty array.

For example, if the sequence is “ababc”, and the stamp is "abc", then we could return the answer [0, 2], corresponding to the moves “?????” -> “abc??” -> “ababc”.

Also, if the sequence is possible to stamp, it is guaranteed it is possible to stamp within 10 * target.length moves. Any answers specifying more than this number of moves will not be accepted.

Example 1:

Input: stamp = "abc", target = "ababc"
Output: [0,2]
([1,0,2] would also be accepted as an answer, as well as some other answers.)

Example 2:

Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]

Note:

1 <= stamp.length <= target.length <= 1000
stamp and target only contain lowercase letters.

Solution: Greedy + Reverse Simulation

Reverse the stamping process. Each time find a full or partial match. Replace the matched char to ‘?’.

Don’t forget the reverse the answer as well.

T = “ababc”, S = “abc”

T = “ab???”, index = 2

T = “?????”, index = 0

ans = [0, 2]

Time complexity: O((T – S)*S)

Space complexity: O(T)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

vector<int> movesToStamp(string stamp, string target) {

vector<int> ans;

vector<int> seen(target.length());

int total = 0;

while (total < target.length()) {

bool found = false;

for (int i = 0; i <= target.length() - stamp.length(); ++i) {

if (seen[i]) continue;

int l = unStamp(stamp, target, i);

if (l == 0) continue;

seen[i] = 1;

total += l;

ans.push_back(i);

found = true;

}

if (!found) return {};

}

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

return ans;

}

private:

int unStamp(const string& stamp, string& target, int s) {

int l = stamp.size();

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

if (target[s + i] == '?')

--l;

else if (target[s + i] != stamp[i])

return 0;

}

if (l != 0)

std::fill(begin(target) + s, begin(target) + s + stamp.length(), '?');

return l;

}

};

花花酱 LeetCode 946. Validate Stack Sequences

By zxi on November 29, 2018

Problem

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Note:

0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.

Solution: Simulation

Simulate the push/pop operation.

Push element from |pushed sequence| onto stack s one by one and pop when top of the stack s is equal the current element in the |popped sequence|.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

stack<int> s;

auto it = begin(popped);

for (int e : pushed) {

s.push(e);

while (!s.empty() && s.top() == *it) {

s.pop();

++it;

}

return it == end(popped);

}

};

Python3

# Author: Huahua, Running time: 40 ms

class Solution:

def validateStackSequences(self, pushed, popped):

s = []

i = 0

for e in pushed:

s.append(e)

while s and s[-1] == popped[i]:

s.pop()

i += 1

return i == len(popped)