? ? 1二維數(shù)組中的查找
【題目】在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
【考察點】數(shù)組
【思路】從左下角開始查找，當(dāng)要查找數(shù)字比左下角數(shù)字大時，右移；當(dāng)要查找數(shù)字比左下角數(shù)字小時，上移。
【錯誤】二維數(shù)組中，數(shù)組的行數(shù)為array.length，每行數(shù)組的長度為array[i].length。注意，length是一個屬性，不是一個方法，不能寫成length()。
【代碼】
? ? 2替換空格
【題目】請實現(xiàn)一個函數(shù)，將一個字符串中的每個空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
【考察點】字符串
【思路】先找到字符串中的空格，我用一個數(shù)組spaceIndex來記錄空格的位置，用spaceNum來記錄空格的個數(shù)。
然后利用循環(huán)語句，將記錄下的每個空格的下標(biāo)處的內(nèi)容用StringBuffer的deleteCharAt方法刪除掉，并將“%20”用StringBuffer的insert方法插入該下標(biāo)處。
要注意的是，每當(dāng)刪除掉一個空格并替換成“%20”的時候，后面的空格的下標(biāo)位置就會+2，所以我又用了flag變量，它的初始值是0，在每次替換后+2。在遍歷這些空格的下標(biāo)的時候，我就不再直接用spaceIndex[i]了，這樣會出錯，而是用spaceIndex[i]+flag，這樣每個空格下標(biāo)的位置就隨著字符串的長度變化而動態(tài)的變化著>_<
【錯誤1】沒有return
【錯誤2】spaceIndex[]沒有初始化
【錯誤3】替換空格為%20的時候，終止條件不應(yīng)用數(shù)組spaceIndex的長度來控制，因為它始終是100，而是用spaceNum+1來控制。
【代碼】
? ? 3從尾到頭打印鏈表
【題目】輸入一個鏈表，按鏈表值從尾到頭的順序返回一個ArrayList。
【考察點】鏈表
哇塞一次性AC，好開心！
【思路】利用ArrayList中的Add方法，可以將元素插入指定位置，順序遍歷鏈表將每個元素都插入ArrayList的0下標(biāo)位置，即可實現(xiàn)逆序。
【代碼】
? ? 4重建二叉樹
【題目】輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。
【考察點】樹
【思路】二叉樹的前序遍歷順序是：先訪問根節(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹。
中序遍歷順序是：中序遍歷根節(jié)點的左子樹，然后是訪問根節(jié)點，最后中序遍歷右子樹。
我們可以知道的是：
1、二叉樹的前序遍歷序列一定是該樹的根節(jié)點。
2、中序遍歷序列中根節(jié)點前面一定是該樹的左子樹，后面是該樹的右子樹。
從上面可知，題目中前序遍歷的第一個節(jié)點{1}一定是這棵二叉樹的根節(jié)點，根據(jù)中序遍歷序列，可以發(fā)現(xiàn)中序遍歷序列中節(jié)點{1}之前的{4,7,2}是這棵二叉樹的左子樹，{5,3,8,6}是這棵二叉樹的右子樹。然后，對于左子樹，遞歸地把前序子序列{2,4,7}和中序子序列{4,7,2}看成新的前序遍歷和中序遍歷序列。此時，對于這兩個序列，該子樹的根節(jié)點是{2}，該子樹的左子樹為{4,7}、右子樹為空，如此遞歸下去（即把當(dāng)前子樹當(dāng)做樹，又根據(jù)上述步驟分析）。{5,3,8,6}這棵右子樹的分析也是這樣。
【出錯點】判斷結(jié)束標(biāo)志寫成了==（應(yīng)該是>），且返回的是tree(應(yīng)該是null)。
【關(guān)鍵點1】結(jié)束遞歸的標(biāo)志是pStart>pEnd&&iStart>iEnd，注意這里是>而不是==或者>=哦。（==說明這個時候數(shù)組中只有一個數(shù)字，這個節(jié)點是一個葉子節(jié)點；>說明這個時候數(shù)組是空的，這個節(jié)點是null，此時我們結(jié)束遞歸返回null）
【關(guān)鍵點2】注意遞歸時候pStart、pEnd、iStart、iEnd的取值。一般左子樹的pStart都是在原先pStart上加1，pEnd原先pStart加上左子樹的長度（i-iStart），iStart和iEnd就比較好求，此處略。
【代碼】
