Huahua’s Tech Road

花花酱 LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets

By zxi on October 17, 2021

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]

Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 2³ - 1 = 7 total subsets.

Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

Constraints:

1 <= nums.length <= 16
1 <= nums[i] <= 10⁵

Solution: Brute Force

Try all possible subsets

Time complexity: O(n*2ⁿ)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countMaxOrSubsets(vector<int>& nums) {

const int n = nums.size();

int max_or = 0;

int count = 0;

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

int cur_or = 0;

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

if (s >> i & 1) cur_or |= nums[i];

if (cur_or > max_or) {

max_or = cur_or;

count = 1;

} else if (cur_or == max_or) {

++count;

}

return count;

}

};

花花酱 LeetCode 2043. Simple Bank System

By zxi on October 17, 2021

You have been tasked with writing a program for a popular bank that will automate all its incoming transactions (transfer, deposit, and withdraw). The bank has n accounts numbered from 1 to n. The initial balance of each account is stored in a 0-indexed integer array balance, with the (i + 1)^th account having an initial balance of balance[i].

Execute all the valid transactions. A transaction is valid if:

The given account number(s) are between 1 and n, and
The amount of money withdrawn or transferred from is less than or equal to the balance of the account.

Implement the Bank class:

Bank(long[] balance) Initializes the object with the 0-indexed integer array balance.
boolean transfer(int account1, int account2, long money) Transfers money dollars from the account numbered account1 to the account numbered account2. Return true if the transaction was successful, false otherwise.
boolean deposit(int account, long money) Deposit money dollars into the account numbered account. Return true if the transaction was successful, false otherwise.
boolean withdraw(int account, long money) Withdraw money dollars from the account numbered account. Return true if the transaction was successful, false otherwise.

Example 1:

Input
["Bank", "withdraw", "transfer", "deposit", "transfer", "withdraw"]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
Output

[null, true, true, true, false, false]

Explanation Bank bank = new Bank([10, 100, 20, 50, 30]); bank.withdraw(3, 10); // return true, account 3 has a balance of $20, so it is valid to withdraw $10. // Account 3 has $20 – $10 = $10. bank.transfer(5, 1, 20); // return true, account 5 has a balance of $30, so it is valid to transfer $20. // Account 5 has $30 – $20 = $10, and account 1 has $10 + $20 = $30. bank.deposit(5, 20); // return true, it is valid to deposit $20 to account 5. // Account 5 has $10 + $20 = $30. bank.transfer(3, 4, 15); // return false, the current balance of account 3 is $10, // so it is invalid to transfer $15 from it. bank.withdraw(10, 50); // return false, it is invalid because account 10 does not exist.

Constraints:

n == balance.length
1 <= n, account, account1, account2 <= 10⁵
0 <= balance[i], money <= 10¹²
At most 10⁴ calls will be made to each function transfer, deposit, withdraw.

Solution: Simulation

Time complexity: O(1) per operation
Space complexity: O(n) for n accounts

C++

class Bank {

public:

Bank(vector<long long>& balance)

: n_(balance.size()), balance_(balance) {}

bool transfer(int account1, int account2, long long money) {

if (account1 <= 0 || account1 > n_) return false;

if (account2 <= 0 || account2 > n_) return false;

if (balance_[account1 - 1] < money) return false;

balance_[account1 - 1] -= money;

balance_[account2 - 1] += money;

return true;

}

bool deposit(int account, long long money) {

if (account <= 0 || account > n_) return false;

balance_[account - 1] += money;

return true;

}

bool withdraw(int account, long long money) {

if (account <= 0 || account > n_ || balance_[account - 1] < money)

return false;

balance_[account - 1] -= money;

return true;

}

private:

const int n_;

vector<long long> balance_;

};

/**

* Your Bank object will be instantiated and called as such:

* Bank* obj = new Bank(balance);

* bool param_1 = obj->transfer(account1,account2,money);

* bool param_2 = obj->deposit(account,money);

* bool param_3 = obj->withdraw(account,money);

花花酱 LeetCode 2042. Check if Numbers Are Ascending in a Sentence

By zxi on October 17, 2021

A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.

For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.

Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).

Return true if so, or false otherwise.

Example 1:

Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

Example 2:

Input: s = "hello world 5 x 5"
Output: false
Explanation: The numbers in s are: 5, 5. They are not strictly increasing.

Example 3:

Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
Output: false
Explanation: The numbers in s are: 7, 51, 50, 60. They are not strictly increasing.

Example 4:

Input: s = "4 5 11 26"
Output: true
Explanation: The numbers in s are: 4, 5, 11, 26.
They are strictly increasing from left to right: 4 < 5 < 11 < 26.

Constraints:

3 <= s.length <= 200
s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.
The number of tokens in s is between 2 and 100, inclusive.
The tokens in s are separated by a single space.
There are at least two numbers in s.
Each number in s is a positive number less than 100, with no leading zeros.
s contains no leading or trailing spaces.

Solution: String

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

C++

// Author: Huahua

class Solution {

public:

bool areNumbersAscending(string s) {

stringstream ss(s);

string token;

int last = -1;

while (ss >> token) {

if (isdigit(token[0])) {

int num = stoi(token);

if (num <= last) return false;

last = num;

}

return true;

}

};

花花酱 LeetCode 2028. Find Missing Observations

By zxi on October 4, 2021

You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6. n of the observations went missing, and you only have the observations of m rolls. Fortunately, you have also calculated the average value of the n + m rolls.

You are given an integer array rolls of length m where rolls[i] is the value of the i^th observation. You are also given the two integers mean and n.

Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.

The average value of a set of k numbers is the sum of the numbers divided by k.

Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.

Example 1:

Input: rolls = [3,2,4,3], mean = 4, n = 2
Output: [6,6]
Explanation: The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Example 2:

Input: rolls = [1,5,6], mean = 3, n = 4
Output: [2,3,2,2]
Explanation: The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

Example 3:

Input: rolls = [1,2,3,4], mean = 6, n = 4
Output: []
Explanation: It is impossible for the mean to be 6 no matter what the 4 missing rolls are.

Example 4:

Input: rolls = [1], mean = 3, n = 1
Output: [5]
Explanation: The mean of all n + m rolls is (1 + 5) / 2 = 3.

Constraints:

m == rolls.length
1 <= n, m <= 10⁵
1 <= rolls[i], mean <= 6

Solution: Math & Greedy

Total sum = (m + n) * mean
Left = Total sum – sum(rolls) = (m + n) * mean – sum(rolls)
If left > 6 * n or left < 1 * n, then there is no solution.
Otherwise, we need to distribute Left into n rolls.
There are very ways to do that, one of them is even distribution, e.g. using the average number as much as possible, and use avg + 1 to fill the gap.
Compute the average and reminder: x = left / n, r = left % n.
there will be n – r of x and r of x + 1 in the output array.

e.g. [1, 5, 6], mean = 3, n = 4
Total sum = (3 + 4) * 3 = 21
Left = 21 – (1 + 5 + 6) = 9
x = 9 / 4 = 2, r = 9 % 4 = 1
Ans = [2, 2, 2, 2+1] = [2,2,2,3]

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

C++

class Solution {

public:

vector<int> missingRolls(vector<int>& rolls, int mean, int n) {

const int m = rolls.size();

int t = accumulate(begin(rolls), end(rolls), 0);

int left = mean * (m + n) - t;

if (left > 6 * n || left < n) return {};

vector<int> ans(n, left / n);

for (int i = 0; i < left % n; ++i) ++ans[i];

return ans;

}

};

花花酱 LeetCode 2027. Minimum Moves to Convert String

By zxi on October 4, 2021

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return the minimum number of moves required so that all the characters of s are converted to 'O'.

Example 1:

Input: s = "XXX"
Output: 1
Explanation: XXX -> OOO
We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"
Output: 2
Explanation: XXOX -> OOOX -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

Constraints:

3 <= s.length <= 1000
s[i] is either 'X' or 'O'.

Solution: Straight Forward

if s[i] == ‘X’, change s[i], s[i + 1] and s[i + 2] to ‘O’.

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

C++

class Solution {

public:

int minimumMoves(string s) {

const int n = s.length();

int ans = 0;

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

if (s[i] == 'X') {

ans += 1;

i += 2;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets

Solution: Brute Force

C++

花花酱 LeetCode 2043. Simple Bank System

Solution: Simulation

C++

花花酱 LeetCode 2042. Check if Numbers Are Ascending in a Sentence

C++

花花酱 LeetCode 2028. Find Missing Observations

Solution: Math & Greedy

C++

花花酱 LeetCode 2027. Minimum Moves to Convert String

Solution: Straight Forward

C++