題目1：設(shè)計(jì)一個(gè)類越走，我們只能生成該類的一個(gè)實(shí)例
//雙檢鎖/雙重校驗(yàn)鎖（DCL澜汤，即 double-checked locking）
public class Singleton {
private volatile static Singleton sInstance = null;
private Singleton() {
}
public static Singleton getInstance() {
if (sInstance == null) {
synchronized (Singleton.class) {
if (sInstance == null) {
sInstance = new Singleton();
}
}
}
return sInstance;
}
}
題目2：找出數(shù)組中的重復(fù)數(shù)字械筛，時(shí)間復(fù)雜度O(n)
//對于一維數(shù)組排序滿足O（n）時(shí)間復(fù)雜度，優(yōu)先考慮hashmap
private static int findDuplicateNumber(int[] list) {
int number = -1;
//以數(shù)組的數(shù)作為key，如果key有重復(fù)诡曙，value遞增
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i=0; i<list.length; i++) {
if (map.containsKey(list[i])) {
map.put(list[i], map.get(list[i]) + 1);
} else {
map.put(list[i], 1);
}
}
//便利hashmap臀叙，找出value大于1對應(yīng)的key值
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
if (entry.getValue() > 1) {
number = entry.getKey();
}
}
return number;
}
題目3：實(shí)現(xiàn)一個(gè)函數(shù)，把字符串每中的每個(gè)空格替換成“%20”价卤。例如輸入“we are happy.”劝萤，則輸出“we%20are%20happy.”
public static void main (String[] args) {
String str = "We are happy!";
replaceBlank(str.toCharArray());
}
private static void replaceBlank(char[] arr) {
int count = 0;
int lenth = 0;
//計(jì)算新數(shù)組長度，等于原長度加上空格數(shù)*2
for (int i=0; i<arr.length; i++) {
if (arr[i] == ' ') {
count ++;
}
}
lenth = arr.length + count * 2;
//設(shè)置兩個(gè)指針p1,p2慎璧，如果p1遇到空格床嫌，p2 后三位賦值%20，p1后移一位
char[] list = new char[lenth];
int p1=0, p2=0; //p1原數(shù)組指針胸私，p2 新數(shù)組指針
while (p1<arr.length && p2<lenth) {
if (arr[p1] == ' ') {
list[p2++] = '%';
list[p2++] = '2';
list[p2++] = '0';
p1++;
} else {
list[p2++] = arr[p1++];
}
}
System.out.print(String.valueOf(list));
}
題目4：有兩個(gè)排序的數(shù)組A1和A2厌处，內(nèi)存在A1的末尾有足夠多的空余空間容納A2.請實(shí)現(xiàn)一個(gè)函數(shù)，把A2中的所有數(shù)字插入A1中岁疼，并且所有的數(shù)字是排序的阔涉。
public static void main(String[] args) {
int[] A1 = {1, 3, 6, 7, 10, 23};
int[] A2 = {2, 6, 8, 24};
merged(A1, A2);
}
private static void merged(int[] A1, int[] A2) {
int indexA1 = A1.length - 1;
int indexA2 = A2.length - 1;
int mergedIndex = A1.length + A2.length - 1;
int[] mergedA = new int[A1.length + A2.length];
//從后往前插入，也可以從前往后插入
while (indexA1>=0 && indexA2>=0) {
if (A1[indexA1] >= A2[indexA2]) {
mergedA[mergedIndex--] = A1[indexA1--];
} else {
mergedA[mergedIndex--] = A2[indexA2--];
}
}
while (indexA1>=0) {
mergedA[mergedIndex--] = A1[indexA1--];
}
while (indexA2>=0) {
mergedA[mergedIndex--] = A2[indexA2--];
}
for(int i=0; i<mergedA.length; i++) {
System.out.print(mergedA[i] + ", ");
}
}
題目5：輸入一個(gè)鏈表的頭結(jié)點(diǎn)五续，從尾到頭反過來打印每個(gè)節(jié)點(diǎn)的值
//鏈表節(jié)點(diǎn)定義
static class ListNode {
int data;
ListNode next;
}
public static void main(String[] args) {
ListNode listNode = new ListNode();
ListNode listNode2 = new ListNode();
ListNode listNode3 = new ListNode();
ListNode listNode4 = new ListNode();
ListNode listNode5 = new ListNode();
listNode.data = 1;
listNode.next = listNode2;
listNode2.data = 5;
listNode2.next = listNode3;
listNode3.data = 10;
listNode3.next = listNode4;
listNode4.data = 15;
listNode4.next = listNode5;
listNode5.data = 20;
//打印鏈表
printListNode(listNode);
System.out.print("\n----------------------------\n");
//使用堆反向打印鏈表
printListReversByStack(listNode);
System.out.print("\n----------------------------\n");
//使用遞歸反向打印堆棧
printListReversByRecursive(listNode);
}
//順序打印鏈表
private static void printListNode(ListNode node) {
if (node == null) {
return;
}
while (node != null) {
System.out.print(node.data);
node = node.next;
if (node != null) {
System.out.print(" --> ");
}
}
}
//使用堆反向打印鏈表
private static void printListReversByStack(ListNode node) {
Stack<ListNode> stack = new Stack<ListNode>();
while (node != null) {
stack.push(node);
node = node.next;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop().data);
if (!stack.isEmpty()) {
System.out.print(" --> ");
}
}
}
//使用遞歸反向打印堆棧
private static void printListReversByRecursive(ListNode node) {
if (node != null) {
if (node.next != null) {
printListReversByRecursive(node.next);
}
}
System.out.print(node.data);
}
題目5：重構(gòu)二叉樹
public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
}
public static void main(String[] args) {
int[] preOrder = {1,2,4,7,3,5,6,8};
int[] inOrder={4,7,2,1,5,3,8,6};
BinaryTreeNode node = reConstruct( preOrder, inOrder );
printTree( node );
}
private static BinaryTreeNode reConstruct (int[] prOrder, int[] inOrder) {
if (prOrder == null || inOrder == null || prOrder.length != inOrder.length || prOrder.length < 1) {
return null;
}
return constrct(prOrder, 0, prOrder.length-1, inOrder, 0, inOrder.length-1);
}
/*
* @param preOrder 前序遍歷序列
* @param preBegin 前序遍歷開始位置
* @param preEnd 前序遍歷結(jié)束位置
* @param inOrder 中序遍歷序列
* @param inBegin 中序遍歷序列開始位置
* @param inEnd 中序遍歷序列結(jié)束位置
* */
private static BinaryTreeNode constrct (int[] preOrder, int preBegin, int preEnd, int[] inOrder, int inBegin, int inEnd) {
if (preBegin > preEnd) return null;
int root = preOrder[preBegin];
int index = inBegin;
while (index <= inEnd && inOrder[index] != root) {
index ++;
}
if (index > inEnd) {
throw new RuntimeException( "invalid input index: " + index);
}
BinaryTreeNode node = new BinaryTreeNode();
node.value = root;
node.left = constrct( preOrder, preBegin+1, preBegin+index-inBegin, inOrder, inBegin, index-1 );
node.right = constrct( preOrder, preBegin+index-inBegin+1, preEnd, inOrder, index+1, inEnd );
return node;
}
/*
* 中序遍歷遞歸打印
* */
private static void printTree (BinaryTreeNode node) {
if (node != null) {
printTree( node.left );
System.out.print( node.value + " " );
printTree( node.right );
}
}
