-
Pow(x, n)
指数计算应该是递归程序设计的入门级题目，但是在一场面试中写一个bug-free的代码还是需要多多注意边界条件。首先是底数的正负会影响结果，其次是指数的正负，也会影响结果。因为函数原型是pow(int x, int n),所以指数一定是整数。题目的一个简单思路是使用一个循环计算n遍x的乘积，但是这样的计算复杂度太高。如果我们想计算pow(x,16),我们需要做15次乘法，这样的开销很大。使用分治法换一个角度考虑，pow(x,16)其实可以分成两个pow(x,8)的乘积，同样的，pow(x,8)可以…
-
Valid Parentheses
括号题目是一类经典的算法题目，有很多变形。这类题目乍一看上去没有什么思路，但是实质上就是最近成对括号的匹配问题。常用的方法有记录括号数目和使用栈两种方式。 合法括号的判断问题是指在一串由()[]和{}组成的字符串中，判断括号是否合法。比如{()[]}是一个合法序列，但是(])就是非法的。该题目的解决可以使用栈来完成。当发现一个左括号([{时，将其压入栈中；当扫描到一个右括号时，判断栈顶元素（java中使用peek()函数）是否是与当前元素匹配的括号字符。如果不匹配，则整个字符串不合法；如果匹配…
-
Climbing Stairs
爬楼梯问题是一道典型的递归问题和动态规划问题的入门级题目。题目描述是：给定一个n个台阶楼梯，每次可以上一个或者两个台阶，请问最终可以有多少种方法爬到顶层。使用递归的思路解决是，到达第K个楼梯的方法数目是到达地k-1个楼梯的方法数与到达地k-2的楼梯的方法数的和。所以，如果函数原型是int cal(int n)，那么我们可以得到递归规则是cal(k)=cal(k-1)+cal(k-2）。边界条件是cal(1)=1,cal(2)=2。但是，这样计算会有很多的重复性计算，所以可以使用动态规划来解决。如…
-
Balanced Binary Tree
判定平衡二叉树的题目是一道基本的数据结构题目，在Leetcode的OJ上也有相关的测试用例。二叉树的结构请参见《Leetcode中使用的二叉树结构》。 可以使用一个递归函数，递归的判断每个节点的左子树和右子树的高度是否相差1，但是这样的算法会产生很多次重复的计算，效率并不高。另外一种方法是设计一个递归函数，返回以每个节点为根的二叉树的高度，当左右子树返回的高度相差超过1时，则返回-1表示该树不平衡。这样的算法时间复杂度为O(n)。该算法的Java实现如下。 public class Solu…
-
Leetcode中使用的二叉树结构
在leetcode中使用的二叉树,大多是"双指针"二叉树,即每个节点有指向其两个孩子的两个指针。同时，每个节点都有一个域存储该节点的int型值。每个节点写成一个类，该类每个域都是默认的public型的，可以从类外直接访问。该类提供一个构造函数，用于创建一个新的节点并将int型的value赋值。每个节点的java实现如下： public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(…