【剑指】4.4 分解复杂问题

遇到复杂问题可以尝试分步骤去解决，分为多个方法调用也能让逻辑看起来更清晰。

面试题35：复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。

解题思路

一个直接的思路可能是，首先按照next顺序走一遍链表并复制出一个值相同的链表，同时使用一个map建立起原节点对象到克隆节点对象的映射。第二次再用双指针同步遍历原链表和克隆链表，如果发现原链表中的节点A的random指针不为空，则通过map快速获得该random节点对象的克隆节点对象RC，并将A的克隆对象的random指针指向RC。这中方法需要使用O(n)的额外空间和O(2n)的时间。

import java.util.HashMap;
import java.util.Map;

public class CloneComplexList {
    public RandomListNode Clone1(RandomListNode pHead) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode originPointer = pHead, clonedPointer = dummy;
        while (originPointer != null) {
            clonedPointer.next = new RandomListNode(originPointer.label);
            clonedPointer = clonedPointer.next;
            map.put(originPointer,clonedPointer);
            originPointer = originPointer.next;
        }
        clonedPointer = dummy.next;
        originPointer = pHead;
        while (originPointer != null) {
            if (originPointer.random != null) {
                clonedPointer.random = map.get(originPointer.random);
            }
            originPointer = originPointer.next;
            clonedPointer = clonedPointer.next;
        }
        return dummy.next;
    }
}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

还有一种不需要map额外O(n)空间的思路，前面我们要设置某个克隆节点的random指针，是需要通过map快速得到其原节点random指针的克隆节点。现在我们可以直接把一个节点的克隆节点插入到其后面来在下一次设置random指针时快速得到它。分三步去完成：

1. 将每个节点的拷贝插入到链表中该节点后的位置
2. 遍历节点，为相邻的拷贝节点设置random指针
3. 从拷贝后的链表中分离出拷贝的节点。

public class CloneComplexList {
    public RandomListNode Clone(RandomListNode pHead) {
        linearDuplicate(pHead);
        setRandom(pHead);
        return detachCloned(pHead);
    }

    private void linearDuplicate(RandomListNode pHead) {
        if (pHead == null) return;
        RandomListNode nextTarget = pHead.next;
        RandomListNode clonedTarget = new RandomListNode(pHead.label);
        pHead.next = clonedTarget;
        clonedTarget.next = nextTarget;
        linearDuplicate(nextTarget);
    }

    private void setRandom(RandomListNode pHead) {
        if (pHead == null) return;
        RandomListNode cloned = pHead.next;
        //设置克隆节点的random指针时要注意可能的空指针问题
        cloned.random = pHead.random == null ? null : pHead.random.next;
        setRandom(cloned.next);
    }

    private RandomListNode detachCloned(RandomListNode pHead) {
        if (pHead == null) return null;
        RandomListNode clonedHead = pHead.next;
        RandomListNode odd = pHead;
        while (odd != null) {
            RandomListNode even = odd.next;
            odd.next = even.next;
            odd = even.next;
            even.next = odd == null ? null : odd.next;
        }
        return clonedHead;
    }
}

面试题36：二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解题思路

使用一个list保存BST的中序遍历结果以确保list中的节点是有序的，然后按照list中的顺序修改节点的指针即可。另外用递归也可以实现修改，递归时用一个全局变量保存中序遍历的上一个节点，在修改两个节点间的连接关系，不过递归其实也是需要O(n)的栈空间的。

public class ConvertBST2List {
    List<TreeNode> list = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        list = new ArrayList<>();
        inorderTraversal(pRootOfTree);
        TreeNode pre = null;
        for (int i = 0; i < list.size(); i++) {
            TreeNode curr = list.get(i);
            if (i == list.size() - 1) curr.right = null;
            curr.left = pre;
            if (pre != null) pre.right = curr;
            pre = curr;
        }
        return list.get(0);
    }

    private void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);
            list.add(root);
            inorderTraversal(root.right);
        }
    }
}

递归解法：

public class ConvertBST2List {
    TreeNode pre=null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree==null)
            return null;
        Convert(pRootOfTree.right);
        if (pre!= null){
            pRootOfTree.right=pre;
            pre.left=pRootOfTree;
        }
        pre=pRootOfTree;
        Convert(pRootOfTree.left);
        return pre;
    }
}

面试题37：序列化/反序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1!#!#!"，然后通过自己的函数来解析回这个二叉树。

解题思路

统一使用一种遍历方式例如前序遍历来序列化二叉树，访问到父亲节点时就把其val序列化到字符串中，遇到孩子是空节点时就序列化"#!"。同样地，反序列化时，遇到节点为空才返回，否则创建节点并递归设置左右孩子。

public class SerializeTree {
    String Serialize(TreeNode root) {
        if (root == null) return "#!";
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> stack = new LinkedList<>();
        while (true) {
            while (root != null) {
                sb.append(root.val).append("!");
                stack.push(root);
                root=root.left;
            }
            sb.append("#!");
            if (stack.size()==0) break;
            root = stack.pop();
            root = root.right;
        }
        return sb.toString();
    }

    String[] values = null;
    int index = 0;
    
    TreeNode Deserialize(String str) {
        values = str.split("!");
        return preOrder();
    }

    private TreeNode preOrder() {
        if (values[index].equals("#")) {
            index++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(values[index++]));
        node.left = preOrder();
        node.right = preOrder();
        return node;
    }
}

面试题38：字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

解题思路

排列、组合问题的解空间非常大，往往都可以用回溯法来解决。牛客网上这道题额外要求按照字典序，所以在开始前要对字符进行排序。另外可能有重复字符，所以在加入结果集之前要判断是否已经存在相同的字符串。

public class PermutationOfString {
    ArrayList<String> result = null;
    char[] s = null;
    boolean[] visited = null;

    public ArrayList<String> Permutation(String str) {
        result = new ArrayList<>();
        if (str==null||str.length()==0) return result;
        s = str.toCharArray();
        Arrays.sort(s);
        visited = new boolean[s.length];
        backtrack(new StringBuilder());
        return result;
    }

    private void backtrack(StringBuilder path) {
        if (path.length() == s.length) {
            String fullPath = path.toString();
            if (!result.contains(fullPath))
                result.add(fullPath);
            return;
        }
        for (int i = 0; i < s.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                path.append(s[i]);
                backtrack(path);
                path.deleteCharAt(path.length() - 1);
                visited[i] = false;
            }
        }
    }
}