剑指 Offer 37. 序列化二叉树
这题给我笑死了,我看到题解有个解法,我愿称之为神。
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,只不过是反操作。
public class Codec { public String serialize(TreeNode root) { if(root == null) return "[]"; StringBuilder res = new StringBuilder("["); Queue<TreeNode> 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<TreeNode> 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; } }
剑指 Offer 38. 字符串的排列
回溯的万能模板
def backtrack(...): for 选择 in 选择列表: 做选择 backtrack(...) 撤销选择
这里也挺奇怪,居然不是返回list,就定了hashset最后再遍历进字符串数组返回,
注意这里是不重复,所以,创建要给visited数组来判断是否遍历过该字符。
class Solution { HashSet<String> 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<s.length();i++){ if(visited[i]==true) continue; stringb.append(s.charAt(i)); visited[i]=true; back(s,stringb); visited[i]=false; stringb.deleteCharAt(stringb.length()-1); } } }