2013/06/15手写代码竞赛参考实现

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顺序）。

写的很好，既有讲解又有代码