liancheng/ref.md

## ref.md

      
    Raw
  

              ref.md
            
          
Next Permutation
STL风格版本 https://gitcafe.com/liancheng/leetcode/blob/master/solutions/next-permutation/solution.hpp
利用reverse_iterator简化边界判断，可处理重复元素。参见：生成全排列、下一个排列、第k个排列的。


Unique Binary Search Trees
一维DP版本 https://gitcafe.com/liancheng/leetcode/blob/master/solutions/unique-binary-search-trees/dp.hpp
时间复杂度O(N^2)，空间复杂度O(N)


Recover Binary Search Tree
基本思想是中序遍历二叉树，寻找逆序数对。


简单版本 https://gitcafe.com/liancheng/leetcode/blob/master/solutions/recover-binary-search-tree/naive.hpp 空间复杂度O(N)


Morris Traversal版本 https://gitcafe.com/liancheng/leetcode/blob/master/solutions/recover-binary-search-tree/morris.hpp 空间复杂度O(1)
参见Binary Tree Inorder Traversal（题目、Morris Traversal参考实现）


Subsets
https://gitcafe.com/liancheng/leetcode/blob/master/solutions/subsets/solution.hpp
令集合大小为N，常见子集生成思路：

遍历长度为N的Gray Codes（相关LeetCode题目、Wikipedia条目）
遍历0至2^N - 1的所有整数

以上两个思路都是每个整数对应于一个子集，其中第i个bit代表原集合中第i个元素是否存在于目标子集。缺点在于N较大时需要用到大整数运算。给出的参考实现不存在这个缺点，思路类似于Gray Code遍历（将j由递增改为递减便成为Gray Code顺序）。