Posts tagged as “simulation”

花花酱 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 1910. Remove All Occurrences of a Substring

By zxi on December 24, 2021

Given two strings s and part, perform the following operation on s until all occurrences of the substring part are removed:

Find the leftmost occurrence of the substring part and remove it from s.

Return s after removing all occurrences of part.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "daabcbaabcbc", part = "abc"
Output: "dab"
Explanation: The following operations are done:
- s = "daabcbaabcbc", remove "abc" starting at index 2, so s = "dabaabcbc".
- s = "dabaabcbc", remove "abc" starting at index 4, so s = "dababc".
- s = "dababc", remove "abc" starting at index 3, so s = "dab".
Now s has no occurrences of "abc".

Example 2:

Input: s = "axxxxyyyyb", part = "xy"
Output: "ab"
Explanation: The following operations are done:
- s = "axxxxyyyyb", remove "xy" starting at index 4 so s = "axxxyyyb".
- s = "axxxyyyb", remove "xy" starting at index 3 so s = "axxyyb".
- s = "axxyyb", remove "xy" starting at index 2 so s = "axyb".
- s = "axyb", remove "xy" starting at index 1 so s = "ab".
Now s has no occurrences of "xy".

Constraints:

1 <= s.length <= 1000
1 <= part.length <= 1000
s and part consists of lowercase English letters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string removeOccurrences(string s, string part) {

while (true) {

size_t i = s.find(part);

if (i == string::npos) break;

s.erase(i, part.size());

}

return s;

}

};

花花酱 LeetCode 2109. Adding Spaces to a String

By zxi on December 20, 2021

You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index.

For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee".

Return the modified string after the spaces have been added.

Example 1:

Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15]
Output: "Leetcode Helps Me Learn"
Explanation: 
The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn".
We then place spaces before those characters.

Example 2:

Input: s = "icodeinpython", spaces = [1,5,7,9]
Output: "i code in py thon"
Explanation:
The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython".
We then place spaces before those characters.

Example 3:

Input: s = "spacing", spaces = [0,1,2,3,4,5,6]
Output: " s p a c i n g"
Explanation:
We are also able to place spaces before the first character of the string.

Constraints:

1 <= s.length <= 3 * 10⁵
s consists only of lowercase and uppercase English letters.
1 <= spaces.length <= 3 * 10⁵
0 <= spaces[i] <= s.length - 1
All the values of spaces are strictly increasing.

Solution: Scan orignal string / Two Pointers

Just scan the original string and insert a space if the current index matched the front space index.

Time complexity: O(n)
Space complexity: O(m+n) / O(1)

C++

// Author: Huahua

class Solution {

public:

string addSpaces(string s, vector<int>& spaces) {

const int m = spaces.size();

string ans;

for (int i = 0, j = 0; i < s.length(); ++i) {

if (j < m && i == spaces[j]) {

ans += " ";

++j;

}

ans += s[i];

}

return ans;

}

};

花花酱 LeetCode 2105. Watering Plants II

By zxi on December 12, 2021

Problem

Solution: Simulation w/ Two Pointers

Simulate the watering process.

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

C++

// Author: Huahua

class Solution {

public:

int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {

const int n = plants.size();

int ans = 0;

for (int l = 0, r = n - 1, A = capacityA, B = capacityB; l <= r; ++l, --r) {

if (l == r)

return ans += max(A, B) < plants[l];

if ((A -= plants[l]) < 0)

A = capacityA - plants[l], ++ans;

if ((B -= plants[r]) < 0)

B = capacityB - plants[r], ++ans;

}

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;

}

};