Huahua’s Tech Road

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

By zxi on November 28, 2021

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

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

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

Example 1:

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

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Example 4:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Solution: DP

A special case of 花花酱 LeetCode 188. Best Time to Buy and Sell Stock IV where k = 2.

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

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int>& prices) {

constexpr int k = 2;

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];

}

};

花花酱 LeetCode 143. Reorder List

By zxi on November 28, 2021

You are given the head of a singly linked-list. The list can be represented as:

L₀ → L₁ → … → L_{n - 1} → L_n

Reorder the list to be on the following form:

L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 2} → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10⁴].
1 <= Node.val <= 1000

Solution: Three steps

Step 1: Find mid node that splits the list into two halves.
Step 2: Reverse the second half
Step 3: Merge two lists

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

C++

// Author: Huahua

class Solution {

public:

void reorderList(ListNode* head) {

if (!head || !head->next) return;

ListNode* slow = head;

ListNode* fast = head;

while (fast->next && fast->next->next) {

slow = slow->next;

fast = fast->next->next;

}

ListNode* h1 = head;

ListNode* h2 = reverse(slow->next);

slow->next = nullptr;

while (h1 && h2) {

ListNode* n1 = h1->next;

ListNode* n2 = h2->next;

h1->next = h2;

h2->next = n1;

h1 = n1;

h2 = n2;

}

private:

// reverse a linked list

// returns head of the linked list

ListNode* reverse(ListNode* head) {

if (!head || !head->next) return head;

ListNode* prev = head;

ListNode* cur = head->next;

ListNode* next = cur;

while (cur) {

next = next->next;

cur->next = prev;

prev = cur;

cur = next;

}

head->next = nullptr;

return prev;

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 123. Best Time to Buy and Sell Stock III

Solution: DP

C++

花花酱 LeetCode 143. Reorder List

Solution: Three steps

C++

花花酱 LeetCode 147. Insertion Sort List

Solution: Scan from head

C++

花花酱 LeetCode 152. Maximum Product Subarray

Solution: Track high and low

C++

花花酱 LeetCode 179. Largest Number

Solution: Greedy

C++