Huahua’s Tech Road

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

By zxi on December 5, 2021

1014. Best Sightseeing Pair

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxScoreSightseeingPair(self, values: List[int]) -> int:

# score = (values[i] + i) + (values[j] - j)

@cache

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

"""Returns:

1) Max score of values[0..j]

2) Largest values[i] + i (i <= j)."""

if j < 0: return 0, 0

s, v = dp(j - 1)

return max(s, v + values[j] - j), max(v, values[j] + j)

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

121. Best Time to Buy and Sell Stock

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

"""Returns:

1) max profit of prices[0:i].

2) min price of prices[0:i]."""

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

max_profit, min_price = dp(i - 1)

return max(max_profit, prices[i] - min_price), min(min_price, prices[i])

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

122. Best Time to Buy and Sell Stock II

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

"""Returns:

1) Max profit after i-th day. Holding no stocks. Can buy.

2) Max balance after i-th day. Holding a stock. Can sell.

"""

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

profit, balance = dp(i - 1)

return (max(profit, balance + prices[i]), # do nothing, sell

max(balance, profit - prices[i])) # do nothing, buy

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

花花酱 LeetCode 219. Contains Duplicate II

By zxi on December 5, 2021

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

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

Solution: Sliding Window + Hashtable

Hashtable to store the last index of a number.

Remove the number if it’s k steps behind the current position.

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

C++

// Author: Huahua

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

unordered_map<int, int> m; // num -> last index

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

if (i > k && m[nums[i - k - 1]] < i - k + 1)

m.erase(nums[i - k - 1]);

if (m.count(nums[i])) return true;

m[nums[i]] = i;

}

return false;

}

};

花花酱 LeetCode 215. Kth Largest Element in an Array

By zxi on December 5, 2021

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Example 1:

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

Example 2:

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

Constraints:

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

Solution: Quick selection

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

C++

// Author: Huahua

class Solution {

public:

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

nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), std::greater<int>());

return nums[k - 1];

}

};

Huahua's Tech Road

花花酱 LeetCode 231. Power of Two

Solution: 1 bit set

C++

C++

花花酱 LeetCode 222. Count Complete Tree Nodes

Solution: Recursion

C++

花花酱 LeetCode Ultimate DP Study Plan Day 7

1014. Best Sightseeing Pair

Python3

121. Best Time to Buy and Sell Stock

Python3

122. Best Time to Buy and Sell Stock II

Python3

花花酱 LeetCode 219. Contains Duplicate II

C++

花花酱 LeetCode 215. Kth Largest Element in an Array

Solution: Quick selection

C++