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<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;
}
}
2.1、題目2
劍指 Offer 38. 字串的排列
2.2、解法
回溯的萬能模板
def backtrack(...):
for 選擇 in 選擇串列:
做選擇
backtrack(...)
撤銷選擇
這里也挺奇怪，居然不是回傳list,就定了hashset最后再遍歷進字串陣列回傳，
注意這里是不重復，所以，創建要給visited陣列來判斷是否遍歷過該字符，
2.3、代碼
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);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303687.html
標籤：Java