花花酱 LeetCode 449. Serialize and Deserialize BST

By zxi on October 19, 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

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

Idea:

Binary format

serialized size: 4*n bytes, n is the number of nodes in the BST.

Time complexity: O(n)

Space complexity: O(n)

Solution:

C++

// Author: Huahua

// Runtime: 19 ~ 26 ms (<93.31%)

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, INT_MIN, INT_MAX);

}

private:

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

if (!root) return;

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

serialize(root->left, s);

serialize(root->right, s);

}

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

if (pos >= s.size()) return nullptr;

int val = *reinterpret_cast<const int*>(s.data() + pos);

if (val < curMin || val > curMax) return nullptr;

pos += sizeof(val);

TreeNode* root = new TreeNode(val);

root->left = deserialize(s, pos, curMin, val);

root->right = deserialize(s, pos, val, curMax);

return root;

}

};

Related Problems

[解题报告] LeetCode 297. Serialize and Deserialize Binary Tree

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

By zxi on October 17, 2017

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

/ \

2 3

Return 6.

Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

Solution: Recursion

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxPathSum(TreeNode* root) {

if (!root) return 0;

int ans = INT_MIN;

maxPathSum(root, ans);

return ans;

}

private:

int maxPathSum(TreeNode* root, int& ans) {

if (!root) return 0;

int l = max(0, maxPathSum(root->left, ans));

int r = max(0, maxPathSum(root->right, ans));

int sum = l + r + root->val;

ans = max(ans, sum);

return max(l, r) + root->val;

}

};

Python3

"""

Author: Huahua

Runtime: 138 ms (< 90.38%)

"""

class Solution(object):

def _maxPathSum(self, root):

if not root: return -sys.maxint

l = max(0, self._maxPathSum(root.left))

r = max(0, self._maxPathSum(root.right))

self.ans = max(self.ans, root.val + l + r)

return root.val + max(l, r)

def maxPathSum(self, root):

self.ans = -sys.maxint

self._maxPathSum(root)

return self.ans

Related Problems:

花花酱 LeetCode 37. Sudoku Solver

By zxi on October 16, 2017

Problem:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

Idea:

DFS + backtracking

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

void solveSudoku(vector<vector<char>>& board) {

rows_ = vector<vector<int>>(9, vector<int>(10));

cols_ = vector<vector<int>>(9, vector<int>(10));

boxes_ = vector<vector<int>>(9, vector<int>(10));

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

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

const char c = board[i][j];

if ( c != '.') {

int n = c - '0';

int bx = j / 3;

int by = i / 3;

rows_[i][n] = 1;

cols_[j][n] = 1;

boxes_[by * 3 + bx][n] = 1;

}

fill(board, 0, 0);

}

private:

vector<vector<int>> rows_, cols_, boxes_;

bool fill(vector<vector<char>>& board, int x, int y) {

if (y == 9)

return true;

int nx = (x + 1) % 9;

int ny = (nx == 0) ? y + 1 : y;

if (board[y][x] != '.') return fill(board, nx, ny);

for (int i = 1; i <= 9; i++) {

int bx = x / 3;

int by = y / 3;

int box_key = by * 3 + bx;

if (!rows_[y][i] && !cols_[x][i] && !boxes_[box_key][i]) {

rows_[y][i] = 1;

cols_[x][i] = 1;

boxes_[box_key][i] = 1;

board[y][x] = i + '0';

if (fill(board, nx, ny)) return true;

board[y][x] = '.';

boxes_[box_key][i] = 0;

cols_[x][i] = 0;

rows_[y][i] = 0;

}

return false;

}

};

Related Problems:

[解题报告] LeetCode 51. N-Queens

花花酱 LeetCode 40. Combination Sum II

By zxi on October 15, 2017

Problem:

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

Idea:

DFS

Solution:

C++ / set

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

set<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return vector<vector<int>>(ans.begin(), ans.end());

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

set<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.insert(curr);

return;

}

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

int num = candidates[i];

if (num > target) return;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

C++ / vector

// Author: Huahua

// Runtime: 9ms

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

vector<vector<int>> ans;

std::sort(candidates.begin(), candidates.end());

vector<int> curr;

dfs(candidates, target, 0, ans, curr);

return ans;

}

private:

void dfs(const vector<int>& candidates,

int target, int s,

vector<vector<int>>& ans,

vector<int>& curr) {

if (target == 0) {

ans.push_back(curr);

return;

}

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

int num = candidates[i];

if (num > target) return;

if (i > s && candidates[i] == candidates[i - 1]) continue;

curr.push_back(num);

dfs(candidates, target - num, i + 1, ans, curr);

curr.pop_back();

}

};

花花酱 LeetCode 72. Edit Distance

By zxi on October 15, 2017

Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Idea:

Dynamic Programming

Solution:

Recursive

// Author: Huahua

// Runtime: 13 ms

class Solution {

public:

int minDistance(string word1, string word2) {

int l1 = word1.length();

int l2 = word2.length();

d_ = vector<vector<int>>(l1 + 1, vector<int>(l2 + 1, -1));

return minDistance(word1, word2, l1, l2);

}

private:

vector<vector<int>> d_;

// minDistance from word1[0:l1-1] to word2[0:l2-1]

int minDistance(const string& word1, const string& word2, int l1, int l2) {

if (l1 == 0) return l2;

if (l2 == 0) return l1;

if (d_[l1][l2] >= 0) return d_[l1][l2];

int ans;

if (word1[l1 - 1] == word2[l2 - 1])

ans = minDistance(word1, word2, l1 - 1, l2 - 1);

else

ans = min(minDistance(word1, word2, l1 - 1, l2 - 1),

min(minDistance(word1, word2, l1 - 1, l2),

minDistance(word1, word2, l1, l2 - 1))) + 1;

return d_[l1][l2] = ans;

}

};

Iterative

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minDistance(string word1, string word2) {

int l1 = word1.length();

int l2 = word2.length();

// d[i][j] := minDistance(word1[0:i - 1], word2[0:j - 1]);

vector<vector<int>> d(l1 + 1, vector<int>(l2 + 1, 0));

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

d[i][0] = i;

for (int j = 0; j <= l2; ++j)

d[0][j] = j;

for (int i = 1; i <= l1; ++i)

for (int j = 1; j <= l2; ++j) {

int c = (word1[i - 1] == word2[j - 1]) ? 0 : 1;

d[i][j] = min(d[i - 1][j - 1] + c,

min(d[i][j - 1], d[i - 1][j]) + 1);

}

return d[l1][l2];

}

};

Huahua's Tech Road

花花酱 LeetCode 449. Serialize and Deserialize BST

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Solution: Recursion

C++

Python3

花花酱 LeetCode 37. Sudoku Solver

花花酱 LeetCode 40. Combination Sum II

花花酱 LeetCode 72. Edit Distance