Huahua’s Tech Road

花花酱 LeetCode 152. Maximum Product Subarray

By zxi on November 28, 2021

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10⁴
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution: Track high and low

Compute the low / high of prefix product, reset if nums[i] is higher than high or lower than low.

Swap low and high if nums[i] is a negative number.

e.g. [2, 3, -1, 8, -2]
nums[i] = 2, low = 2, high = 2
nums[i] = 3, low = 3, high = 2 * 3 = 6
nums[i] = -1, low = 6 * -1 = -6, high = -1
nums[i] = 8, low = -6 * 8 = -48, high = 8
nums[i] = -2, low = 8*-2 = -16, high = -48 * -2 = 96

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

C++

// Author: Huahua

class Solution {

public:

int maxProduct(vector<int>& nums) {

int ans = nums[0];

for (int i = 1, h = ans, l = ans; i < nums.size(); ++i) {

if (nums[i] < 0) swap(l, h);

l = min(nums[i], nums[i] * l);

h = max(nums[i], nums[i] * h);

ans = max(ans, h);

}

return ans;

}

};

花花酱 LeetCode 179. Largest Number

By zxi on November 28, 2021

Given a list of non-negative integers nums, arrange them such that they form the largest number.

Note: The result may be very large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]
Output: "210"

Example 2:

Input: nums = [3,30,34,5,9]
Output: "9534330"

Example 3:

Input: nums = [1]
Output: "1"

Example 4:

Input: nums = [10]
Output: "10"

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 10⁹

Solution: Greedy

Sort numbers by lexical order.
e.g. 9 > 666

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

C++

// Author: Huahua

class Solution {

public:

string largestNumber(vector<int> &num) {

vector<string> s;

for (int x : num)

s.emplace_back(to_string(x));

sort(begin(s), end(s), [](const auto& s1, const auto& s2) {

return s1 + s2 > s2 + s1;

});

if (s[0] == "0") return "0";

string ans;

for (int i = 0; i < s.size(); ++i)

ans += s[i];

return ans;

}

};

花花酱 LeetCode 173. Binary Search Tree Iterator

By zxi on November 28, 2021

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.

Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

Example 1:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output

[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // return 3 bSTIterator.next(); // return 7 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 9 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 15 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 20 bSTIterator.hasNext(); // return False

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
0 <= Node.val <= 10⁶
At most 10⁵ calls will be made to hasNext, and next.

Follow up:

Could you implement next() and hasNext() to run in average O(1) time and use O(h) memory, where h is the height of the tree?

Solution: In-order traversal using a stack

Use a stack to simulate in-order traversal.

Each next, we walk to the left most (smallest) node and push all the nodes along the path to the stack.

Then pop the top one t as return val, our next node to explore is the right child of t.

Time complexity: amortized O(1) for next() call.
Space complexity: O(n)

C++

// Author: Huahua

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

class BSTIterator {

public:

BSTIterator(TreeNode* root) : root_(root) {}

int next() {

while (root_) {

s_.push(root_);

root_ = root_->left;

}

TreeNode* t = s_.top(); s_.pop();

root_ = t->right;

return t->val;

}

bool hasNext() {

return (root_ || !s_.empty());

}

private:

TreeNode* root_;

stack<TreeNode*> s_;

};

/**

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

* BSTIterator* obj = new BSTIterator(root);

* int param_1 = obj->next();

* bool param_2 = obj->hasNext();

花花酱 LeetCode 187. Repeated DNA Sequences

By zxi on November 28, 2021

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]

Constraints:

1 <= s.length <= 10⁵
s[i] is either 'A', 'C', 'G', or 'T'.

Solution: Hashtable

Store each subsequence into the hashtable, add it into the answer array when it appears for the second time.

Time complexity: O(n*l)
Space complexity: O(n*l) -> O(n) / string_view

C++

// Author: Huahua

class Solution {

public:

vector<string> findRepeatedDnaSequences(string_view s) {

constexpr int kLen = 10;

const int n = s.length();

unordered_map<string_view, int> m;

vector<string> ans;

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

if (++m[s.substr(i, kLen)] == 2)

ans.emplace_back(s.substr(i, kLen));

return ans;

}

};

Optimization

There are 4 type of letters, each can be encoded into 2 bits. We can represent the 10-letter-long string using 20 lowest bit of a int32. We can use int as key for the hashtable.

A -> 00
C -> 01
G -> 10
T -> 11

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

C++

// Author: Huahua

class Solution {

public:

vector<string> findRepeatedDnaSequences(string s) {

constexpr int kLen = 10;

constexpr int mask = (1 << (2 * kLen)) -1;

const int n = s.length();

unordered_map<int, int> m;

array<int, 128> km;

km['A'] = 0;

km['C'] = 1;

km['G'] = 2;

km['T'] = 3;

vector<string> ans;

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

key = ((key << 2) & mask) | km[s[i]];

if (i < kLen - 1) continue;

if (++m[key] == 2)

ans.push_back(s.substr(i - kLen + 1, kLen));

}

return ans;

}

};

花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV

By zxi on November 28, 2021

You are given an integer array prices where prices[i] is the price of a given stock on the i^th day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000

Solution: DP

profit[i][j] := max profit by making up to j sells in first i days. (Do not hold any share)
balance[i][j] := max balance by making at to up j buys in first i days. (Most hold a share)

balance[i][j] = max(balance[i-1][j], profit[i-1][j-1] – prices[i]) // do nothing or buy at i-th day.
profit[i][j] = max(profit[i-1][j], balance[i-1][j] + prices[i]) // do nothing or sell at i-th day.

ans = profit[n-1][k]

Time complexity: O(n*k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int maxProfit(int k, vector<int>& prices) {

const int n = prices.size();

vector<int> balance(k + 1, INT_MIN);

vector<int> profit(k + 1, 0);

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

for (int j = 1; j <= k; ++j) {

balance[j] = max(balance[j], profit[j - 1] - prices[i]);

profit[j] = max(profit[j], balance[j] + prices[i]);

}

return profit[k];

}

};

Huahua's Tech Road

花花酱 LeetCode 152. Maximum Product Subarray

Solution: Track high and low

C++

花花酱 LeetCode 179. Largest Number

Solution: Greedy

C++

花花酱 LeetCode 173. Binary Search Tree Iterator

Solution: In-order traversal using a stack

C++

花花酱 LeetCode 187. Repeated DNA Sequences

Solution: Hashtable

C++

Optimization

C++

花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV

Solution: DP

C++

Related Problems