Posts published in “Simulation”

花花酱 LeetCode 2660. Determine the Winner of a Bowling Game

By zxi on April 30, 2023

You are given two 0-indexed integer arrays player1 and player2, that represent the number of pins that player 1 and player 2 hit in a bowling game, respectively.

The bowling game consists of n turns, and the number of pins in each turn is exactly 10.

Assume a player hit x_i pins in the i^th turn. The value of the i^th turn for the player is:

2x_i if the player hit 10 pins in any of the previous two turns.
Otherwise, It is x_i.

The score of the player is the sum of the values of their n turns.

Return

1 if the score of player 1 is more than the score of player 2,
2 if the score of player 2 is more than the score of player 1, and
0 in case of a draw.

Example 1:

Input: player1 = [4,10,7,9], player2 = [6,5,2,3]
Output: 1
Explanation: The score of player1 is 4 + 10 + 2*7 + 2*9 = 46.
The score of player2 is 6 + 5 + 2 + 3 = 16.
Score of player1 is more than the score of player2, so, player1 is the winner, and the answer is 1.

Example 2:

Input: player1 = [3,5,7,6], player2 = [8,10,10,2]
Output: 2
Explanation: The score of player1 is 3 + 5 + 7 + 6 = 21.
The score of player2 is 8 + 10 + 2*10 + 2*2 = 42.
Score of player2 is more than the score of player1, so, player2 is the winner, and the answer is 2.

Example 3:

Input: player1 = [2,3], player2 = [4,1]
Output: 0
Explanation: The score of player1 is 2 + 3 = 5
The score of player2 is 4 + 1 = 5
The score of player1 equals to the score of player2, so, there is a draw, and the answer is 0.

Constraints:

n == player1.length == player2.length
1 <= n <= 1000
0 <= player1[i], player2[i] <= 10

Solution: Simulation

We can write a function to compute the score of a player.

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

C++

// Author: Huahua

class Solution {

public:

int isWinner(vector<int>& player1, vector<int>& player2) {

auto score = [] (const vector<int>& player) {

int sum = 0;

int twice = 0;

for (int x : player) {

sum += twice-- > 0 ? x * 2 : x;

if (x == 10) twice = 2;

}

return sum;

};

int s1 = score(player1);

int s2 = score(player2);

if (s1 == s2) return 0;

return s1 > s2 ? 1 : 2;

}

};

花花酱 LeetCode 2639. Find the Width of Columns of a Grid

By zxi on April 29, 2023

You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.

For example, if grid = [[-10], [3], [12]], the width of the only column is 3 since -10 is of length 3.

Return an integer array ans of size n where ans[i] is the width of the i^th column.

The length of an integer x with len digits is equal to len if x is non-negative, and len + 1 otherwise.

Example 1:

Input: grid = [[1],[22],[333]]
Output: [3]
Explanation: In the 0^th column, 333 is of length 3.

Example 2:

Input: grid = [[-15,1,3],[15,7,12],[5,6,-2]]
Output: [3,1,2]
Explanation: 
In the 0^th column, only -15 is of length 3.
In the 1^st column, all integers are of length 1. 
In the 2^nd column, both 12 and -2 are of length 2.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-10⁹ <= grid[r][c] <= 10⁹

Solution: Simulation

Note: width of ‘0’ is 1.

Time complexity: O(m*n*log(x))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> findColumnWidth(vector<vector<int>>& grid) {

vector<int> ans;

for (int j = 0; j < grid[0].size(); ++j) {

int maxWidth = 1;

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

int x = grid[i][j];

int width = 0;

if (x < 0) {

x = -x;

++width;

}

while (x) {

x /= 10;

++width;

}

maxWidth = max(maxWidth, width);

}

ans.push_back(maxWidth);

}

return ans;

}

};

花花酱 LeetCode 2257. Count Unguarded Cells in the Grid

By zxi on May 1, 2022

You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [row_i, col_i] and walls[j] = [row_j, col_j] represent the positions of the i^th guard and j^th wall respectively.

A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it.

Return the number of unoccupied cells that are not guarded.

Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

Example 2:

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

Constraints:

1 <= m, n <= 10⁵
2 <= m * n <= 10⁵
1 <= guards.length, walls.length <= 5 * 10⁴
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= row_i, row_j < m
0 <= col_i, col_j < n
All the positions in guards and walls are unique.

Solution: Simulation

Enumerate each cell, for each guard, shoot rays to 4 directions, mark cells on the way to 1 and stop when hit a guard or a wall.

Time complexity: O(mn)
Space complexity: O(mn)

C++

// Author: Huahua

class Solution {

public:

int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {

vector<vector<int>> s(m, vector<int>(n));

for (const auto& g : guards)

s[g[0]][g[1]] = 2;

for (const auto& w : walls)

s[w[0]][w[1]] = 3;

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

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

if (s[i][j] != 2) continue;

for (int y = i - 1; y >= 0; s[y--][j] = 1)

if (s[y][j] >= 2) break;

for (int y = i + 1; y < m; s[y++][j] = 1)

if (s[y][j] >= 2) break;

for (int x = j - 1; x >= 0; s[i][x--] = 1)

if (s[i][x] >= 2) break;

for (int x = j + 1; x < n; s[i][x++] = 1)

if (s[i][x] >= 2) break;

}

int ans = 0;

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

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

ans += !s[i][j];

return ans;

}

};

花花酱 LeetCode 2221. Find Triangular Sum of an Array

By zxi on April 2, 2022

You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the value of the only element present in nums after the following process terminates:

Let nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
For each index i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
Replace the array nums with newNums.
Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Example 1:

Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2:

Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 9

Solution 1: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int triangularSum(vector<int>& nums) {

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

vector<int> next(nums.size() - 1);

for (size_t i = 0; i < nums.size() - 1; ++i)

next[i] = (nums[i] + nums[i + 1]) % 10;

swap(next, nums);

}

return nums[0];

}

};

花花酱 LeetCode 2169. Count Operations to Obtain Zero

By zxi on February 13, 2022

You are given two non-negative integers num1 and num2.

In one operation, if num1 >= num2, you must subtract num2 from num1, otherwise subtract num1 from num2.

For example, if num1 = 5 and num2 = 4, subtract num2 from num1, thus obtaining num1 = 1 and num2 = 4. However, if num1 = 4 and num2 = 5, after one operation, num1 = 4 and num2 = 1.

Return the number of operations required to make either num1 = 0 or num2 = 0.

Example 1:

Input: num1 = 2, num2 = 3
Output: 3
Explanation: 
- Operation 1: num1 = 2, num2 = 3. Since num1 < num2, we subtract num1 from num2 and get num1 = 2, num2 = 3 - 2 = 1.
- Operation 2: num1 = 2, num2 = 1. Since num1 > num2, we subtract num2 from num1.
- Operation 3: num1 = 1, num2 = 1. Since num1 == num2, we subtract num2 from num1.
Now num1 = 0 and num2 = 1. Since num1 == 0, we do not need to perform any further operations.
So the total number of operations required is 3.

Example 2:

Input: num1 = 10, num2 = 10
Output: 1
Explanation: 
- Operation 1: num1 = 10, num2 = 10. Since num1 == num2, we subtract num2 from num1 and get num1 = 10 - 10 = 0.
Now num1 = 0 and num2 = 10. Since num1 == 0, we are done.
So the total number of operations required is 1.

Constraints:

0 <= num1, num2 <= 10⁵

Solution 1: Simulation

Time complexity: O(max(n,m) / min(n, m))
Space complexity: O(1)

No code

Solution 2: Simualtion + Math

For the case of 100, 3
100 – 3 = 97
97 – 3 = 94
…
4 – 3 = 1
Swap
3 – 1 = 2
2 – 1 = 1
1 – 1 = 0
It takes 36 steps.

We can do 100 / 3 to skip 33 steps
100 %= 3 = 1
3 / 1 = 3 to skip 3 steps
3 %= 1 = 0
total is 33 + 3 = 36.

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

C++

// Author: Huahua

class Solution {

public:

int countOperations(int num1, int num2) {

int ans = 0;

while (num1 && num2) {

if (num1 < num2) swap(num1, num2);

ans += num1 / num2;

num1 %= num2;

}

return ans;

}

};