Posts published in “Simulation”

花花酱 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;

}

};

花花酱 LeetCode 1945. Sum of Digits of String After Convert

By zxi on December 31, 2021

You are given a string s consisting of lowercase English letters, and an integer k.

First, convert s into an integer by replacing each letter with its position in the alphabet (i.e., replace 'a' with 1, 'b' with 2, …, 'z' with 26). Then, transform the integer by replacing it with the sum of its digits. Repeat the transform operation k times in total.

For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:

Convert: "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
Transform #2: 17 ➝ 1 + 7 ➝ 8

Return the resulting integer after performing the operations described above.

Example 1:

Input: s = "iiii", k = 1
Output: 36
Explanation: The operations are as follows:
- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.

Example 2:

Input: s = "leetcode", k = 2
Output: 6
Explanation: The operations are as follows:
- Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.

Example 3:

Input: s = "zbax", k = 2
Output: 8

Constraints:

1 <= s.length <= 100
1 <= k <= 10
s consists of lowercase English letters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int getLucky(string s, int k) {

int ans = 0;

for (char c : s) {

int n = c - 'a' + 1;

ans += n % 10;

ans += n / 10;

}

while (--k) {

int n = ans;

ans = 0;

while (n) {

ans += n % 10;

n /= 10;

}

return ans;

}

};

花花酱 LeetCode 2101. Detonate the Maximum Bombs

By zxi on December 12, 2021

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array bombs where bombs[i] = [x_i, y_i, r_i]. x_i and y_i denote the X-coordinate and Y-coordinate of the location of the i^th bomb, whereas r_i denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

Example 1:

Input: bombs = [[2,1,3],[6,1,4]]
Output: 2
Explanation:
The above figure shows the positions and ranges of the 2 bombs.
If we detonate the left bomb, the right bomb will not be affected.
But if we detonate the right bomb, both bombs will be detonated.
So the maximum bombs that can be detonated is max(1, 2) = 2.

Example 2:

Input: bombs = [[1,1,5],[10,10,5]]
Output: 1
Explanation:
Detonating either bomb will not detonate the other bomb, so the maximum number of bombs that can be detonated is 1.

Example 3:

Input: bombs = [[1,2,3],[2,3,1],[3,4,2],[4,5,3],[5,6,4]]
Output: 5
Explanation:
The best bomb to detonate is bomb 0 because:
- Bomb 0 detonates bombs 1 and 2. The red circle denotes the range of bomb 0.
- Bomb 2 detonates bomb 3. The blue circle denotes the range of bomb 2.
- Bomb 3 detonates bomb 4. The green circle denotes the range of bomb 3.
Thus all 5 bombs are detonated.

Constraints:

1 <= bombs.length <= 100
bombs[i].length == 3
1 <= x_i, y_i, r_i <= 10⁵

Solution: Simulation w/ BFS

Enumerate the bomb to detonate, and simulate the process using BFS.

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

C++

// Author: Huahua

class Solution {

public:

int maximumDetonation(vector<vector<int>>& bombs) {

const int n = bombs.size();

auto check = [&](int i, int j) -> bool {

long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2];

long x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2];

return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r1 * r1);

};

int ans = 0;

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

int count = 0;

queue<int> q{{s}};

vector<int> seen(n);

seen[s] = 1;

while (!q.empty()) {

++count;

int i = q.front(); q.pop();

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

if (check(i, j) && !seen[j]++)

q.push(j);

}

ans = max(ans, count);

}

return ans;

}

};