Tuesday, January 27, 2015
Sunday, January 25, 2015
Saturday, January 24, 2015
Wednesday, January 21, 2015
Sunday, January 18, 2015
Saturday, January 17, 2015
Thursday, January 15, 2015
Sunday, January 11, 2015
[LeetCode]Sqrt
Labels:
binary search,
leetcode,
math
Location:
Irvine, CA, USA
Thursday, January 8, 2015
Wednesday, January 7, 2015
[Data Structure]Binary Search Tree
本文主要涉及BST的构造以及order operation方面的内容:
Labels:
binary search tree,
data structure
Location:
Irvine, CA, USA
[LintCode]Search Range In Binary Search Tree
首先是brute-force的方法, inorder看是不是在range里,在的话就加入。时间复杂度是O(N)。显然面试官不可能希望这个方法。
Labels:
binary search,
binary tree,
iterative,
LintCode,
recursion
Location:
Irvine, CA, USA
[LintCode]Remove Node in Binary Search Tree
删除的时候三种情况:
- 没有子节点
- 有一个子节点
- 有两个子节点
Labels:
binary tree,
LintCode,
recursion
Location:
Irvine, CA, USA
[LintCode]Insert Node in Binary Search Tree
很简单题,每个node决定是往左还是往右还是就是这个节点。类似二分的做法。
Labels:
binary search,
binary tree,
iterative,
LintCode,
recursion
Location:
Irvine, CA, USA
[LeetCode]String to Integer(atoi)
主要麻烦的地方在于注意各种corner case,按照题目要求来就好。主要讲一下,判断overflow, 之前我用的是很蠢的判断溢出的方法,以正数为例,之前是Integer.MAX_VALUE减去十次原来的数,在减去新的一位看是不是大于0。刷第三次的时候觉得这个方法太过于愚蠢了,稍微想了下,只需要Integer.MAX_VALUE减去新的那一位再除以10,看是不是大于原来的数就可以了。
Labels:
implementation,
leetcode,
string
Location:
Irvine, CA, USA
Monday, January 5, 2015
[LeetCode]Symmetric Tree
Top-down, 尾递归。
Labels:
binary tree,
leetcode,
recursion
Location:
Irvine, CA, USA
[LeetCode]Same Tree
Top-down, 尾递归。
Labels:
binary tree,
recursion
Location:
Irvine, CA, USA
[LeetCode]Validate Binary Search Tree
注意光判断左子结点小于当前节点右子结点大于当前节点是不够的。比如 5
/ \
3 8
\
6
就满足条件但不是valid BST。要判断也应该是左子树最大值小于当前节点,右子树最小值大于当前节点。不过这样太麻烦,用top-bottom的方法,开始的范围是(-∞,+∞)。每次经过一个结点从(low, high)分割成(low, curr.val)和(curr.val, high)像两个子节点递归。不满足就返回false,碰到null返回true。
/ \
3 8
\
6
就满足条件但不是valid BST。要判断也应该是左子树最大值小于当前节点,右子树最小值大于当前节点。不过这样太麻烦,用top-bottom的方法,开始的范围是(-∞,+∞)。每次经过一个结点从(low, high)分割成(low, curr.val)和(curr.val, high)像两个子节点递归。不满足就返回false,碰到null返回true。
Labels:
binary tree,
leetcode,
recursion
Location:
Irvine, CA, USA
[LeetCode]Binary Search Tree Iterator
BST中序遍历的迭代器,Inorder遍历iterative版本的好处就体现出来了,我们可以控制停在哪里,而recursive版本的就不好控制。这里我们要决定的是如何找到后继结点,分两种情况,一种是有右子树,那么我们找到右子树最小值即可。第二种是没有右子树,我们pop出栈顶的元素就是后继结点,至于为什么,我们在Binary Tree Preorder Traversal已经证明过这个问题。最后注意一下终止条件即可。
Labels:
binary tree,
leetcode,
stack
Location:
Irvine, CA, USA
[Algorithm]Binary Tree Morris Traversal
Binary Tree的Traversal问题总是面试的重点。不管是recursive还是iterative的版本,我们都需要额外的空间。
[LeetCode]Binary Tree Postorder Traversal
Labels:
binary tree,
leetcode,
stack
Location:
Irvine, CA, USA
[LeetCode]Binary Tree Inorder Traversal
在Binary Tree Preorder Traversal中说明过,Inorder的代码基本上是一样的,只有一行的区别。
Labels:
binary tree,
leetcode,
stack
Location:
Irvine, CA, USA
[LeetCode]Binary Tree Preorder Traversal
BST遍历的问题,很经典的问题。
Labels:
binary tree,
leetcode,
stack
Location:
Irvine, CA, USA
Subscribe to:
Posts (Atom)