Huahua’s Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 9

By zxi on December 11, 2021

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)

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]

花花酱 LeetCode 231. Power of Two

By zxi on December 7, 2021

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2^x.

Example 1:

Input: n = 1
Output: true
Explanation: 2⁰ = 1

Example 2:

Input: n = 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: n = 3
Output: false

Example 4:

Input: n = 4
Output: true

Example 5:

Input: n = 5
Output: false

Constraints:

-2³¹ <= n <= 2³¹ - 1

Solution: 1 bit set

Any power of two has only 1 bit set in the binary format. e.g. 1=0b01, 2=0b10, 4=0b100, 8=0b1000

use popcount.

C++

// Author: Huahua

class Solution {

public:

bool isPowerOfTwo(int n) {

return n > 0 ? __builtin_popcount(n) == 1 : false;

}

};

2. Use (n) & (n – 1) to remove the last set bit, so it should be zero.

C++

// Author: Huahua

class Solution {

public:

bool isPowerOfTwo(int n) {

return n > 0 ? !(n & (n - 1)) : false;

}

};

花花酱 LeetCode 222. Count Complete Tree Nodes

By zxi on December 7, 2021

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2^h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

Constraints:

The number of nodes in the tree is in the range [0, 5 * 10⁴].
0 <= Node.val <= 5 * 10⁴
The tree is guaranteed to be complete.

Solution: Recursion

For each node, count the height of it’s left and right subtree by going left only.

Let L = height(left) R = height(root), if L == R, which means the left subtree is perfect.
It has (2^L – 1) nodes, +1 root, we only need to count nodes of right subtree recursively.
If L != R, L must be R + 1 since the tree is complete, which means the right subtree is perfect.
It has (2^(L-1) – 1) nodes, +1 root, we only need to count nodes of left subtree recursively.

Time complexity: T(n) = T(n/2) + O(logn) = O(logn*logn)

Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int countNodes(TreeNode* root) {

if (root == nullptr) return 0;

int l = depth(root->left);

int r = depth(root->right);

if (l == r)

return (1 << l) + countNodes(root->right);

else

return (1 << (l - 1)) + countNodes(root->left);

}

private:

int depth(TreeNode* root) {

if (root == nullptr) return 0;

return 1 + depth(root->left);

}

};

花花酱 LeetCode Ultimate DP Study Plan Day 9

139. Word Break

Python3

Optimization

Python3

Adding Dark Mode to WordPress

花花酱 LeetCode Ultimate DP Study Plan Day 8

309. Best Time to Buy and Sell Stock with Cooldown

Python3

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3

花花酱 LeetCode 231. Power of Two

Solution: 1 bit set

C++

C++

花花酱 LeetCode 222. Count Complete Tree Nodes

Solution: Recursion

C++

Huahua's Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 9

139. Word Break

Python3

Optimization

Python3

Adding Dark Mode to WordPress

花花酱 LeetCode Ultimate DP Study Plan Day 8

309. Best Time to Buy and Sell Stock with Cooldown

Python3

714 Best Time to Buy and Sell Stock with Transaction Fee

Python3

花花酱 LeetCode 231. Power of Two

Solution: 1 bit set

C++

C++

花花酱 LeetCode 222. Count Complete Tree Nodes

Solution: Recursion

C++