Punch day22

Question 1: Sword finger Offer 37. Serialized binary tree

Please implement two functions to serialize and deserialize the binary tree respectively.

You need to design an algorithm to realize the serialization and deserialization of binary tree. There is no restriction on the execution logic of your sequence / deserialization algorithm. You only need to ensure that a binary tree can be serialized into a string and deserialize the string into the original tree structure.

Note: the input / output format is the same as that currently used by LeetCode. For details, please refer to the format of LeetCode serialized binary tree. You don't have to take this approach, you can also take other methods to solve the problem.

Example:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Source: LeetCode
Link: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof

Problem solving ideas:

Serialization is implemented using sequence traversal. Deserialization is realized by deducing the index of each node in the sequence through the above recursive formula.

The serialization and deserialization required by the topic are reversible operations. Therefore, the serialized string should carry the complete binary tree information.

java code:

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;
    }
}

Question 2: Sword finger Offer 38. Arrangement of strings

Enter a string and print out all the arrangements of characters in the string.
You can return this string array in any order, but there can be no duplicate elements.

Example:
Enter: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

Limitations:
Length of 1 < = s < = 8

Source: LeetCode
Link: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

Problem solving ideas:
According to the characteristics of string arrangement, depth first search is considered to search all arrangement schemes

When there are duplicate characters in the string, there are also duplicate arrangement schemes in the arrangement scheme. In order to eliminate the duplicate scheme, when fixing a character, ensure that "each character is fixed only once in this bit", that is, when encountering duplicate characters, they will not be exchanged and will be skipped directly. From a DFS perspective, this operation is called pruning.

java code:

class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // Add arrangement scheme
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // Repeat, so prune
            set.add(c[i]);
            swap(i, x);                      // Swap, fix c[i] in bit x
            dfs(x + 1);                      // Turn on fixed x + 1 st character
            swap(i, x);                      // Recovery exchange
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}