Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 2222. Number of Ways to Select Buildings

By zxi on April 2, 2022

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

  • s[i] = '0' denotes that the ith building is an office and
  • s[i] = '1' denotes that the ith building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

  • For example, given s = "001101", we cannot select the 1st, 3rd, and 5th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings.

Example 1:

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.

Example 2:

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.

Constraints:

  • 3 <= s.length <= 105
  • s[i] is either '0' or '1'.

Solution: DP

The brute force solution will take O(n3) which will lead to TLE.

Since the only two valid cases are “010” and “101”.

We just need to count how many 0s and 1s, thus we can count 01s and 10s and finally 010s and 101s.

C++

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

  1. 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.
  2. 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.
  3. Replace the array nums with newNums.
  4. 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(n2)
Space complexity: O(n)

C++

花花酱 LeetCode 2220. Minimum Bit Flips to Convert Number

By zxi on April 2, 2022

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

  • For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:

Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -> 010.
- Flip the second bit from the right: 010 -> 000.
- Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

Constraints:

  • 0 <= start, goal <= 109

Solution: XOR

start ^ goal will give us the bitwise difference of start and goal in binary format.
ans = # of 1 ones in the xor-ed results.
For C++, we can use __builtin_popcount or bitset<32>::count() to get the number of bits set for a given integer.

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

C++

花花酱 LeetCode 2218. Maximum Value of K Coins From Piles

By zxi on March 28, 2022

There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.

In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.

Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

Example 1:

Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.

Example 2:

Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.

Constraints:

  • n == piles.length
  • 1 <= n <= 1000
  • 1 <= piles[i][j] <= 105
  • 1 <= k <= sum(piles[i].length) <= 2000

Solution: DP

let dp(i, k) be the maximum value of picking k elements using piles[i:n].

dp(i, k) = max(dp(i + 1, k), sum(piles[i][0~j]) + dp(i + 1, k – j – 1)), 0 <= j < len(piles[i])

Time complexity: O(n * m), m = sum(piles[i]) <= 2000
Space complexity: O(n * k)

Python

花花酱 LeetCode 2217. Find Palindrome With Fixed Length

By zxi on March 28, 2022

Given an integer array queries and a positive integer intLength, return an array answer where answer[i] is either the queries[i]th smallest positive palindrome of length intLength or -1 if no such palindrome exists.

A palindrome is a number that reads the same backwards and forwards. Palindromes cannot have leading zeros.

Example 1:

Input: queries = [1,2,3,4,5,90], intLength = 3
Output: [101,111,121,131,141,999]
Explanation:
The first few palindromes of length 3 are:
101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, ...
The 90th palindrome of length 3 is 999.

Example 2:

Input: queries = [2,4,6], intLength = 4
Output: [1111,1331,1551]
Explanation:
The first six palindromes of length 4 are:
1001, 1111, 1221, 1331, 1441, and 1551.

Constraints:

  • 1 <= queries.length <= 5 * 104
  • 1 <= queries[i] <= 109
  • 1 <= intLength <= 15

Solution: Math

For even length e.g. 4, we work with length / 2, e.g. 2. Numbers: 10, 11, 12, …, 99, starting from 10, ends with 99, which consist of 99 – 10 + 1 = 90 numbers. For the x-th number, e.g. 88, the left part is 10 + 88 – 1 = 97, just mirror it o get the palindrome. 97|79. Thus we can answer a query in O(k/2) time which is critical.


For odd length e.g. 3 we work with length / 2 + 1, e.g. 2, Numbers: 10, 11, 12, 99. Drop the last digit and mirror the left part to get the palindrome. 101, 111, 121, …, 999.

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

C++