Search & Backtracking

2016-11-4 开始

2017-1-21 复习

Backtracking 都有三个步骤：

• Add element
• DFS
• Remove element

其中随着 dfs 传递参数的不同，三个步骤的位置会有变化。

其他的 DFS 是 element 已经加好了之后才开始的，而 Tree 是带着当前在考虑的 element 开始的。

Binary Tree Paths

先把Permutation和 Binary Tree Paths做一下体会不同。

其他的 DFS 是 element 已经加好了之后才开始的，而 Tree 是带着当前的节点在考虑的 element 开始的。

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if(root == null) {
            return result;
        }

        // 传入一个根节点，这是回溯的起点
        // 在中间结果是 String 的情况下，如果想保存一个 object 的 reference 可以用 StringBuilder, 
        // 同时也可以利用 immutable 的性质直接传新的 String copy (空间占用多一些)，这样可以免去删除的步骤。
        helper(root, root.val + "", result);
        return result;
    }

    private void helper(TreeNode root, String path, List<String> result) {
        if(root == null) {
            return;
        }
        // stop backtracking
        if(root.left == null && root.right == null) {
            result.add(path);
            return;
        }
        if(root.left != null) {
            helper(root.left, path + "->" + root.left.val, result);    
        }
        if(root.right != null) {
            helper(root.right, path + "->" + root.right.val, result);
        }
    }
}

Permutation Sequence

String 不在heap里面。

这道题目算法上没有什么特别的，更像是一道找规律的数学题目。

我们知道，n个数的permutation总共有n!个，基于这个性质我们可以得到某一位对应的数字是哪一个。

思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是 (n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。如此递推直到数组中没有元素结束。

实现中我们要 维护一个数组 来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。 时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。 这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。