Huahua’s Tech Road

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

}

};

花花酱 LeetCode 199. Binary Tree Right Side View

By zxi on November 28, 2021

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

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

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Solution: Pre-order traversal

By using pre-order traversal, the right most node will be the last one to visit in each level.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> rightSideView(TreeNode* root) {

vector<int> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {

if (!root) return;

if (ans.size() < d + 1) ans.push_back(0);

ans[d] = root->val;

dfs(root->left, d + 1);

dfs(root->right, d + 1);

};

dfs(root, 0);

return ans;

}

};

花花酱 LeetCode 191. Number of 1 Bits

By zxi on November 28, 2021

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?

Solution: Bit Operation

Use n & 1 to get the lowest bit of n.
Use n >>= 1 to right shift n for 1 bit, e.g. removing the last bit.

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

C++

// Author: Huahua

class Solution {

public:

int hammingWeight(uint32_t n) {

int ans = 0;

while (n) {

ans += n & 1;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 171. Excel Sheet Column Number

By zxi on November 28, 2021

Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnTitle = "A"
Output: 1

Example 2:

Input: columnTitle = "AB"
Output: 28

Example 3:

Input: columnTitle = "ZY"
Output: 701

Example 4:

Input: columnTitle = "FXSHRXW"
Output: 2147483647

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Solution: Base conversion

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

C++

// Author: Huahua

class Solution {

public:

int titleToNumber(string s) {

int ans = 0;

for (int i = s.length() - 1, cur = 0; i >= 0; --i) {

cur = cur ? cur * 26 : 1;

ans += (s[i] - 'A' + 1) * cur;

}

return ans;

}

};

花花酱 LeetCode 168. Excel Sheet Column Title

By zxi on November 28, 2021

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Example 4:

Input: columnNumber = 2147483647
Output: "FXSHRXW"

Constraints:

1 <= columnNumber <= 2³¹ - 1

Solution: Base conversion

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

string convertToTitle(int n) {

string ans;

do {

n--;

ans += 'A' + (char)(n % 26);

n /= 26;

} while (n);

reverse(begin(ans), end(ans));

return ans;

}

};

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

Solution: DP

C++

Related Problems

花花酱 LeetCode 199. Binary Tree Right Side View

Solution: Pre-order traversal

C++

花花酱 LeetCode 191. Number of 1 Bits

Solution: Bit Operation

C++

花花酱 LeetCode 171. Excel Sheet Column Number

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems

Huahua's Tech Road

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

Solution: DP

C++

Related Problems

花花酱 LeetCode 199. Binary Tree Right Side View

Solution: Pre-order traversal

C++

花花酱 LeetCode 191. Number of 1 Bits

Solution: Bit Operation

C++

花花酱 LeetCode 171. Excel Sheet Column Number

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems