一、在二叉樹中尋找值最大的節(jié)點(diǎn)并返回：
給出如下一棵二叉樹：
1
/ \
-5 2
/ \ / \
0 3 -4 -5
返回值為 3 的節(jié)點(diǎn)。
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;
}
}
簡析：使用了遞歸的思想哩簿；注意為空的判斷宵蕉；
二、單例
單例 是最為最常見的設(shè)計模式之一节榜。對于任何時刻羡玛，如果某個類只存在且最多存在一個具體的實(shí)例，那么我們稱這種設(shè)計模式為單例宗苍。例如稼稿，對于 class Mouse (不是動物的mouse哦)，我們應(yīng)將其設(shè)計為 singleton 模式讳窟。
你的任務(wù)是設(shè)計一個 getInstance 方法让歼，對于給定的類，每次調(diào)用 getInstance 時丽啡，都可得到同一個實(shí)例是越。
樣例：
在 Java 中:
A a = A.getInstance();
A b = A.getInstance();
a 應(yīng)等于 b.
挑戰(zhàn)：
如果并發(fā)的調(diào)用 getInstance，你的程序也可以正確的執(zhí)行么碌上？
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() {}
}
注意：實(shí)現(xiàn)一個單例有兩點(diǎn)注意事項(xiàng)倚评，①將構(gòu)造器私有，不允許外界通過構(gòu)造器創(chuàng)建對象馏予；②通過公開的靜態(tài)方法向外界返回類的唯一實(shí)例
參考：單例模式的幾種寫法對比：
http://wuchong.me/blog/2014/08/28/how-to-correctly-write-singleton-pattern/
三天梧、整數(shù)排序
給一組整數(shù)，按照升序排序霞丧，使用選擇排序呢岗，冒泡排序，插入排序或者任何 O(n2) 的排序算法蛹尝。
樣例：
對于數(shù)組 [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; //未排序序列中最小數(shù)據(jù)數(shù)組下標(biāo)
for (j = i + 1; j < len; j++) { //在未排序元素中繼續(xù)尋找最小元素，并保存其下標(biāo)
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;
}
}
}
答案解析：
各個語言的實(shí)現(xiàn)請參考維基百科：https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
** 四突那、斐波那契數(shù)列**
查找斐波納契數(shù)列中第 N 個數(shù)挫酿。所謂的斐波納契數(shù)列是指：
前2個數(shù)是 0 和 1 。
第 i 個數(shù)是第 i-1 個數(shù)和第i-2 個數(shù)的和愕难。
斐波納契數(shù)列的前10個數(shù)字是：
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;
}
注意事項(xiàng)：
1早龟、n是從1開始的，而不是0
2猫缭、一般我們都會想到用遞歸的方式實(shí)現(xiàn)葱弟，但是這個時間開銷很大：
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
