syntax highlighter

2014年8月23日星期六

Leecode中图相关的题目

1. clone graph 图的深度拷贝。广度优先遍历图+hashtable,如果当前遇到的节点没有visit过,那么new一个新copy加入 并且把相应的邻居节点更新。如果visit过则略过new,直接将邻居节点更新

2013年12月16日星期一

Leetcode中平面几何相关的题目

1. Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
用斜率slope和y截距来定义一条直线是通常的做法,那么n个线段里两两配对,然后把slope和截距记录到hashtable里。这样的算法比较复杂。另一种简单的做法是依次选取一个点 P, 然后考察其他点和他的斜率,如果线段AP和BP的斜率一样,那么ABP三个点是共线的,这样就省去了截距的计算。 当然每一次iteration hashtable要清空,因为AP 和BQ的斜率即便一样,也未必是同一条线。最后要注意重复点的问题。

2013年10月10日星期四

常用排序算法

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(下层第一个非空孩子)

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

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。

2013年9月24日星期二

Leetcode 中stack在string处理中的应用

1. Valid Parentheses
这题思路较简单。用stack保存考察的char如果是右括号就对比和栈顶元素是否匹配,是则弹出否则插入。

2. Longest Valid Parentheses
这道题由于要求长度,因此压入栈的不是字符本身,而是index。遇到(直接压入,遇到)如果栈非空而且栈顶是(则update当前最大长度。 3. Simplify Path 预处理:去掉多余的"/"并在最后一位补上“/”。 设置状态位 flag==1 说明一层目录的开始,flag==2是一层目录的结尾。注意区别 "/."和“/..”. 前者直接舍弃,后者需要把栈顶元素弹出
4. Largest Rectangle in Histogram
最简单的方法就是依次遍历,取最大值 O(n^2)。比较巧妙的算法是用一个stack,存直方图的index,如果下一个直方图比栈顶直方图高,继续压栈,否则计算下一个直方图和当前直方图组成的面积。 5. Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. 此题第一步先纵向累计,i.e. 新建matrix (called mat), mat[i][j] 表示第j列上 以i结尾的最长连续1的个数。此步结束可以得到i组直方图然后用上题思路求解 6. Evaluate the value of an arithmetic expression in Reverse Polish Notation.
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
思路很简单, 读出来如果是操作数就压栈,如果是操作符,就把栈顶的两个元素拿出来计算,结果再次压栈