1、字符串

　　如果IDE沒有代碼自動(dòng)補(bǔ)全功能，所以你應(yīng)該記住下面的這些方法。

　　toCharArray() //獲得字符串對(duì)應(yīng)的char數(shù)組

　　Arrays.sort() //數(shù)組排序

　　Arrays.toString(char[] a) //數(shù)組轉(zhuǎn)成字符串

　　charAt(int x) //獲得某個(gè)索引處的字符

　　length() //字符串長(zhǎng)度

　　length //數(shù)組大小

　　2、鏈表

　　在Java中，鏈表的實(shí)現(xiàn)非常簡(jiǎn)單，每個(gè)節(jié)點(diǎn)Node都有一個(gè)值val和指向下個(gè)節(jié)點(diǎn)的鏈接next。

　　class Node {

　　int val;

　　Node next;

　　Node(int x) {

　　val = x;

　　next = null;

　　}

　　}

　　鏈表兩個(gè)著名的應(yīng)用是棧Stack和隊(duì)列Queue。

　　棧：

　　class Stack{

　　Node top;

　　public Node peek(){

　　if(top != null){

　　return top;

　　}

　　return null;

　　}

　　public Node pop(){

　　if(top == null){

　　return null;

　　}else{

　　Node temp = new Node(top.val);

　　top = top.next;

　　return temp;

　　}

　　}

　　public void push(Node n){

　　if(n != null){

　　n.next = top;

　　top = n;

　　}

　　}

　　}

　　隊(duì)列：

　　class Queue{

　　Node first, last;

　　public void enqueue(Node n){

　　if(first == null){

　　first = n;

　　last = first;

　　}else{

　　last.next = n;

　　last = n;

　　}

　　}

　　public Node dequeue(){

　　if(first == null){

　　return null;

　　}else{

　　Node temp = new Node(first.val);

　　first = first.next;

　　return temp;

　　}

　　}

　　}

　　3、樹

　　這里的樹通常是指二叉樹，每個(gè)節(jié)點(diǎn)都包含一個(gè)左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)，像下面這樣：

　　class TreeNode{

　　int value;

　　TreeNode left;

　　TreeNode right;

　　}

　　下面是與樹相關(guān)的一些概念：

　　1)平衡vs.非平衡：平衡二叉樹中，每個(gè)節(jié)點(diǎn)的左右子樹的深度相差至多為1(1或0)。

　　2)滿二叉樹(Full Binary Tree)：除葉子節(jié)點(diǎn)以為的每個(gè)節(jié)點(diǎn)都有兩個(gè)孩子。

　　3)完美二叉樹(Perfect Binary Tree)：是具有下列性質(zhì)的滿二叉樹：所有的葉子節(jié)點(diǎn)都有相同的深度或處在同一層次，且每個(gè)父節(jié)點(diǎn)都必須有兩個(gè)孩子。

　　4)完全二叉樹(Complete Binary Tree)：二叉樹中，可能除了最后一個(gè)，每一層都被完全填滿，且所有節(jié)點(diǎn)都必須盡可能想左靠。

　　譯者注：完美二叉樹也隱約稱為完全二叉樹。完美二叉樹的一個(gè)例子是一個(gè)人在給定深度的祖先圖，因?yàn)槊總�(gè)人都一定有兩個(gè)生父母。完全二叉樹可以看成是可以有若干額外向左靠的葉子節(jié)點(diǎn)的完美二叉樹。

　　4、疑問：完美二叉樹和滿二叉樹的區(qū)別?

　　圖相關(guān)的問題主要集中在深度優(yōu)先搜索(depth first search)和廣度優(yōu)先搜索(breath first search)。

　　下面是一個(gè)簡(jiǎn)單的圖廣度優(yōu)先搜索的實(shí)現(xiàn)。

　　1)定義GraphNode

　　class GraphNode{

　　int val;

　　GraphNode next;

　　GraphNode[] neighbors;

　　boolean visited;

　　GraphNode(int x) {

　　val = x;

　　}

　　GraphNode(int x, GraphNode[] n){

　　val = x;

　　neighbors = n;

　　}

　　public String toString(){

　　return "value: "+ this.val;

　　}

　　}

　　2)定義一個(gè)隊(duì)列Queue

　　class Queue{

　　GraphNode first, last;

　　public void enqueue(GraphNode n){

　　if(first == null){

　　first = n;

　　last = first;

　　}else{

　　last.next = n;

　　last = n;

　　}

　　}

　　public GraphNode dequeue(){

　　if(first == null){

　　return null;

　　}else{

　　GraphNode temp = new GraphNode(first.val, first.neighbors);

　　first = first.next;

　　return temp;

　　}

　　}

　　}

　　3)用隊(duì)列Queue實(shí)現(xiàn)廣度優(yōu)先搜索

　　public class GraphTest {

　　public static void main(String[] args) {

　　GraphNode n1 = new GraphNode(1);

　　GraphNode n2 = new GraphNode(2);

　　GraphNode n3 = new GraphNode(3);

　　GraphNode n4 = new GraphNode(4);

　　GraphNode n5 = new GraphNode(5);

　　n1.neighbors = new GraphNode[]{n2,n3,n5};

　　n2.neighbors = new GraphNode[]{n1,n4};

　　n3.neighbors = new GraphNode[]{n1,n4,n5};

　　n4.neighbors = new GraphNode[]{n2,n3,n5};

　　n5.neighbors = new GraphNode[]{n1,n3,n4};

　　breathFirstSearch(n1, 5);

　　}

　　public static void breathFirstSearch(GraphNode root, int x){

　　填寫下面表單即可預(yù)約申請(qǐng)免費(fèi)試聽java課程!害怕學(xué)不會(huì)?助教全程陪讀，隨時(shí)解惑!擔(dān)心就業(yè)?一地學(xué)習(xí)，可全國(guó)推薦就業(yè)!

　　if(root.val == x)

　　System.out.println("find in root");

　　Queue queue = new Queue();

　　root.visited = true;

　　queue.enqueue(root);

　　while(queue.first != null){

　　GraphNode c = (GraphNode) queue.dequeue();

　　for(GraphNode n: c.neighbors){

　　if(!n.visited){

　　System.out.print(n + " ");

　　n.visited = true;

　　if(n.val == x)

　　System.out.println("Find "+n);

　　queue.enqueue(n);

　　}

　　}

　　}

　　}

　　}

　　Output:

　　1

　　2

　　value: 2 value: 3 value: 5 Find value: 5

　　value: 4

　　5、排序

　　下面是不同排序算法的時(shí)間復(fù)雜度，你可以去wiki看一下這些算法的基本思想。

　　Algorithm

　　Average Time

　　Worst Time

　　Space

　　冒泡排序

　　n^2

　　n^2

　　1

　　選擇排序

　　n^2

　　n^2

　　1

　　Counting Sort

　　n+k

　　n+k

　　n+k

　　Insertion sort

　　n^2

　　n^2

　　Quick sort

　　n log(n)

　　n^2

　　Merge sort

　　n log(n)

　　n log(n)

　　depends

　　另外，這里有一些實(shí)現(xiàn)/演示：: Counting sort、Mergesort、Quicksort、InsertionSort。

　　《視覺直觀感受7種常用的排序算法》

　　《視頻: 6分鐘演示15種排序算法》

　　6、遞歸VS迭代

　　對(duì)程序員來(lái)說，遞歸應(yīng)該是一個(gè)與生俱來(lái)的思想(a built-in thought)，可以通過一個(gè)簡(jiǎn)單的例子來(lái)說明。

　　問題：有n步臺(tái)階，一次只能上1步或2步，共有多少種走法。

　　步驟1:找到走完前n步臺(tái)階和前n-1步臺(tái)階之間的關(guān)系。

　　為了走完n步臺(tái)階，只有兩種方法：從n-1步臺(tái)階爬1步走到或從n-2步臺(tái)階處爬2步走到。如果f(n)是爬到第n步臺(tái)階的方法數(shù)，那么f(n) = f(n-1) + f(n-2)。

　　步驟2:確保開始條件是正確的。

　　f(0) = 0;

　　f(1) = 1;

　　public static int f(int n){

　　if(n <= 2) return n;

　　int x = f(n-1) + f(n-2);

　　return x;

　　}

　　遞歸方法的時(shí)間復(fù)雜度是n的指數(shù)級(jí)，因?yàn)橛泻芏嗳哂嗟挠?jì)算，如下：

　　f(5)

　　f(4) + f(3)

　　f(3) + f(2) + f(2) + f(1)

　　f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

　　f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

　　直接的想法是將遞歸轉(zhuǎn)換為迭代：

　　public static int f(int n) {

　　if (n <= 2){

　　return n;

　　}

　　int first = 1, second = 2;

　　int third = 0;

　　for (int i = 3; i <= n; i++) {

　　third = first + second;

　　first = second;

　　second = third;

　　}

　　return third;

　　}

　　對(duì)這個(gè)例子而言，迭代花費(fèi)的時(shí)間更少，你可能也想看看Recursion vs Iteration。

　　7、動(dòng)態(tài)規(guī)劃

　　動(dòng)態(tài)規(guī)劃是解決下面這些性質(zhì)類問題的技術(shù)：

　　1)一個(gè)問題可以通過更小子問題的解決方法來(lái)解決(譯者注：即問題的最優(yōu)解包含了其子問題的最優(yōu)解，也就是最優(yōu)子結(jié)構(gòu)性質(zhì))。

　　2)有些子問題的解可能需要計(jì)算多次(譯者注：也就是子問題重疊性質(zhì))。

　　3)子問題的解存儲(chǔ)在一張表格里，這樣每個(gè)子問題只用計(jì)算一次。

　　4)需要額外的空間以節(jié)省時(shí)間。

　　爬臺(tái)階問題完全符合上面的四條性質(zhì)，因此可以用動(dòng)態(tài)規(guī)劃法來(lái)解決。

　　public static int[] A = new int[100];

　　public static int f3(int n) {

　　if (n <= 2)

　　A[n]= n;

　　if(A[n] > 0)

　　return A[n];

　　else

　　A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!

　　return A[n];

　　}

　　8、位操作

　　位操作符：

　　OR (|)

　　AND (&)

　　XOR (^)

　　Left Shift (<<)

　　Right Shift (>>)

　　Not (~)

　　1|0=1

　　1&0=0

　　1^0=1

　　0010<<2=1000

　　1100>>2=0011

　　~1=0

　　獲得給定數(shù)字n的第i位：(i從0計(jì)數(shù)并從右邊開始)

　　public static boolean getBit(int num, int i){

　　int result = num & (1<

　　if(result == 0){

　　return false;

　　}else{

　　return true;

　　}

　　例如，獲得數(shù)字10的第2位：

　　i=1, n=10

　　1<<1= 10

　　1010&10=10

　　10 is not 0, so return true;

　　9、概率問題

　　解決概率相關(guān)的問題通常需要很好的規(guī)劃了解問題(formatting the problem)，這里剛好有一個(gè)這類問題的簡(jiǎn)單例子：

　　一個(gè)房間里有50個(gè)人，那么至少有兩個(gè)人生日相同的概率是多少?(忽略閏年的事實(shí)，也就是一年365天)

　　計(jì)算某些事情的概率很多時(shí)候都可以轉(zhuǎn)換成先計(jì)算其相對(duì)面。在這個(gè)例子里，我們可以計(jì)算所有人生日都互不相同的概率，也就是：365/365 * 364/365 * 363/365 *…* (365-49)/365，這樣至少兩個(gè)人生日相同的概率就是1– 這個(gè)值。

　　public static double caculateProbability(int n){

　　double x = 1;

　　for(int i=0; i

　　x *= (365.0-i)/365.0;

　　}

　　double pro = Math.round((1-x) * 100);

　　return pro/100;

　　calculateProbability(50) = 0.97

　　10、排列組合

　　組合和排列的區(qū)別在于次序是否關(guān)鍵。