Huahua’s Tech Road

花花酱 LeetCode 2099. Find Subsequence of Length K With the Largest Sum

By zxi on December 12, 2021

You are given an integer array nums and an integer k. You want to find a subsequence of nums of length k that has the largest sum.

Return any such subsequence as an integer array of length k.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [2,1,3,3], k = 2
Output: [3,3]
Explanation:
The subsequence has the largest sum of 3 + 3 = 6.

Example 2:

Input: nums = [-1,-2,3,4], k = 3
Output: [-1,3,4]
Explanation: 
The subsequence has the largest sum of -1 + 3 + 4 = 6.

Example 3:

Input: nums = [3,4,3,3], k = 2
Output: [3,4]
Explanation:
The subsequence has the largest sum of 3 + 4 = 7. 
Another possible subsequence is [4, 3].

Constraints:

1 <= nums.length <= 1000
-10⁵ <= nums[i] <= 10⁵
1 <= k <= nums.length

Solution 1: Full sorting + Hashtable

Make a copy of the original array, sort it in whole and put k largest elements in a hashtable.

Scan the original array and append the number to the answer array if it’s in the hashtable.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> maxSubsequence(vector<int>& nums, int k) {

vector<int> ans;

vector<int> s(nums);

sort(rbegin(s), rend(s));

unordered_map<int, int> m;

for (int i = 0; i < k; ++i) ++m[s[i]];

for (int x : nums)

if (--m[x] >= 0)

ans.push_back(x);

return ans;

}

};

Solution 2: k-th element

Use quick select / partial sort to find the k-th largest element of the array. Any number greater than that must be in the sequence. The tricky part is: what about the pivot itself? We couldn’t include ’em all blindly. Need to figure out how many copies of the pivot is there in the k largest and only include as many as of that in the final answer.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> maxSubsequence(vector<int>& nums, int k) {

vector<int> ans;

vector<int> s(nums);

nth_element(begin(s), begin(s) + k - 1, end(s), greater<int>());

const int pivot = s[k - 1];

// How many pivots in the largest k elements.

int left = count(begin(s), begin(s) + k, pivot);

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > pivot || (nums[i] == pivot && --left >= 0))

ans.push_back(nums[i]);

return ans;

}

};

花花酱 LeetCode Ultimate DP Study Plan Day 10

By zxi on December 11, 2021

413. Arithmetic Slices

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

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

@cache

def dp(i: int) -> int:

"""Number of arithmetic subarrays end with nums[i]."""

if i < 2: return 0

if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:

return 1 + dp(i - 1)

return 0

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

91. Decode Ways

Python3

# Author: Huahua

# Time complexity: O(n^2) -> O(n)

# Space complexity: O(n)

class Solution:

@cache

def numDecodings(self, s: str) -> int:

if not s: return 1

if s[0] == '0': return 0

ans = self.numDecodings(s[1:])

if len(s) > 1 and (s[0] == '1' or (s[0] == '2' and s[1] <= '6')):

ans += self.numDecodings(s[2:])

return ans

花花酱 LeetCode Ultimate DP Study Plan Day 9

By zxi on December 11, 2021

139. Word Break

Python3

# Author: Huahua

# Time complexity: O(n^2)

# Space complexity: O(n^2)

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:

words = set(wordDict)

n = len(s)

@cache

def dp(s: str) -> bool:

"""Returns whether s is breakable."""

if not s: return True

for l in range(1, min(n, 20) + 1):

if s[0:l] in words and dp(s[l:]): return True

return dp(s)

Optimization

Python3

# Author: Huahua

# Time complexity: O(n*l^2)

# Space complexity: O(n)

class Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:

words = set(wordDict)

n = len(s)

@cache

def dp(i: int) -> bool:

"""Returns whether s[i:] is breakable."""

if i >= n: return True

for l in range(1, min(n, 20) + 1):

if s[i:i+l] in words and dp(i + l): return True

return dp(0)

Adding Dark Mode to WordPress

By zxi on December 10, 2021

Supporting dark mode now becomes an industry standard, I also received several requests from my viewers/readers recently thus I decided to add this feature. First thing in my mind is a plugin, I found WP Dark Mode, it’s feature rich and kind of worked until someone told me it didn’t work with cached pages. Then I found Darkmode.js, there’re several plugin versions but I decided to use the plain js version. It’s simple but makes the job done. There are only a few options you can play with, like the position, size, color and emoji of the icon, that’s it. Here’s mine.

Put the following code in header.php

const options = {

bottom: '48px', // default: '32px'

right: '12px', // default: '32px'

left: 'unset', // default: 'unset'

time: '0.3s', // default: '0.3s'

mixColor: '#ddd', // default: '#fff' reduce contrast and lower the brightness.

backgroundColor: '#fff', // default: '#fff'

buttonColorDark: '#100f2c', // default: '#100f2c'

buttonColorLight: '#fff', // default: '#fff'

saveInCookies: true, // default: true,

label: '🌓', // default: ''

autoMatchOsTheme: true // default: true

}

function addDarkmodeWidget() {

new Darkmode(options).showWidget();

}

addDarkmodeWidget(); // No delays.

</script>

Basically, it adds an overlay layer that applies a revert color filter (white -> black, blue -> yellow, etc) to ALL the content including images and iframes as well as syntax-highlighted code which I decided to ignore later on.

To ignore a few types of content, add the following code to header.php

<style>

.darkmode-layer, .darkmode-toggle {

z-index: 500;

}

.darkmode--activated img {

filter: invert(1);

}

.darkmode--activated iframe {

filter: invert(1);

}

.darkmode--activated .crayon-syntax {

filter: invert(1);

}

</style>

The next thing is to apply a different color theme for code under darkmode. I plan to use classic for day-mode and sublime-text for darkmode. Although the author says the persistent darkmode setting is in cookies, but turns out it’s in localstorage. There are two scenarios we need to handle. 1) page loads with darkmode on, 2) user click button to toggle darkmode. We need to change the class for code blocks accordingly.

Put the following code in the footer.php, since we need to let the syntax-highlighter do the work first.

var darkMode = localStorage.getItem("darkmode") == "true";

if (darkMode) {

updateCrayonTheme(darkMode);

}

var button = document.getElementsByClassName("darkmode-toggle")[0];

button.addEventListener("click", () => {

darkMode = localStorage.getItem("darkmode") == "true";

updateCrayonTheme(darkMode);

});

function updateCrayonTheme(darkMode) {

var x = document.getElementsByClassName("crayon-syntax");

for (var i = 0; i < x.length; i++) {

x[i].classList.remove("crayon-theme-classic");

x[i].classList.remove("crayon-theme-sublime-text");

x[i].classList.add(darkMode ? "crayon-theme-sublime-text" : "crayon-theme-classic");

}

</script>

Or don’t forget to preload the darkmode theme since only the default theme will be loaded to reduce requests and bandwidth.

Put the following code in the header.php <head> section, replace with your domain and plugin version.

1	<link rel="stylesheet" id="crayon-theme-sublime-text-css" href="https://example.com/wp-content/plugins/crayon-syntax-highlighter-2.8.6/themes/sublime-text/sublime-text.css?ver=_2.7.2_beta" type="text/css" media="all">

Finally it looks like below, not perfect but pretty good and easy to config. I hope wordpress could officially add dark mode in the future release such that all the themes and plugins could implement that (more work though).

花花酱 LeetCode Ultimate DP Study Plan Day 8

By zxi on December 9, 2021

309. Best Time to Buy and Sell Stock with Cooldown

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxProfit(self, prices: List[int]) -> int:

@cache

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

"""

Returns

1) sold: Max profit w/o holdings. Can't buy. Can't sell.

2) holding: Max profit w/ holdings. Can't buy, Can sell.

3) cooldown: Max profit w/o holdings. Can buy. Can't sell."""

if i < 0: return -10**9, -10**9, 0

sold, holding, cooldown = dp(i - 1)

return (holding + prices[i], # sold

max(holding, cooldown - prices[i]), # do nothing, or buy.

max(cooldown, sold)) # cooldown

return max(dp(len(prices) - 1))

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxProfit(self, prices: List[int], fee: int) -> int:

@cache

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

"""

Returns:

1) sold: Max profit w/o holdings.

2) holding: Max profit w/ holdings."""

if i < 0: return 0, -10**9

sold, holding = dp(i - 1)

return (max(sold, holding + prices[i] - fee), # do nothing, sell

max(holding, sold - prices[i])) # do nothing, buy

return dp(len(prices) - 1)[0]

Huahua's Tech Road

Solution 1: Full sorting + Hashtable

C++

Solution 2: k-th element

C++

Python3

Python3

Python3

Optimization

Python3

309. Best Time to Buy and Sell Stock with Cooldown

Python3

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3