码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居西雅图。


Tag: Technical


  1. 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)可以…

    Technical, Career继续阅读

  2. Valid Parentheses

    括号题目是一类经典的算法题目,有很多变形。这类题目乍一看上去没有什么思路,但是实质上就是最近成对括号的匹配问题。常用的方法有记录括号数目和使用栈两种方式。 合法括号的判断问题是指在一串由()[]和{}组成的字符串中,判断括号是否合法。比如{()[]}是一个合法序列,但是(])就是非法的。该题目的解决可以使用栈来完成。当发现一个左括号([{时,将其压入栈中;当扫描到一个右括号时,判断栈顶元素(java中使用peek()函数)是否是与当前元素匹配的括号字符。如果不匹配,则整个字符串不合法;如果匹配,…

    Technical, Career继续阅读

  3. 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。但是,这样计算会有很多的重复性计算,所以可以使用动态规划来解决。如…

    Technical, Career继续阅读

  4. Balanced Binary Tree

    判定平衡二叉树的题目是一道基本的数据结构题目,在Leetcode的OJ上也有相关的测试用例。二叉树的结构请参见《Leetcode中使用的二叉树结构》。 可以使用一个递归函数,递归的判断每个节点的左子树和右子树的高度是否相差1,但是这样的算法会产生很多次重复的计算,效率并不高。另外一种方法是设计一个递归函数,返回以每个节点为根的二叉树的高度,当左右子树返回的高度相差超过1时,则返回-1表示该树不平衡。这样的算法时间复杂度为O(n)。该算法的Java实现如下。 public class Soluti…

    Technical, Career继续阅读

  5. Leetcode中使用的二叉树结构

    在leetcode中使用的二叉树,大多是"双指针"二叉树,即每个节点有指向其两个孩子的两个指针。同时,每个节点都有一个域存储该节点的int型值。每个节点写成一个类,该类每个域都是默认的public型的,可以从类外直接访问。该类提供一个构造函数,用于创建一个新的节点并将int型的value赋值。每个节点的java实现如下: public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(i…

    Technical, Career继续阅读