Huahua’s Tech Road

花花酱 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 1942. The Number of the Smallest Unoccupied Chair

By zxi on December 31, 2021

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrival_i, leaving_i], indicating the arrival and leaving times of the i^th friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

Constraints:

n == times.length
2 <= n <= 10⁴
times[i].length == 2
1 <= arrival_i < leaving_i <= 10⁵
0 <= targetFriend <= n - 1
Each arrival_i time is distinct.

Solution: Treeset + Simulation

Use a treeset to track available chairs, sort events by time.
note: process leaving events first.

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

C++

// Author: Huahua

class Solution {

public:

int smallestChair(vector<vector<int>>& times, int targetFriend) {

const int n = times.size();

vector<pair<int, int>> arrival(n);

vector<pair<int, int>> leaving(n);

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

arrival[i] = {times[i][0], i};

leaving[i] = {times[i][1], i};

}

vector<int> pos(n);

iota(begin(pos), end(pos), 0); // pos = [0, 1, ..., n -1]

set<int> aval(begin(pos), end(pos));

sort(begin(arrival), end(arrival));

sort(begin(leaving), end(leaving));

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

const auto [t, u] = arrival[i];

while (j < n && leaving[j].first <= t)

aval.insert(pos[leaving[j++].second]);

aval.erase(pos[u] = *begin(aval));

if (u == targetFriend) return pos[u];

}

return -1;

}

};

花花酱 LeetCode 1941. Check if All Characters Have Equal Number of Occurrences

By zxi on December 31, 2021

Given a string s, return true if s is a good string, or false otherwise.

A string s is good if all the characters that appear in s have the same number of occurrences (i.e., the same frequency).

Example 1:

Input: s = "abacbc"
Output: true
Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:

Input: s = "aaabb"
Output: false
Explanation: The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

Constraints:

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

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

bool areOccurrencesEqual(string s) {

vector<int> m(26);

int maxCount = 0;

for (char c : s)

maxCount = max(maxCount, ++m[c - 'a']);

return all_of(begin(m), end(m), [maxCount](int c) -> bool {

return c == 0 || c == maxCount;

});

}

};

Python3

# Author: Huahua

class Solution:

def areOccurrencesEqual(self, s: str) -> bool:

return len(set(Counter(s).values())) == 1

花花酱 LeetCode 1936. Add Minimum Number of Rungs

By zxi on December 31, 2021

You are given a strictly increasing integer array rungs that represents the height of rungs on a ladder. You are currently on the floor at height 0, and you want to reach the last rung.

You are also given an integer dist. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is at most dist. You are able to insert rungs at any positive integer height if a rung is not already there.

Return the minimum number of rungs that must be added to the ladder in order for you to climb to the last rung.

Example 1:

Input: rungs = [1,3,5,10], dist = 2
Output: 2
Explanation:
You currently cannot reach the last rung.
Add rungs at heights 7 and 8 to climb this ladder. 
The ladder will now have rungs at [1,3,5,7,8,10].

Example 2:

Input: rungs = [3,6,8,10], dist = 3
Output: 0
Explanation:
This ladder can be climbed without adding additional rungs.

Example 3:

Input: rungs = [3,4,6,7], dist = 2
Output: 1
Explanation:
You currently cannot reach the first rung from the ground.
Add a rung at height 1 to climb this ladder.
The ladder will now have rungs at [1,3,4,6,7].

Constraints:

1 <= rungs.length <= 10⁵
1 <= rungs[i] <= 10⁹
1 <= dist <= 10⁹
rungs is strictly increasing.

Solution: Math

Check two consecutive rungs, if their diff is > dist, we need insert (diff – 1) / dist rungs in between.
ex1 5 -> 11, diff = 6, dist = 2, (diff – 1) / dist = (6 – 1) / 2 = 2. => 5, 7, 9, 11.
ex2 0 -> 3, diff = 3, dist = 1, (diff – 1) / dist = (3 – 1) / 1 = 2 => 0, 1, 2, 3

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

C++

// Author: Huahua

class Solution {

public:

int addRungs(vector<int>& rungs, int dist) {

int ans = 0;

for (size_t i = 0; i < rungs.size(); ++i)

ans += (rungs[i] - (i ? rungs[i - 1] : 0) - 1) / dist;

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def addRungs(self, rungs: List[int], dist: int) -> int:

return sum((r - 1 - (rungs[i - 1] if i else 0)) // dist for i, r in enumerate(rungs))

花花酱 LeetCode 1935. Maximum Number of Words You Can Type

By zxi on December 31, 2021

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: We cannot type "world" because the 'd' key is broken.

Example 2:

Input: text = "leet code", brokenLetters = "lt"
Output: 1
Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3:

Input: text = "leet code", brokenLetters = "e"
Output: 0
Explanation: We cannot type either word because the 'e' key is broken.

Constraints:

1 <= text.length <= 10⁴
0 <= brokenLetters.length <= 26
text consists of words separated by a single space without any leading or trailing spaces.
Each word only consists of lowercase English letters.
brokenLetters consists of distinct lowercase English letters.

Solution: Hashset / bitset

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

C++

// Author: Huahua

class Solution {

public:

int canBeTypedWords(string text, string brokenLetters) {

const int n = text.size();

bitset<26> b;

for (char c : brokenLetters) b.set(c - 'a');

int ans = 0;

for (int i = 0, broken = 0; i <= n; ++i) {

if (i == n || text[i] == ' ') {

if (!broken) ++ans;

broken = 0;

} else {

broken |= b[text[i] - 'a'];

}

return ans;

}

};

Huahua's Tech Road

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

Solution: Simulation

C++

花花酱 LeetCode 1942. The Number of the Smallest Unoccupied Chair

Solution: Treeset + Simulation

C++

花花酱 LeetCode 1941. Check if All Characters Have Equal Number of Occurrences

Solution: Hashtable

C++

Python3

花花酱 LeetCode 1936. Add Minimum Number of Rungs

Solution: Math

C++

Python3

花花酱 LeetCode 1935. Maximum Number of Words You Can Type

Solution: Hashset / bitset

C++