Posts tagged as “simulation”

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

}

};

花花酱 LeetCode 2154. Keep Multiplying Found Values by Two

By zxi on February 4, 2022

You are given an array of integers nums. You are also given an integer original which is the first number that needs to be searched for in nums.

You then do the following steps:

If original is found in nums, multiply it by two (i.e., set original = 2 * original).
Otherwise, stop the process.
Repeat this process with the new number as long as you keep finding the number.

Return the final value of original.

Example 1:

Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation: 
- 3 is found in nums. 3 is multiplied by 2 to obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 24.
- 24 is not found in nums. Thus, 24 is returned.

Example 2:

Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
- 4 is not found in nums. Thus, 4 is returned.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i], original <= 1000

Solution: Hashset

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

C++

// Author: Huahua

class Solution {

public:

int findFinalValue(vector<int>& nums, int original) {

unordered_set<int> s(begin(nums), end(nums));

while (true) {

if (!s.count(original)) break;

original *= 2;

}

return original;

}

};