一、在二叉树中寻找值最大的节点并返回：
给出如下一棵二叉树：
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
网友评论