LintCode/LeetCode训练题目&答案详解—基

一、在二叉树中寻找值最大的节点并返回：
给出如下一棵二叉树：

     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5 

返回值为 3 的节点。

public class Solution {
    /**
 * @param root the root of binary tree
 * @return the max node
 */
public TreeNode maxNode(TreeNode root) {
    if (root == null) {
        return null;
    }
    return getMaxTreeNode(root);
}

private TreeNode getMaxTreeNode(TreeNode root) {
    if (root == null) {
        return new TreeNode(Integer.MIN_VALUE);
    }
    TreeNode left = getMaxTreeNode(root.left);
    TreeNode right = getMaxTreeNode(root.right);
    if (root.val > left.val && root.val > right.val) {
        return root;
    } else if (right.val > left.val && right.val > root.val) {
        return right;
    }
    return left;
}
 }

简析：使用了递归的思想；注意为空的判断；

二、单例

单例 是最为最常见的设计模式之一。对于任何时刻，如果某个类只存在且最多存在一个具体的实例，那么我们称这种设计模式为单例。例如，对于 class Mouse (不是动物的mouse哦)，我们应将其设计为 singleton 模式。

你的任务是设计一个 getInstance 方法，对于给定的类，每次调用 getInstance 时，都可得到同一个实例。

样例：
在 Java 中:

A a = A.getInstance();
A b = A.getInstance();
a 应等于 b.

挑战：
如果并发的调用 getInstance，你的程序也可以正确的执行么？

class Solution {
private volatile static  Solution mInstance = null;
/**
* @return: The same instance of this class every time
*/
public static Solution getInstance() {
    if (mInstance == null) {
        synchronized(Solution.class) {
            if (mInstance == null) {
                mInstance = new Solution();    
            }
        }
    }
    return mInstance;
}

private Solution() {}

}

注意：实现一个单例有两点注意事项，①将构造器私有，不允许外界通过构造器创建对象；②通过公开的静态方法向外界返回类的唯一实例

参考：单例模式的几种写法对比：
http://wuchong.me/blog/2014/08/28/how-to-correctly-write-singleton-pattern/

三、整数排序

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。

样例：
对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]。

答案(java版本)：

选择排序：

public void sortIntegers(int[] A) {
    int i, j, min, temp, len = A.length;
    for (i = 0; i < len -1; i++) {
        min = i; //未排序序列中最小数据数组下标
        for (j = i + 1; j < len; j++) { //在未排序元素中继续寻找最小元素，并保存其下标
            if (A[min] > A[j]) {
                min = j;
            }
        }
        if (i != min) { //将最小元素放到已排序序列的末尾
            temp = A[min];
            A[min] = A[i];
            A[i] = temp;
        }
    }    
}

冒泡排序：

public void sortIntegers(int[] A) {
    int i, j, temp, len = A.length;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - i - 1; j ++)
        if (A[j] > A[j+1]) {
            temp = A[j+1];
            A[j+1] = A[j];
            A[j] = temp;
        }
    }
    
}

答案解析：
各个语言的实现请参考维基百科：https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F

** 四、斐波那契数列**

查找斐波纳契数列中第 N 个数。所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

答案：

public int fibonacci(int n) {
    // write your code here
    int a1 = 0;
    int a2 = 1;
    int result = 0;
    if (n == 1) {
        return a1;
    }
    if (n == 2) {
        return a2;
    }
    for (int i = 3; i <= n; i++) {
        result = a1 + a2;
        a1 = a2; 
        a2 = result;
    }
    return result;
}

注意事项：
1、n是从1开始的，而不是0
2、一般我们都会想到用递归的方式实现，但是这个时间开销很大：

int fibonacci(int n) { 
  if (n == 1)
      return 0;
  else if (n == 2)
      return 1;
  return fib(n-1) + fib(n-2);
}

3、题目的引申: 青蛙跳阶梯，铺方砖
参考：http://www.bubuko.com/infodetail-1099705.html