Serialize and Deserialize Binary Tree
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
1
/ \
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.
----------------------------------------------------------
遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
queue<TreeNode *> que;
que.push(root);
string s = "";
while (!que.empty()) {
TreeNode *t = que.front();
que.pop();
if (t == NULL) {
s += "n";
}else {
s += to_string(t->val) + ",";
que.push(t->left);
que.push(t->right);
}
}
return s;
}
int next(string data, int &i) {
int rt = 0, sign = 1;
if (data[i] == '-') {
sign = -1;
i++;
}
while (isdigit(data[i])) {
rt = rt * 10 + data[i] - '0';
i++;
}
i++;
return rt * sign;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data == "n") return NULL;
queue<TreeNode *> que;
int i = 0;
TreeNode *root = new TreeNode(next(data,i));
que.push(root);
while (!que.empty()) {
TreeNode* t = que.front();
que.pop();
if (isdigit(data[i]) || data[i] == '-') {
t->left = new TreeNode(next(data,i));
que.push(t->left);
}else {
i++;
}
if (isdigit(data[i]) || data[i] == '-') {
t->right = new TreeNode(next(data,i));
que.push(t->right);
}else {
i++;
}
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (!que.isEmpty()) {
TreeNode top = que.poll();
if (top == null) {
sb.append("n").append(",");
} else {
sb.append(top.val).append(",");
que.add(top.left);
que.add(top.right);
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
List<String> l = Arrays.asList(data.split(","));
Queue<TreeNode> que = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(l.get(0)));
que.add(root);
for (int i = 1; i < l.size(); i += 2) {
TreeNode node = que.poll();
if (l.get(i).equals("n")) {
node.left = null;
} else {
TreeNode left = new TreeNode(Integer.parseInt(l.get(i)));
node.left = left;
que.add(left);
}
if (l.get(i + 1).equals("n")) {
node.right = null;
} else {
TreeNode right = new TreeNode(Integer.parseInt(l.get(i + 1)));
node.right = right;
que.add(right);
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL) {
return "n";
}
string rt = to_string(root->val) + ",";
rt += serialize(root->left) + serialize(root->right);
return rt;
}
TreeNode *helper(string &s, int &i) {
if (i == s.length()) return NULL;
if (s[i] == 'n') {
i++;
return NULL;
}
int sign = 1;
if (s[i] == '-') {
sign = -1;
i++;
}
int rt = 0;
while (isdigit(s[i])) {
rt = rt * 10 + s[i] - '0';
i++;
}
i++;
TreeNode *root = new TreeNode(rt * sign);
root->left = helper(s,i);
root->right = helper(s,i);
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int i = 0;
return helper(data,i);
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
}
private void buildString(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("n").append(",");
return;
}
sb.append(root.val).append(",");
buildString(root.left, sb);
buildString(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
List<String> s = Arrays.asList(data.split(","));
return toNode(s);
}
private int index = 0;
private TreeNode toNode(List<String> s) {
if (s.get(index).equals("n")) {
index++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(s.get(index)));
index++;
node.left = toNode(s);
node.right = toNode(s);
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Bulls and Cows
You are playing the following
Bulls and Cows game with your friend: You write a 4-digit secret number and ask your friend to guess it. Each time your friend guesses a number, you give a hint. The hint tells your friend how many digits are in the correct positions (called "bulls") and how many digits are in the wrong positions (called "cows"). Your friend will use those hints to find out the secret number.
For example:
Secret number: "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".
Please note that both secret number and friend's guess may contain duplicate digits, for example:
Secret number: "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.
--------------------------------------------------------
class Solution {
public:
string getHint(string secret, string guess) {
vector<int> upper(256,0);
vector<int> lower(256,0);
int bull = 0, cow = 0;
for (int i = 0; i < guess.length(); i++) {
if (secret[i] == guess[i]) {
bull++;
}else {
if (upper[guess[i]] > 0) {
cow++;
upper[guess[i]]--;
}else {
lower[guess[i]]++;
}
if (lower[secret[i]] > 0) {
cow++;
lower[secret[i]]--;
}else {
upper[secret[i]]++;
}
}
}
return to_string(bull) + "A" + to_string(cow) + "B";
}
};
Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
--------------------------------------------------------------
Solution #1, dp[i] 里存的是以i为后一位的，[0, i]之间的最长递增subsequence
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,1);
int len = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
len = max(len, dp[i]);
}
return len;
}
};
Solution #2, N(lg N)
ref:
http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
原理：
假设我们有[100, 101, 102, 1, ......], 当处理到[3]的时候，我们不能把前3位的信息抛弃，只有当以1开头的subsequence长度>= 3时，才能将之前的3位丢掉。这时一个方法是把所有的subsequence信息都记录下来，然后每次对比长度。另一个方法就是下面这个，进行元素替换。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> arr(1,nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < arr[0]) {
arr[0] = nums[i];
}else if (nums[i] > arr.back()) {
arr.push_back(nums[i]);
}else {
int low = 0, high = arr.size() - 1;
while (low <= high) {
int mid= (low + high) / 2;
if (mid > 0 && arr[mid - 1] <= nums[i] && arr[mid] > nums[i]) {
arr[mid] = nums[i];
break;
}
if (arr[mid] < nums[i]) {
low = mid + 1;
}else {
high = mid - 1;
}
}
}
}
return arr.size();
}
};
Remove Invalid Parentheses
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
--------------------------------------------------
都是brute force，以下为bfs
class Solution {
public:
bool isValid(string s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') count++;
if (s[i] == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
vector<string> removeInvalidParentheses(string s) {
queue<string> que;
unordered_set<string> dic;
que.push(s);
dic.insert(s);
vector<string> rt;
bool found = false;
while (!que.empty()) {
string str = que.front();
que.pop();
if (isValid(str)) {
rt.push_back(str);
found = true;
}
if (found) continue;
for (int i = 0; i < str.length(); i++) {
if (str[i] != '(' && str[i] != ')') continue;
string newStr = str.substr(0,i) + str.substr(i + 1);
if (dic.find(newStr) == dic.end()) {
que.push(newStr);
dic.insert(newStr);
}
}
}
return rt;
}
};
dfs,
ref:
http://blog.csdn.net/foreverling/article/details/49740665
remove the minimum number等于是建立一个最长的有效括号字符串
class Solution {
public:
void dfs(vector<string> &rt, string s, string curS, int left, int totalLeft, int &maxLen, unordered_set<string> &dic) {
if (s.length() == 0) {
if (left == 0 && totalLeft > maxLen) {
maxLen = totalLeft;
}
if (left == 0 && maxLen == totalLeft && dic.find(curS) == dic.end()) {
rt.push_back(curS);
dic.insert(curS);
}
return;
}
if (s[0] == '(') {
dfs(rt,s.substr(1), curS + '(', left + 1, totalLeft + 1, maxLen,dic);
dfs(rt,s.substr(1), curS, left, totalLeft, maxLen,dic);
}else if (s[0] == ')') {
if (left > 0) {
dfs(rt,s.substr(1), curS + ')', left - 1, totalLeft, maxLen,dic);
}
dfs(rt, s.substr(1), curS, left, totalLeft, maxLen,dic);
}else {
dfs(rt, s.substr(1), curS + s[0], left, totalLeft, maxLen,dic);
}
}
vector<string> removeInvalidParentheses(string s) {
vector<string> rt;
unordered_set<string> dic;
int maxLen = 0;
dfs(rt,s,"",0,0,maxLen,dic);
return rt;
}
};
Solution #3, in Java
- 先预处理，计算出为了得到合法的String，最少需要移除多少个左、右括号
- 依次移除右、左括号，并递减计数。
- 先移除右括号是为了剪枝，如')(()',虽然不影响最后结果
- 加isValid是为了解决'()()()(' -> '()())('
- ref: http://zxi.mytechroad.com/blog/searching/leetcode-301-remove-invalid-parentheses/
class Solution {
public List<String> removeInvalidParentheses(String s) {
int left = 0, right = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
}else if (s.charAt(i) == ')') {
if (left == 0) {
right++;
} else {
left--;
}
}
}
List<String> rt = new ArrayList<>();
dfs(new StringBuilder(s),0,left,right,rt);
return rt;
}
public void dfs(StringBuilder s, int index, int left, int right, List<String> rt) {
if (right == 0 && left == 0 && isValid(s)) {
rt.add(s.toString());
return;
}
for (int i = index; i < s.length(); i++) {
if (i != index && s.charAt(i) == s.charAt(i - 1)) continue;
if (right > 0 && s.charAt(i) == ')') {
StringBuilder s1 = new StringBuilder(s);
s1.deleteCharAt(i);
dfs(s1, i, left, right - 1, rt);
} else if (right == 0 && left > 0 && s.charAt(i) == '(') {
StringBuilder s1 = new StringBuilder(s);
s1.deleteCharAt(i);
dfs(s1, i, left - 1, right, rt);
}
}
}
public boolean isValid(StringBuilder s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
count++;
}
if (c == ')') {
count--;
}
if (count < 0) {
return false;
}
}
return count == 0;
}
}
