Posts published in “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 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;

}

};

花花酱 LeetCode 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

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

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 LeetCode 118. Pascal’s Triangle

By zxi on November 27, 2021

Given an integer numRows, return the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

1 <= numRows <= 30

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> ans(numRows);

for (int i = 0; i < numRows;++i) {

ans[i].resize(i + 1);

ans[i][0] = ans[i][i] = 1;

for (int j = 1; j < i; ++j)

ans[i][j] = ans[i-1][j] + ans[i-1][j-1];

}

return ans;

}

花花酱 LeetCode 2079. Watering Plants

By zxi on November 20, 2021

You want to water n plants in your garden with a watering can. The plants are arranged in a row and are labeled from 0 to n - 1 from left to right where the i^th plant is located at x = i. There is a river at x = -1 that you can refill your watering can at.

Each plant needs a specific amount of water. You will water the plants in the following way:

Water the plants in order from left to right.
After watering the current plant, if you do not have enough water to completely water the next plant, return to the river to fully refill the watering can.
You cannot refill the watering can early.

You are initially at the river (i.e., x = -1). It takes one step to move one unit on the x-axis.

Given a 0-indexed integer array plants of n integers, where plants[i] is the amount of water the i^th plant needs, and an integer capacity representing the watering can capacity, return the number of steps needed to water all the plants.

Example 1:

Input: plants = [2,2,3,3], capacity = 5
Output: 14
Explanation: Start at the river with a full watering can:
- Walk to plant 0 (1 step) and water it. Watering can has 3 units of water.
- Walk to plant 1 (1 step) and water it. Watering can has 1 unit of water.
- Since you cannot completely water plant 2, walk back to the river to refill (2 steps).
- Walk to plant 2 (3 steps) and water it. Watering can has 2 units of water.
- Since you cannot completely water plant 3, walk back to the river to refill (3 steps).
- Walk to plant 3 (4 steps) and water it.
Steps needed = 1 + 1 + 2 + 3 + 3 + 4 = 14.

Example 2:

Input: plants = [1,1,1,4,2,3], capacity = 4
Output: 30
Explanation: Start at the river with a full watering can:
- Water plants 0, 1, and 2 (3 steps). Return to river (3 steps).
- Water plant 3 (4 steps). Return to river (4 steps).
- Water plant 4 (5 steps). Return to river (5 steps).
- Water plant 5 (6 steps).
Steps needed = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30.

Example 3:

Input: plants = [7,7,7,7,7,7,7], capacity = 8
Output: 49
Explanation: You have to refill before watering each plant.
Steps needed = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49.

Constraints:

n == plants.length
1 <= n <= 1000
1 <= plants[i] <= 10⁶
max(plants[i]) <= capacity <= 10⁹

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int wateringPlants(vector<int>& plants, int capacity) {

const int n = plants.size();

int ans = 0;

for (int i = 0, c = capacity; i < n; c -= plants[i++], ++ans) {

if (c >= plants[i]) continue;

ans += i * 2;

c = capacity;

}

return ans;

}

};

Posts published in “Simulation”

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

Solution: Simulation

C++

花花酱 LeetCode 2101. Detonate the Maximum Bombs

Solution: Simulation w/ BFS

C++

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

花花酱 LeetCode 118. Pascal’s Triangle

Solution: Simulation

C++

Related Problems

花花酱 LeetCode 2079. Watering Plants

Solution: Simulation

C++