Press "Enter" to skip to content

Posts tagged as “binary”

花花酱 LeetCode 1261. Find Elements in a Contaminated Binary Tree

Given a binary tree with the following rules:

  1. root.val == 0
  2. If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
  3. If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2

Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.

You need to first recover the binary tree and then implement the FindElements class:

  • FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first.
  • bool find(int target) Return if the target value exists in the recovered binary tree.

Example 1:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output

[null,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output

[null,true,true,false]

Explanation FindElements findElements = new FindElements([-1,-1,-1,-1,-1]); findElements.find(1); // return True findElements.find(3); // return True findElements.find(5); // return False

Example 3:

Input
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output

[null,true,false,false,true]

Explanation FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]); findElements.find(2); // return True findElements.find(3); // return False findElements.find(4); // return False findElements.find(5); // return True

Constraints:

  • TreeNode.val == -1
  • The height of the binary tree is less than or equal to 20
  • The total number of nodes is between [1, 10^4]
  • Total calls of find() is between [1, 10^4]
  • 0 <= target <= 10^6

Solutoin 1: Recursion and HashSet

Time complexity: Recover O(n), find O(1)
Space complexity: O(n)

C++

Solution 2: Recursion and Binary format

The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node.
t % 2 == 1, go right, otherwise go left
t = t / 2 or t >>= 1

Time complexity: Recover O(n), find O(log|target|)
Space complexity: O(1)

C++

花花酱 LeetCode 78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

Solution: Combination

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

Implemention 1: DFS

C++

Python3

Implementation 2: Binary

C++

Python3

花花酱 LeetCode 869. Reordered Power of 2

Problem

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

Input: 1
Output: true

Example 2:

Input: 10
Output: false

Example 3:

Input: 16
Output: true

Example 4:

Input: 24
Output: false

Example 5:

Note:

  1. 1 <= N <= 10^9

Solution: HashTable

Compare the counter of digit string with that of all power of 2s.

e.g. 64 -> {4: 1, 6: 1} == 46 {4:1, 6: 1}

Time complexity: O(1)

Space complexity: O(1)

C++

 

花花酱 LeetCode 868. Binary Gap

Problem

Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.

If there aren’t two consecutive 1’s, return 0.

Example 1:

Input: 22
Output: 2
Explanation: 
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.

Example 2:

Input: 5
Output: 2
Explanation: 
5 in binary is 0b101.

Example 3:

Input: 6
Output: 1
Explanation: 
6 in binary is 0b110.

Example 4:

Input: 8
Output: 0
Explanation: 
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.\

Note:

  • 1 <= N <= 10^9

Solution: Bit

Time complexity: O(logN)

Space complexity: O(1)

C++

 

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Idea:

Recursion

Time Complexity O(n)

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems