Problem

In the following, every capital letter represents some hexadecimal digit from 0 to f.

The red-green-blue color "#AABBCC" can be written as "#ABC" in shorthand. For example, "#15c" is shorthand for the color "#1155cc".

Now, say the similarity between two colors "#ABCDEF" and "#UVWXYZ" is -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2.

Given the color "#ABCDEF", return a 7 character color that is most similar to #ABCDEF, and has a shorthand (that is, it can be represented as some "#XYZ"

Example 1:
Input: color = "#09f166"
Output: "#11ee66"
Explanation:  
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.

Note:

color is a string of length 7.
color is a valid RGB color: for i > 0, color[i] is a hexadecimal digit from 0 to f
Any answer which has the same (highest) similarity as the best answer will be accepted.
All inputs and outputs should use lowercase letters, and the output is 7 characters.

Solution: Brute Force

R, G, B are independent, find the closest color for each channel separately.

Time complexity: O(3 * 16)

Space complexity: O(1)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

string similarRGB(string color) {

const string hex{"0123456789abcdef"};

vector<int> rgb(3, 0);

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

rgb[i] = hex.find(color[2 * i + 1]) * 16 + hex.find(color[2 * i + 2]);

string ans(7, '#');

for (int i = 0; i < 3; ++i) {

int best = INT_MAX;

for (int j = 0; j < 16; ++j) {

int diff = abs(j * 16 + j - rgb[i]);

if (diff >= best) continue;

best = diff;

ans[2 * i + 1] = ans[2 * i + 2] = hex[j];

}

return ans;

}

};

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 “conversion”

花花酱 LeetCode 504. Base 7

Problem

Solution: Simulation

花花酱 LeetCode 800. Simple RGB Color

Problem

Note:

Solution: Brute Force

花花酱 LeetCode 297. Serialize and Deserialize Binary Tree

Solution 1: ASCII

C++

Solution 2: Binary

C++

C++ (string)

Related Problems