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("[");
Queuequeue = 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]));
Queuequeue = 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 {
HashSetres = 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<s.length();i++){ if(visited[i]="=true)" continue;="" stringb.append(s.charat(i));="" visited[i]="true;" back(s,stringb);="" stringb.deletecharat(stringb.length()-1);="" }=""
文章来源:https://www.cnblogs.com/urmkhaos/p/15346348.html
|