1. 选择排序
每次遍历从集合中选择出最小或最大的放入集合的开头或结尾的位置，下次循环从剩余的元素集合中遍历找出最小的并如上操作，最后直至所有原集合元素都遍历完毕，排序结束。
2. 冒泡排序
依次比较相邻两个元素，优先级高（或大或小）的元素向后移动，直至到达序列末尾，无序区间就会相应地缩小。下一次再从无序区间进行冒泡操作，依此循环直至无序区间为1，排序结束。
3. 插入排序
将前面的区间（初始区间为1，包含第一个元素）视作有序区间，然后将有序区间的后一元素插入到前面有序区间的适当位置。直至有有序区间扩展到原区间的大小，排序结束。
4. 快速排序
思想就是任取待排序序列中的某个元素（元素的选取方式在一定程序上会影响实现过程和排序效率）作为标杆，将待排序序列划分为左右两个子序列，左侧元素小于标杆元素，右侧元素大于标杆元素，标杆元素则排在这两个子序列的中间，然后再对这两个子序列重复上述的方法，直至排序结束。
方法2
5. 归并排序
归并排序的原理比较简单，也是基于分治思想的。它将待排序的元素序列分成两个长度相等的子序列，然后为每一个子序列排序，然后再将它们合并成一个序列。
6. 堆排序
堆排序的过程分为两个步骤，第一步是根据初始输入数据，建立一个初始堆；第二步是将堆顶元素与当前无序区间的最后一个元素进行交换，然后再从堆顶元素开始对堆进行调整。
2013年10月2日星期三
LeetCode 中Tree的BFS
Tree 的BFS往往指的是层序遍历已经层序遍历的变型。最常见的做法是用两个queue，交替表示当前层和下一层。这种做法思路清晰简单，但是空间耗费是O（n）。 有些时候会要求更巧妙的空间耗费少的办法。
1. Binary Tree Level Order Traversal
也可以用递归的方法来做：
2. Binary Tree ZigZag Level Order Traversal
因为是zigzag顺序，因此用stack而不是queue，反序时先放left后放right，正序时先放right后放left。
3. Binary Tree Level Order Traversal II
题目由自顶向下改为了自底向上，只要把题1的结果reverse即可。这里代码略去
4. Populating Next Right Pointers in Each Node
此题是按层遍历的变种，用到双层 queue。注意此题的假设树是完全二叉树(perfect binary tree)
还有一种O（1）空间的解法，两个节点node负责换层(node=node->left), cross负责把左右子树连起来，以及右子树和corss->next的左子树连起来。
5. Populating Next Right Pointers in Each Node II
此题输入是任意的二叉树，因此并不是左右子树都存在，要分别考虑。代码很简单只需要改动两行
空间O（1）的解法，需要先把下一层链接好然后 用next来遍历下一层。 在开始遍历每一层前，next和pre都为0，这是位了发现正确的next（下层第一个非空孩子）和pre（下层第一个非空孩子）
1. Binary Tree Level Order Traversal
也可以用递归的方法来做：
2. Binary Tree ZigZag Level Order Traversal
因为是zigzag顺序，因此用stack而不是queue，反序时先放left后放right，正序时先放right后放left。
3. Binary Tree Level Order Traversal II
题目由自顶向下改为了自底向上，只要把题1的结果reverse即可。这里代码略去
4. Populating Next Right Pointers in Each Node
此题是按层遍历的变种，用到双层 queue。注意此题的假设树是完全二叉树(perfect binary tree)
还有一种O（1）空间的解法，两个节点node负责换层(node=node->left), cross负责把左右子树连起来，以及右子树和corss->next的左子树连起来。
5. Populating Next Right Pointers in Each Node II
此题输入是任意的二叉树，因此并不是左右子树都存在，要分别考虑。代码很简单只需要改动两行
空间O（1）的解法，需要先把下一层链接好然后 用next来遍历下一层。 在开始遍历每一层前，next和pre都为0，这是位了发现正确的next（下层第一个非空孩子）和pre（下层第一个非空孩子）
LeetCode 中 Tree的DFS
树是典型的可以用dfs算法的数据结构。 DFS往往都伴随着递归。但是与上一篇博客不同，这里的递归函数往往是help函数，难度也增加了，需要仔细分析
1. Path Sum I
检查是否有从root到leaf的path 使得他们的和等于sum，很典型的利用递归的DFS算法：
2. Path Sum II找到所有符合上题条件的路径
典型的DFS+回溯(pop_back)
3. Flatten Binary Tree to Linked List
思路是把每一个节点的left child置为空，right child挂在左子树最右子树（preorder right child的前驱）后面，right child放左子树（pre order 的next节点）。递归考虑右子树。
4. Binary Tree Maximum Path Sum
这题稍有难度。 三种情况需要考虑：1.左子树路径加当前根节点。2。右子树路径加当前根节点。 前两种情况都是以当前根节点为起始点。 3.如果path是穿过当前根节点的，那就需要左右子树路径加当前节点
5. Sum root to Leaf Numbers
思路是从root一直加下去，如果当前节点是叶子节点那么加到结果中去，否则最左右子数继续加。
6. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目， 如果数组为空，毫无疑问，只有一种BST，即空树， Count[0] =1
如果数组仅有一个元素{1}，只有一种BST，单个节点 Count[1] = 1
如果数组有两个元素{1,2}， 那么有如下两种可能
1 2
\ /
2 1
Count[2] = Count[0] * Count[1] (1为根的情况)
+ Count[1] * Count[0] (2为根的情况。
再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2] (1为根的情况)
+ Count[1]*Count[1] (2为根的情况)
+ Count[2]*Count[0] (3为根的情况)
所以，由此观察，可以得出Count的递推公式为Count[i] = ∑ Count[0...k] * [ k+1....i] 0<=k<i-1
问题至此划归为一维动态规划。当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。
7. Unique Binary Search Tree II
思路和上题类似，先定root然后把各种可能的左右子树分别组合。 8. Construct Binary Tree from Preorder and Inorder Traversal
9. Construct Binary Tree From PostOrder and InOrder TRaversal
定义Count[i] 为以[0,i]能产生的Unique Binary Tree的数目， 如果数组为空，毫无疑问，只有一种BST，即空树， Count[0] =1
如果数组仅有一个元素{1}，只有一种BST，单个节点 Count[1] = 1
如果数组有两个元素{1,2}， 那么有如下两种可能
1 2
\ /
2 1
Count[2] = Count[0] * Count[1] (1为根的情况)
+ Count[1] * Count[0] (2为根的情况。
再看一遍三个元素的数组，可以发现BST的取值方式如下：
Count[3] = Count[0]*Count[2] (1为根的情况)
+ Count[1]*Count[1] (2为根的情况)
+ Count[2]*Count[0] (3为根的情况)
所以，由此观察，可以得出Count的递推公式为Count[i] = ∑ Count[0...k] * [ k+1....i] 0<=k<i-1
问题至此划归为一维动态规划。当数组为 1，2，3，4，.. i，.. n时，基于以下原则的BST建树具有唯一性：以i为根节点的树，其左子树由[0, i-1]构成， 其右子树由[i+1, n]构成。
7. Unique Binary Search Tree II
思路和上题类似，先定root然后把各种可能的左右子树分别组合。 8. Construct Binary Tree from Preorder and Inorder Traversal
9. Construct Binary Tree From PostOrder and InOrder TRaversal
2013年10月1日星期二
LeetCode 中 Tree相关的Recursion
Tree是一个很重要的考点。其中recursion的题目占很大的比例。 在tree中， recursion往往和dfs相结合。 这里我们探讨一下那些用recursion解决的问题思路都很直观，代码比较容易写出来的题目。 注意相对应的iterative的题目也需要掌握。
1. Tree Pre-Order，InOrder,PostOrder遍历 这里首先给出中序遍历递归代码 iterative for InOrder Travesal iterative for InOrder Travesal with O(1) space (have parent ptr) Iterative for PreOrder Travesal
Iterative for PostOrder Travesal
2.Validate Binary Search Tree 递归检查左子树比root值小，又子树比root值大。 3. Recover Binary Search Tree 可以先用O（n）space 将树中序序列化，然后找出乱序的数字。这里要求O（1）的space 3.a 另一个利用iterative inorder的方法，不需要全局变量 以上方法都用到了extra space。下面的方法真正用到了O(1)space 4. Same Tree recursion 算法非常简单： 这里再给出iterative的方法 5. Symmetric Tree 思路和上一道题差不多。 Iterative: 6. Construct Binary Tree from Preorder and Inorder Tree 分段递归 7. Construct Binary Tree from Postorder and Inorder Tree 分段递归 8.Convert Sorted Array to Binary Search Tree 比较简单，每次取中间的数作为root，递归对左右两边的子数组进行操作。 9.Convert Sorted linkedList to Binary Search Tree 这题比上题复杂。 如果按照上题的思路每一层都需要遍历一次list 需要O（NlogN）。 如果采用从底向上的方法构建，可以充分利用list不能随机访问的性质，达到O（n） 10. Maximum Depth of Binary Tree 非常简单，递归调用 11. Minimum Depth of Binary Tree 思路和上题一样，但是不同的是，空！=零的关系，因此不能照搬上题的答案。 12， Balanced Search Tree 左右子数都是balance的而且两者maximum 高度差不超过1。
1. Tree Pre-Order，InOrder,PostOrder遍历 这里首先给出中序遍历递归代码 iterative for InOrder Travesal iterative for InOrder Travesal with O(1) space (have parent ptr) Iterative for PreOrder Travesal
Iterative for PostOrder Travesal
2.Validate Binary Search Tree 递归检查左子树比root值小，又子树比root值大。 3. Recover Binary Search Tree 可以先用O（n）space 将树中序序列化，然后找出乱序的数字。这里要求O（1）的space 3.a 另一个利用iterative inorder的方法，不需要全局变量 以上方法都用到了extra space。下面的方法真正用到了O(1)space 4. Same Tree recursion 算法非常简单： 这里再给出iterative的方法 5. Symmetric Tree 思路和上一道题差不多。 Iterative: 6. Construct Binary Tree from Preorder and Inorder Tree 分段递归 7. Construct Binary Tree from Postorder and Inorder Tree 分段递归 8.Convert Sorted Array to Binary Search Tree 比较简单，每次取中间的数作为root，递归对左右两边的子数组进行操作。 9.Convert Sorted linkedList to Binary Search Tree 这题比上题复杂。 如果按照上题的思路每一层都需要遍历一次list 需要O（NlogN）。 如果采用从底向上的方法构建，可以充分利用list不能随机访问的性质，达到O（n） 10. Maximum Depth of Binary Tree 非常简单，递归调用 11. Minimum Depth of Binary Tree 思路和上题一样，但是不同的是，空！=零的关系，因此不能照搬上题的答案。 12， Balanced Search Tree 左右子数都是balance的而且两者maximum 高度差不超过1。
订阅：
博文 (Atom)