1.1、题目1
剑指 Offer 37. 序列化二叉树
1.2、解法
这题给我笑死了，我看到题解有个解法，我愿称之为神。
public class Codec {
private TreeNode root;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
this.root = root;
return null;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
return root;
}
}
真的是神仙般的人物。
这里serialize是通过BFS遍历实现的，存放到StringBuilder中最终转String返回。
deserialize也是BFS，只不过是反操作。
1.3、代码
public class Codec {
public String serialize(TreeNode root) {
if(root == null) return "[]";
StringBuilder res = new StringBuilder("[");
Queue queue = new LinkedList<>() {{ add(root); }};
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(node != null) {
res.append(node.val + ",");
queue.add(node.left);
queue.add(node.right);
}
else res.append("null,");
}
res.deleteCharAt(res.length() - 1);
res.append("]");
return res.toString();
}
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] vals = data.substring(1, data.length() - 1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
Queue queue = new LinkedList<>() {{ add(root); }};
int i = 1;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(!vals[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.left);
}
i++;
if(!vals[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(vals[i]));
queue.add(node.right);
}
i++;
}
return root;
}
}
2.1、题目2
剑指 Offer 38. 字符串的排列
2.2、解法
回溯的万能模板
def backtrack(...):
for 选择 in 选择列表:
做选择
backtrack(...)
撤销选择
这里也挺奇怪，居然不是返回list,就定了hashset最后再遍历进字符串数组返回，
注意这里是不重复，所以，创建要给visited数组来判断是否遍历过该字符。
2.3、代码
class Solution {
HashSet res = new HashSet();
boolean []visited;
public String[] permutation(String s) {
visited = new boolean[s.length()];
StringBuffer stringb = new StringBuffer();
back(s,stringb);
String []resarr = new String[res.size()];
int i=0;
for(String a:res){
resarr[i]=a;
i++;
}
return resarr;
}
public void back(String s,StringBuffer stringb){
if(stringb.length()==s.length()) {
res.add(stringb.toString());
return;
}
for(int i=0;i
Original: https://www.cnblogs.com/cxykhaos/p/15346348.html
Author: 程序员khaos
Title: 剑指offer计划28（搜索与回溯算法困难）—java
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/598454/
转载文章受原作者版权保护。转载请注明原作者出处！