Posts tagged as “binary”

花花酱 LeetCode 78. Subsets

By zxi on December 22, 2018

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++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

vector<vector<int>> ans;

vector<int> cur;

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

dfs(nums, i, 0, cur, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (n == cur.size()) {

ans.push_back(cur);

return;

}

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

cur.push_back(nums[i]);

dfs(nums, n, i + 1, cur, ans);

cur.pop_back();

}

};

Python3

# Author: Huahua, running time: 60 ms

class Solution:

def subsets(self, nums):

ans = []

def dfs(n, s, cur):

if n == len(cur):

ans.append(cur.copy())

return

for i in range(s, len(nums)):

cur.append(nums[i])

dfs(n, i + 1, cur)

cur.pop()

for i in range(len(nums) + 1):

dfs(i, 0, [])

return ans

Implementation 2: Binary

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<vector<int>> subsets(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> ans;

for (int s = 0; s < 1 << n; ++s) {

vector<int> cur;

for (int i = 0; i < n; ++i)

if (s & (1 << i)) cur.push_back(nums[i]);

ans.push_back(cur);

}

return ans;

}

};

Python3

# Author: Huahua, 40 ms

class Solution:

def subsets(self, nums):

n = len(nums)

return [[nums[i] for i in range(n) if s & 1 << i > 0] for s in range(1 << n)]

花花酱 LeetCode 869. Reordered Power of 2

By zxi on July 14, 2018

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:

1 2	<strong>Input: </strong><span id="example-input-5-1">46</span> <strong>Output: </strong><span id="example-output-5">true</span>

Note:

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++

// Author: Huahua

class Solution {

public:

bool reorderedPowerOf2(int N) {

auto m = countMap(N);

for (int i = 0; i < 31; ++i)

if (m == countMap(1 << i)) return true;

return false;

}

private:

map<int, int> countMap(int n) {

map<int, int> m;

while (n) {

++m[n % 10];

n /= 10;

}

return m;

}

};

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++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int binaryGap(int N) {

int l = -1;

int ans = 0;

for (int i = 0; i < 31; ++i)

if (N & (1 << i)) {

if (l >= 0)

ans = max(ans, i - l);

l = i;

}

return ans;

}

};

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

By zxi on September 17, 2017

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

/ \

2 3

/ \

4 5

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++

// Author: Huahua

// Running time: 39 ms

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

void serialize(TreeNode* root, ostringstream& out) {

if (!root) {

out << "# ";

return;

}

out << root->val << " ";

serialize(root->left, out);

serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

string val;

in >> val;

if (val == "#") return nullptr;

TreeNode* root = new TreeNode(stoi(val));

root->left = deserialize(in);

root->right = deserialize(in);

return root;

}

};

Solution 2: Binary

C++

// Author: Huahua

// Running time: 23 ms (beat 98.07%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

ostringstream out;

serialize(root, out);

return out.str();

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

istringstream in(data);

return deserialize(in);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, ostringstream& out) {

char status = 0;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

out.write(&status, sizeof(char));

if (!root) return;

out.write(reinterpret_cast<char*>(&(root->val)), sizeof(root->val));

if (root->left) serialize(root->left, out);

if (root->right) serialize(root->right, out);

}

TreeNode* deserialize(istringstream& in) {

char status;

in.read(&status, sizeof(char));

if (!status & ROOT) return nullptr;

auto root = new TreeNode(0);

in.read(reinterpret_cast<char*>(&root->val), sizeof(root->val));

root->left = (status & LEFT) ? deserialize(in) : nullptr;

root->right = (status & RIGHT) ? deserialize(in) : nullptr;

return root;

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

C++ (string)

// Author: Huahua

// Running time: 23 ms (<98.13%)

class Codec {

public:

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

string s;

serialize(root, s);

return s;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

int pos = 0;

return deserialize(data, pos);

}

private:

enum STATUS {

ROOT_NULL = 0x0,

ROOT = 0x1,

LEFT = 0x2,

RIGHT = 0x4

};

void serialize(TreeNode* root, string& s) {

char status = ROOT_NULL;

if (root) status |= ROOT;

if (root && root->left) status |= LEFT;

if (root && root->right) status |= RIGHT;

s.push_back(status);

if (!root) return;

s.append(reinterpret_cast<char*>(&root->val), sizeof(root->val));

if (root->left) serialize(root->left, s);

if (root->right) serialize(root->right, s);

}

TreeNode* deserialize(const string& s, int& pos) {

char status = s[pos++];

if (!status) return nullptr;

TreeNode* root = new TreeNode(0);

memcpy(&root->val, s.data() + pos, sizeof(root->val));

pos += sizeof(root->val);

root->left = (status & LEFT) ? deserialize(s, pos) : nullptr;

root->right = (status & RIGHT) ? deserialize(s, pos) : nullptr;

return root;

}

};

Posts tagged as “binary”

花花酱 LeetCode 78. Subsets

Solution: Combination

Implemention 1: DFS

C++

Python3

Implementation 2: Binary

C++

Python3

花花酱 LeetCode 869. Reordered Power of 2

Problem

Solution: HashTable

花花酱 LeetCode 868. Binary Gap

Problem

Solution: Bit

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems

花花酱 LeetCode 669. Trim a Binary Search Tree