似乎，，，，返回結果的空間不會算在空間復雜度上

思維的全面性（各種邊界條件）

索引與中點的關系：

設最后元素的索引為n，則中點的索引為n/2【對于奇數(shù)正好是中點，對于偶數(shù)個元素，則是前面的一個元素】（除以2可以考慮采用移位）

/2問題???？？？

設長度為n,索引值：0 ?~ ?n/2-1？？？？

返回值為java內置類型時，返回null則會報錯；

而返回值為自定義類型或數(shù)組類型時，返回null不會報錯。

常用：

Collections.sort(res);

無窮等特殊值

double：Double.POSITIVE_INFINITY，Double.NEGATIVE_INFINITYInt：

Integer.MIN_VALUE，Integer.MAX_VALUE

好題

unique-binary-search-trees-ii（看起來沒有一點頭緒）：?

https://www.nowcoder.com/practice/98aaaefacaca44b9b4f2f2bd75780664?tpId=46&tqId=29082&tPage=3&rp=3&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking

排序

選擇排序（冒泡）

插入排序

希爾排序（基于插入排序）

歸并排序

快排

利用快排思想：

最小的k個數(shù)【此外若要求不能改變數(shù)組，則需要采用其他方法,紅黑樹】

數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)【此外若要求不能改變數(shù)組，則需要采用其他方法：該數(shù)字出現(xiàn)的次數(shù)要大于其他所有數(shù)字出現(xiàn)次數(shù)總和 】

優(yōu)先隊列

查找

順序查找

二分查找（排序數(shù)組、部分排序數(shù)組）

二叉樹查找

哈希表查找

樹總結

樹就用遍歷與遞歸知識！

若要求處理一棵二叉樹的遍歷序列，則可先找到根節(jié)點，然后在分為左右子樹，遞歸地處理兩子樹。

層序遍歷就是廣度優(yōu)先搜索。

遍歷

https://blog.csdn.net/workformywork/article/details/21628351

前序遍歷、中序遍歷、后序遍歷的非遞歸實現(xiàn)，時間復雜度為n,空間復雜度為1的Morris方法

preorder

inorder

postorder

怎么變成后序的呢？？？

http://blog.csdn.net/whzyb1991/article/details/44278723

3步走：

1.左右翻轉

2.前序遍歷

3.反轉順序

void InOrderTraversal( BinTree BT )

{

BinTree T BT;

Stack S = CreatStack( MaxSize ); /*

創(chuàng)建并初始化堆棧 S*/

Stack Q = CreatStack( MaxSize ); /*

創(chuàng)建并初始化堆棧 Q，用于輸出反向*/

while( T || !IsEmpty(S) ){

while(T){ /*

一直向右并將沿途結點壓入堆棧*/

Push(S,T);

Push(Q,T);/*將遍歷到的結點壓棧，用于反向*/

T = T->Right;

}

if(!IsEmpty(S)){

T = Pop(S); /*

結點彈出堆棧*/

T = T->Left; /*

轉向左子樹*/

}

}

while( !IsEmpty(Q) ){

T = Pop(Q);

printf(“%5d”, T->Data); /*

（訪問）打印結點*/

}

}

解釋是： 先序的訪問順序是 root, left, right 假設將先序左右對調，則順序變成 root, right, left，暫定

稱之為

“反序” 。

后序遍歷的訪問順序為 left, right,root ，剛好是“反序”結果的逆向輸出。于是方法如下：

1、反序遍歷二叉樹，具體方法為：將先序遍歷代碼中的 left 和 right 對調即可。

數(shù)據(jù)存在堆棧

S 中。

2、在先序遍歷過程中，每次 Push 節(jié)點后緊接著 print 結點。

對應的，在反序遍歷時，將

print 結點改為把當前結點 PUSH 到堆棧 Q 中。

3、反序遍歷完成后，堆棧 Q 的壓棧順序即為反序遍歷的輸出結果。

此時再將堆棧

Q 中的結果 pop 并 print，即為“反序”結果的逆向，也就是后序遍歷的結果。

缺點是堆棧

Q 的深度等于數(shù)的結點數(shù)，空間占用較大。

level:又分為

1.正常的【利用Queue，雖然順序是對的，但層之間已混在一塊】

2.cur與next的【此時需要明確區(qū)分層級之間的關系，用cur與next得以區(qū)分層與層，但是忘記哪個題目了】

時間復雜度為n,空間復雜度為1的Morris方法：（中序遍歷）

https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

Morris算法與遞歸和使用?？臻g遍歷的思想不同，它使用二叉樹中的葉節(jié)點的right指針來保存后面將要訪問的節(jié)點的信息，當這個right指針使用完成之后，再將它置為NULL，但是在訪問過程中有些節(jié)點會訪問兩次，所以與遞歸的空間換時間的思路不同，Morris則是使用時間換空間的思想，先來看看Morris中序遍歷二叉樹的算法實現(xiàn)：[cpp]?view plain?copy

第一個print為打印左子節(jié)點，第二個為打印當前根節(jié)點

前序遍歷：

動態(tài)規(guī)劃總結------------------------------------------------------------------

常見問法：有無，有多少條（并不求出具體形式）。

（若要求尋找各種組合的具體形式，則是回溯問題）

任何動態(tài)規(guī)劃都是擁有“嚇人的”外殼，但還有一顆柔軟的內心。

本質就是：

1.狀態(tài)（找到）

2.狀態(tài)轉移。(本狀態(tài)與上一次或周邊狀態(tài)的轉換關系）

（然后找到初值，即可）

很多動態(tài)規(guī)劃可以采用滾動數(shù)組的形式以減少空間復雜度（對于一般動歸，空間復雜度從n2降到n）

狀態(tài)表示方法比較重要，主要有：

1.每個位置一個狀態(tài)；

2.每一段一個狀態(tài)。

另外比較高端的解釋：

1.最優(yōu)子結構：問題的最優(yōu)解由相關子問題的最優(yōu)解組合而成，而這些子問題可獨立求解。

2.重疊子問題：遞歸算法反復求解相同的子問題，動態(tài)規(guī)劃算法中使用數(shù)組來保存子問題的解

算法-動態(tài)規(guī)劃 Dynamic Programming--從菜鳥到老鳥

知乎文章：

每個階段只有一個狀態(tài)->遞推；

每個階段的最優(yōu)狀態(tài)都是由上一個階段的最優(yōu)狀態(tài)得到的->貪心；

每個階段的最優(yōu)狀態(tài)是由之前所有階段的狀態(tài)的組合得到的->搜索；

每個階段的最優(yōu)狀態(tài)可以從之前某個階段的某個或某些狀態(tài)直接得到而不管之前這個狀態(tài)是如何得到的->動態(tài)規(guī)劃。

廣搜

采用Queue（記為q）記錄當前的元素，采用visited記錄是否被訪問過，并尋找q中每一元素（不斷pop出來）的neighbors，根據(jù)visited對neighbors進行判重，若不重復，則加入q;否則舍棄。（有時，可能使用HashSet等代替Stack）

有時可以使用雙隊列的方式，從兩頭開始，每次采用size小的一遍尋找neighbors。

回溯------------------------------------------------------------------------------

問題形式：

問題：

求各種組合（可能）：

https://blog.csdn.net/versencoder/article/details/52071930【寫的非常好?。?！】

n皇后問題（典型深搜問題）：

N皇后問題

同一個循環(huán)中不能有同樣的元素，而嵌套循環(huán)中可有：

combination-sum-ii

字符串字符前后交換：

字符串的排列

心得：

任何回溯都是擁有“嚇人的”外殼，但還有一顆柔軟的內（套）心（路）。

都是套路。。。

收斂條件(有時收斂條件和終止條件會合二為一)

終止條件

剪枝

所有可能擴展操作

數(shù)組-------------------------------------------------------------------------

注意邊界條件，異常情況

1.兩已排好序數(shù)組第k大數(shù)

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

2.合并空間

merge-intervals

鏈表

注意&常使用：

異常和邊界檢查

常使用dummy節(jié)點進行反轉 ? ? ?【ListNode dummy=new ListNode(-1); ? ? ? dummy.next=head;】

快慢指針（尋找鏈表中點，尋找環(huán)，尋找環(huán)的起點（https://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad））

某一指針多走幾步

原地復制形成雙重鏈表（復制復雜鏈表https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking）

1.前插法反轉鏈表

很多題目都使用該思想！

示意圖

反轉部分節(jié)點

2.形成一個環(huán)可能會減少工作量

一塊一塊的順序未變。

rotate-list

3.快慢指針

字符串

相互轉化：

Arrays.sort()

String<->int：

Integer.parseInt(str)

Integer.toString(n)

String<->double：

Double.parseDouble(str)

Double?.toString(n)

Char->String:

1. String s = String.valueOf('c');//效率最高的方法

2. String s = String.valueOf(new char[]{'c'});//將一個char數(shù)組轉換成String

3. String s = Character.toString('c');// Character.toString(char)方法實際上直接返回String.valueOf(char)

4. String s =newCharacter('c').toString();

5. String s = "" + 'c';// 雖然這個方法很簡單，但這是效率最低的方法

// Java中的String Object的值實際上是不可變的，是一個final的變量。

// 所以我們每次對String做出任何改變，都是初始化了一個全新的String Object并將原來的變量指向了這個新String。// 而Java對使用+運算符處理String相加進行了方法重載。

// 字符串直接相加連接實際上調用了如下方法：

// new StringBuilder().append("").append('c').toString();

6. String s =newString(newchar[]{'c'});

String-> Char:

1.String.charAt(index)

2.String.toCharArray()

沒有什么難度，主要是考慮到各種極限情況。掌握了下面常用的函數(shù)即可

s.substring(s,e);//不包含e

s.split("/");

Arrays

在Java中Arrays工具類實現(xiàn)功能的六種方法

使用Arrays工具類，要先導入包即：import.java.util.Arrays

以下是實現(xiàn)六種功能的方法：

1、toString方法是把數(shù)組轉換成字符串進行輸出。（參數(shù)是數(shù)組，返回的是字符串）

int[] a1={1,2,3,4};

System.out.println(Arrays.toString(a1));

原理：【 String s1=Arrays.toString(a1);

System.out.println(s1);】

2、sort方法，把數(shù)組中的元素按升序排序。【參數(shù)：除了布爾型都可以，類也可以】

Arrays.sort(a); //排序,a為數(shù)組

//如果h是字符串的話

String[]s1={"c","ab","d","e"};

Arrays.sort(s1);

for(String s:s1){

System.out.println(s);

}

3、BinarySearch:找到元素在數(shù)組當中的下標。

String[]s3={"a","b","c","d","e","w"};

int index=Arrays.binarySearch(s3,"g");

System.out.println("該元素的下標是："+index);

//運行結果：下標為：-6.（找不到g；-（插入點5）-1)=-6

4、比較兩個數(shù)組值是否相等：結果為true、false.(布爾型不能比較)

int []a={10,20,30};

int []b={10,20,30};

int []c={1,2,3};

boolean isEqual=Arrays.equals(a,b); //定義boolean型變量isEqual，

System.out.println(isEqual); //isEqual只能是true或是flase,將a,b比較的值賦給isEqual，并打印

//或者直接用 System.out.println(Arrays.equals(a,b));

System.out.println(Arrays.equals(a,c));

5、copyOf把一個數(shù)組復制出一個新數(shù)組（新數(shù)組的長度為length）

int[]s1={11,22,33,44};

int[]s2=Arrays.copyOf(s1,2); //將s1數(shù)組中的前面的兩個元素復制到s2中

System.out.println(Arrays.toString(s2));

6、fill方法：把整個數(shù)組里的每一個元素的值進行替換為val。函數(shù)原理：（void fill(Arrays,val)）

int[]s1={11,22,33,44};

Arrays.fill(s1,10);

String初始化細節(jié)（挺好）

StringBuffer，StringBuilder

String，StringBuffer，StringBuilder區(qū)分

StringBuilder,StringBuffer函數(shù)

兩者常用函數(shù)：

http://www.runoob.com/java/java-stringbuffer.html

當對字符串進行修改的時候，需要使用 StringBuffer 和 StringBuilder 類。

和 String 類不同的是，StringBuffer 和 StringBuilder 類的對象能夠被多次的修改，并且不產(chǎn)生新的未使用對象。

StringBuilder 類在 Java 5 中被提出，它和 StringBuffer 之間的最大不同在于 StringBuilder 的方法不是線程安全的（不能同步訪問）。

由于 StringBuilder 相較于 StringBuffer 有速度優(yōu)勢，所以多數(shù)情況下建議使用 StringBuilder 類。然而在應用程序要求線程安全的情況下，則必須使用 StringBuffer 類。

StringBuffer 的幾個函數(shù)比較重要：setCharAt，charAt，setLength

刪除stringbuilder最后一個元素：res.setLength(res.length()-1); ?或者res.deleteCharAt(res.length()-1);

導入的包

import java.util.*;

常用的

數(shù)組的大?。篴.length;

字符串的大?。簊.length();

對象、數(shù)組做參數(shù)，傳過去的是地址?；緮?shù)據(jù)類型傳遞的是值。

所以你在你調用的方法里面可以修改對象的某些屬性（值），基本數(shù)據(jù)類型就不可以。Java中數(shù)組也是傳遞地址的。

因此我們如果在某些地方調用其他方法時，需要用傳進去的參數(shù)把結果帶回來，就可以用對象或者數(shù)組做參數(shù)，但用基本數(shù)據(jù)類型，就不能把結果帶回來

基本數(shù)據(jù)類型

byte：8位，最大存儲數(shù)據(jù)量是255，存放的數(shù)據(jù)范圍是-128~127之間。默認值是?0；

short：16位，最大數(shù)據(jù)存儲量是65536，數(shù)據(jù)范圍是-32768~32767之間。默認值是?0；

int：32位，最大數(shù)據(jù)存儲容量是2的32次方減1，數(shù)據(jù)范圍是負的2的31次方到正的2的31次方減1。默認值是?0；

long：64位，最大數(shù)據(jù)存儲容量是2的64次方減1，數(shù)據(jù)范圍為負的2的63次方到正的2的63次方減1。默認值是?0L；

float：32位，數(shù)據(jù)范圍在3.4e-45~1.4e38，直接賦值時必須在數(shù)字后加上f或F。默認值是?0.0f；

double：64位，數(shù)據(jù)范圍在4.9e-324~1.8e308，賦值時可以加d或D也可以不加。默認值是?0.0d；

boolean：只有true和false兩個取值。默認值是?false；

char：16位，存儲Unicode碼，用單引號賦值。判斷是否相等時，可直接用==來判斷

ck

如果要求輸出所有可能的解，往往都是要用深度優(yōu)先搜索。如果是要求找出最優(yōu)的解，或者解的數(shù)量，往往可以使用動態(tài)規(guī)劃。

需要new動態(tài)數(shù)組

res.add(new ArrayList(path));//**如果不new，則在path，remove后，則res就沒有了。

數(shù)組

判斷二維數(shù)組是否為空

1.二維board?

if(board==null || board.length==0 || (?board.length==1 && board[0].length==0?)) return;

2.

長度為0的數(shù)組（空數(shù)組） int[] arr = new int[0]，也稱為空數(shù)組，雖然arr長度為0，但是依然是一個對象

null數(shù)組，int[] arr = null；arr是一個數(shù)組類型的空引用。

則： if?(nums?==?null?||?nums.length?==?0)?{ ?.............? ?}

位運算

相關題目：

二進制中1的個數(shù)

1.移位

>>

對于正數(shù)，左側補0；

對于負數(shù)，左側補1。

2.常用操作

就是常見的操作

一個正數(shù)減去1，則該數(shù)最右邊的1變?yōu)?，而右側還有0的話，則全部變?yōu)?，左側則保持不變.因此，操作前后的數(shù)相與，則相當于把最右邊的1變?yōu)?.【很多二進制問題均可以采用本思路】

其他

判斷兩個double是否相等：

private boolean equal(double n1,double n2)

? ? { ?return ((n1-n2)<0.0000001 && (n1-n2)>-0.0000001); ?}

判斷是否為奇數(shù)

if(n & 0x01==1)?

/2 ?(整除)

n>>1

循環(huán)打?。篽ttps://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a?tpId=13&tqId=11172&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

內部類

？？？？？？？？？？？？？？？？？？

publicclassStringChar?{

????publicstaticvoidmain(String[]?args)?{

????????//字符串--》字符

????????String?str1?=?"風云";

????????charc1?=?str1.charAt(0);//風，?如果要得到云。那么charAt(1);

????????System.out.println(c1);

????????char[]?cs1?=?str1.toCharArray();//字符串轉字符數(shù)組

????????System.out.println(Arrays.toString(cs1));

????????//字符--》字符串

????????charc2?=?'明';

????????String?str2?=?String.valueOf(c2);//字符轉字符串

????????//String?str2??=?c2+"";??//也可以把字符轉換成字符串類型

????????System.out.println(str2);

????????char[]?cs2?=?{'明','月'};

????????String?str3?=?String.copyValueOf(cs2);//字符數(shù)組變字符串

????????System.out.println(str3);

????????String?str4?=?newString(cs2);//字符數(shù)組變字符串

????????System.out.println(str4);

????}

}