Huahua’s Tech Road

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

By zxi on December 4, 2021

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: 
All the possible integers that follow the requirements are in the output array. 
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: 
The same digit can be used as many times as it appears in digits. 
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: 
No even integers can be formed using the given digits.

Example 4:

Input: digits = [0,2,0,0]
Output: [200]
Explanation: 
The only valid integer that can be formed with three digits and no leading zeros is 200.

Example 5:

Input: digits = [0,0,0]
Output: []
Explanation: 
All the integers that can be formed have leading zeros. Thus, there are no valid integers.

Constraints:

3 <= digits.length <= 100
0 <= digits[i] <= 9

Solution: Enumerate all three digits even numbers

Check 100, 102, … 998. Use a hashtable to check whether all digits are covered by the given digits.

Time complexity: O(1000*lg(1000))
Space complexity: O(10)

C++

// Author: Huahua

class Solution {

public:

vector<int> findEvenNumbers(vector<int>& digits) {

vector<int> counts(10);

for (int d : digits) ++counts[d];

vector<int> ans;

for (int x = 100; x < 1000; x += 2) {

bool valid = true;

vector<int> c(10);

for (int t = x; t > 0; t /= 10)

valid &= (++c[t % 10] <= counts[t % 10]);

if (valid) ans.push_back(x);

}

return ans;

}

};

花花酱 LeetCode Ultimate DP Study Plan Day 6

By zxi on December 1, 2021

152. Maximum Product Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def maxProduct(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""min / max subarray product ends with nums[i]."""

if i == 0: return nums[i], nums[i]

low, hi = dp(i - 1)

if nums[i] < 0: low, hi = hi, low

return min(low * nums[i], nums[i]), max(hi * nums[i], nums[i])

return max(dp(i)[1] for i in range(len(nums)))

1567. Maximum Length of Subarray With Positive Product

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def getMaxLen(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""Max length of pos/neg product ends with nums[i]."""

if i < 0 or nums[i] == 0: return 0, 0

p, n = dp(i - 1)

if nums[i] > 0:

return p + 1, n + 1 if n else 0

else: # nums[i] < 0

return n + 1 if n else 0, p + 1

return max(dp(i)[0] for i in range(len(nums)))

花花酱 LeetCode Ultimate DP Study Plan Day 5

By zxi on December 1, 2021

53. Maximum Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxSubArray(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

"""Max subarray ends with nums[i]."""

if i < 0: return 0 # Empty array.

return nums[i] + max(0, dp(i - 1))

# Try all possible ending positions.

return max(dp(i) for i in range(len(nums)))

918. Maximum Sum Circular Subarray

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxSubarraySumCircular(self, nums: List[int]) -> int:

n = len(nums)

@cache

def dp(i: int, s: int) -> int:

"""Max subarray ends with s * nums[i]."""

if i < 0: return 0 # Empty array.

# Append to max subbary ends with nums[i-1] or start a new one.

return nums[i] * s + max(0, dp(i - 1, s))

max_p = max(dp(i, 1) for i in range(n))

max_n = max(dp(i, -1) for i in range(n))

return max_p if max_p < 0 else max(max_p, sum(nums) + max_n)

花花酱 LeetCode Ultimate DP Study Plan Day 4

By zxi on December 1, 2021

55 Jump Game

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n)

class Solution:

def canJump(self, nums: List[int]) -> bool:

n = len(nums)

@cache

def dp(i: int) -> bool:

"""Returns whether we can reach n - 1 from i."""

if i >= n - 1: return True

if i + nums[i] >= n - 1: return True

for s in range(1, nums[i] + 1):

if dp(i + s): return True

return False

return dp(0)

45 Jump Game II

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n)

class Solution:

def jump(self, nums: List[int]) -> int:

n = len(nums)

@cache

def dp(i: int) -> int:

"""Min steps to reach n - 1 from i."""

if i >= n - 1: return 0

if i + nums[i] >= n - 1: return 1

ans = n

for s in range(1, nums[i] + 1):

ans = min(ans, dp(i + s) + 1)

return ans

return dp(0)

花花酱 LeetCode Ultimate DP Study Plan Day 1 – 3

By zxi on November 30, 2021

Day 1

509. Fibonacci Number

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def fib(self, n: int) -> int:

return n if n <= 1 else self.fib(n - 1) + self.fib(n - 2)

1137. N-th Tribonacci Number

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def tribonacci(self, n: int) -> int:

if n == 0: return 0

if n <= 2: return 1

return sum(self.tribonacci(n - i - 1) for i in range(3))

Day 2

70. Climbing Stairs

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

@cache

def climbStairs(self, n: int) -> int:

if n <= 1: return 1

return self.climbStairs(n - 1) + self.climbStairs(n - 2)

746. Min Cost Climbing Stairs

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def minCostClimbingStairs(self, cost: List[int]) -> int:

@cache

def dp(i: int) -> int:

if i <= 1: return 0

return min(dp(i - 1) + cost[i - 1],

dp(i - 2) + cost[i - 2])

return dp(len(cost))

Day 3

198. House Robber

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def rob(self, nums: List[int]) -> int:

@cache

def dp(i: int) -> int:

if i < 0: return 0

return max(nums[i] + dp(i - 2), dp(i - 1))

return dp(len(nums) - 1)

213. House Robber II

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n) -> O(1)

class Solution:

def rob(self, nums: List[int]) -> int:

n = len(nums)

if n == 1: return nums[0]

@cache

def dp(i: int, j: int) -> int:

if j < i: return 0

return max(nums[j] + dp(i, j - 2), dp(i, j - 1))

return max(dp(0, n - 2), dp(1, n - 1))

740. Delete and Earn

This problem can be reduced to LC 198 House Robber

Python3

# Author: Huahua

# Time complexity: O(m + n)

# Space complexity: O(m + n)

class Solution:

def deleteAndEarn(self, nums: List[int]) -> int:

houses = [0] * (10**4 + 1)

for x in nums:

houses[x] += x

@cache

def dp(i : int) -> int:

if i < 0: return 0

return max(houses[i] + dp(i - 2), dp(i - 1))

return dp(len(houses) - 1)

Huahua's Tech Road

花花酱 LeetCode 2094. Finding 3-Digit Even Numbers

Solution: Enumerate all three digits even numbers

C++

花花酱 LeetCode Ultimate DP Study Plan Day 6

152. Maximum Product Subarray

Python3

1567. Maximum Length of Subarray With Positive Product

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 5

53. Maximum Subarray

Python3

918. Maximum Sum Circular Subarray

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 4

55 Jump Game

Python3

45 Jump Game II

Python3

花花酱 LeetCode Ultimate DP Study Plan Day 1 – 3

Day 1

Python3

Python3

Day 2

Python3

Python3

Day 3

Python3

Python3

Python3