三颗猫饼干算法 leetcode: recursions

Showing posts with label recursions. Show all posts

Sunday, July 21, 2013

Convert linked list to bst@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

下面两种方法，第一种更快。因为不用做循环什么的。

Saturday, July 20, 2013

Path Sum II @leetcode

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

» Solve this problem

这题要动态存储找到的path node，思路和permutation一样。还是要注意sol.pop_back()在完成了两个递归之后。

Construct height balanced BST from sorted array

微博：http://www.weibo.com/cathyhwzn

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

这题不是很全面，虽然我们就一直选取中间的点儿当root，然后递归两边就好了。但是实际上，balanced bst不止这一种建立方式。

Friday, July 19, 2013

Symmetric Tree@leetcode

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

But the following is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

这题递归法比较简单，几行代码的事情。但是我在oj的时候老是不通过，逻辑很简单，而且我确定是对的，后来自己跑到emacs上面调试，发现有segmentation fault，原来是我做判断的时候的一句话

if(l->val==r->val&&!l&&!r)

这种情况下，l or r 有可能是null，那么就没有l->val or r->val, 就会出现问题，这样把空判断提前就可以了，细节，但一定要注意！

这题难的是iterative的解法，基本做法是BFS，一层一层看是否对称，然后用两个queue来存储结点。

Thursday, July 18, 2013

Recover Binary Search Tree@leetcode

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

这道题思路很巧妙。刚开始我想穷举所有的情况，然后swap two nodes，后来发现这样做太不现实了。并且code很冗长。在网上看到说用in-order，刚开始没想到关in-order啥事儿。后来想到，因为是binary search tree,所以 in-order traverse得到的array应该是一个递增序列，这样我们就可以把这棵树看作一个array，然后只是其中两个点儿被swap了，找到这两个点，再swap回来就好，这样就不用考虑那些各种情况了。

用2个pointer，一个是pre，一个是current，若是current->val<pre->val, 那么纪录下cur, 遇到下一个再纪录下cur。以免遇到只有两个点儿的情况，要判断一下要不要纪录pre。

然后就是in-order traverse的变体。
还有一个分析得比较多的解法，可以看看 http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html

Unique Binary Tree II@leetcode

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

这道题我觉得很难，思路我有，就是左右子树递归填值，基本的idea 就是

node->val=i;

buildTree(node->left, l, i-1);

buildTree(node->right, i+1, r);

但问题是，我们要存的是一系列的子树，就是说一个n，它左右两边会有很多种类型的子树，它要全部都连接上，并且存到vector里面。这样逻辑就很难想明白（对于我这种recursion没有炉火纯青滴娃）。而且这里要用值传递，比较不浪费空间，不然都用指针，都在栈里面开辟空间，没调用一次都得开一堆东西，太麻烦。

我自己没想出来，参考了别人的答案。这个题可以让我们好好学习recursion。

后一个code用指针，因为涉及太多的vector数列，会需要用到很多拷贝构造，而且变量在栈上开辟。所以我们用指针来做。面试的时候注意。

Valid Binary Tree@leetcode

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

» Solve this problem

这个题思路比较简单，就是看左右子树是否符合BST的条件。但是，有一点需要注意的就是，左子树的所有结点都要比root小，右子树的所有结点都要比root大。这样就给了比较的时候一个range，范围，我们在递归的时候要把这个范围给传递进去。

Thursday, June 27, 2013

subsets@leetcode

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

» Solve this problem

如果有仔细看，会发现这题和上面那题长得很像，和permutations也很像。。。对了，它们就是很像。。。同一类型的题，稍微的变体，在recursion的判断条件上改改就好。