1. 二維數(shù)組中查找
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同）疾就，每一行都按照從左到右遞增的順序排序肩碟，每一列都按照從上到下遞增的順序排序贸辈。請(qǐng)完成一個(gè)函數(shù)纳决，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)碰逸，判斷數(shù)組中是否含有該整數(shù)
思路：
選擇該二維數(shù)組的最右上角的那個(gè)數(shù)開始掃描，當(dāng)target小于該值時(shí)阔加，可以清除一列饵史，當(dāng)target大于該值時(shí)，可以清除一行
public class Solution {
public boolean Find(int target, int [][] array) {
if (null == array) {
return false;
}
int i = 0;//表示第一行
int j = array[0].length;//表示該二維數(shù)組的列數(shù)
int start;
while (i < array.length && j > 0) {
start = array[i][j-1];//每次清除一行或一列后的最右上角的元素
if (target < start) {
j--;
} else if (target > start) {
i++;
} else {
return true;
}
}
return false;
}
}
2. 替換空格
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)胜榔，將一個(gè)字符串中的每個(gè)空格替換成“%20”胳喷。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy苗分。
思路：
- 將每個(gè)空格替換成“%20”厌蔽，則相當(dāng)于每一個(gè)空格都需要新加兩個(gè)字符的位置；如果考慮輸入的是一個(gè)數(shù)組摔癣，為了能夠讓每個(gè)字符只移動(dòng)一次奴饮，則可以預(yù)先預(yù)留出來足夠的正合適的空間纬向，
- 同時(shí)用兩個(gè)指針從分別從舊的末尾和新的末尾開始向前遍歷，可做到每個(gè)字符只移動(dòng)一次
public class Solution {
public String replaceSpace(StringBuffer str) {
if (null == str || str.length() == 0) {
return "";
}
int strOldLength = str.length();//最開始的字符串長度
int blankNumber = 0;//記錄空白字符的個(gè)數(shù)
for (int i = 0; i < strOldLength; i++) {
if (' ' == str.charAt(i)) {
++blankNumber;
// 每遇到一個(gè)空格戴卜，StringBuffer都在末尾新增兩個(gè)空的位置
str.append(' ').append(' ');
}
}
// 如果掃描完字符串的數(shù)組沒有發(fā)現(xiàn)空格逾条，則直接返回
if (0 == blankNumber) {
return str.toString();
}
int strNewLength = str.length();
int firstPoint = strOldLength-1; // 舊的末尾索引
int lastPoint = strNewLength-1; // 新的末尾索引
// 當(dāng)所有的空格都替換后，兩個(gè)節(jié)點(diǎn)會(huì)相遇
while (firstPoint >= 0 && lastPoint > firstPoint) {
if (' ' == str.charAt(firstPoint)) {
str.setCharAt(lastPoint--, '0'); // 設(shè)置當(dāng)前索引位置的值為0投剥，通過指針
str.setCharAt(lastPoint--, '2');
str.setCharAt(lastPoint--, '%');
} else {
str.setCharAt(lastPoint--, str.charAt(firstPoint));
}
firstPoint--;
}
return str.toString();
}
}
3. 從尾到頭打印鏈表
輸入一個(gè)鏈表师脂，按鏈表值從尾到頭的順序返回一個(gè)ArrayList。
思路：
有多種解答方案：1江锨，遞歸(本博客列出的代碼實(shí)例) 2吃警，棧 3，倒轉(zhuǎn)鏈表指針啄育，再從頭到尾打印
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {//該思路是采用遞歸酌心，從尾到頭依次打印鏈表節(jié)點(diǎn)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList arrayList = new ArrayList();
if (listNode == null) {
return arrayList;
}
printListFromTailToHead(arrayList, listNode);
return arrayList;
}
public void printListFromTailToHead(ArrayList array, ListNode listNode) {
if (listNode.next == null) {//當(dāng)?shù)竭_(dá)鏈表尾部時(shí)，將值添加到ArrayList
array.add(listNode.val);
}else {
printListFromTailToHead(array, listNode.next);//進(jìn)入下一個(gè)節(jié)點(diǎn)
array.add(listNode.val);//自己的下一個(gè)節(jié)點(diǎn)執(zhí)行完挑豌，回退到本節(jié)點(diǎn)時(shí)再將值添加進(jìn)ArrayList
}
}
4. 重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果安券，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字氓英。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}侯勉，則重建二叉樹并返回。
思路：
二叉樹的前序序列中第一個(gè)節(jié)點(diǎn)永遠(yuǎn)是根節(jié)點(diǎn)root铝阐，中序序列中root所在的位置的左邊序列址貌，都是當(dāng)前root節(jié)點(diǎn)的左子樹，右邊都是root節(jié)點(diǎn)的右子樹饰迹，
因此芳誓，前序序列的root節(jié)點(diǎn)的下一位又是它的左子樹的根節(jié)點(diǎn)，同樣的規(guī)則適用于它的左右子樹啊鸭，所以這里我們可以用遞歸來實(shí)現(xiàn)
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
// 如果數(shù)組為空或者兩個(gè)數(shù)組的長度不一致锹淌，則輸入有誤
if (pre == null || in == null || pre.length < 0 || in.length < 0 || pre.length != in.length) {
System.out.println("數(shù)組不能為空或者兩個(gè)數(shù)組長度不一致");
return null;
}
// 之所以需要四個(gè)位置變量，是因?yàn)樾枰涗浨靶蛐蛄械拈_始和結(jié)束位置赠制，也要記錄
return reConstructBinaryTree(pre, in, 0, pre.length-1, 0, in.length-1);
// 中序序列的開始和結(jié)束位置
}
// fStart表示前序序列開始節(jié)點(diǎn)赂摆， fStop表示前序序列結(jié)束節(jié)點(diǎn)，mStart表示中序序列開始節(jié)點(diǎn)钟些，mStop表示中序序列結(jié)束節(jié)點(diǎn)
public TreeNode reConstructBinaryTree(int [] pre, int [] in, int fStart, int fStop, int mStart, int mStop) {
int rootValue = pre[fStart];
TreeNode root = new TreeNode(rootValue);//先創(chuàng)建根節(jié)點(diǎn)
root.left = null;
root.right = null;
//判斷是否是只有一個(gè)節(jié)點(diǎn)
if (fStart == fStop) {
if (mStart == mStop) {
return root;
}else { //其實(shí)上面做了判斷烟号，這里就不會(huì)走到else子句中來
System.out.println("兩個(gè)數(shù)組輸入有誤");
return null;
}
}
int mm = mStart; //用一個(gè)變量記錄二叉樹的root節(jié)點(diǎn)在中序序列中的位置
//直到在中序序列中找到root，或者遍歷完中序序列數(shù)組
while (in[mm] != rootValue && mm <= mStop) {
++mm;
}
//此時(shí)還不相等的話政恍，說明中序序列中沒有此時(shí)的root
if (in[mm] != rootValue) {
System.out.println("中序序列中沒有與前序序列中確定的root節(jié)點(diǎn)相等的節(jié)點(diǎn)值");
return null;
}
//這里一定要這樣寫汪拥，記錄移動(dòng)的位置
int mLengh = mm - mStart;
//前序序列當(dāng)前的樹開始的節(jié)點(diǎn)位置+移動(dòng)的位置就等于當(dāng)前樹的子樹的結(jié)束位置
int fLeftSubTreeStop = fStart + mLengh;
if (mm > mStart) {
root.left = reConstructBinaryTree(pre, in, fStart+1, fLeftSubTreeStop, mStart, mm-1);
//(前序序列數(shù)組，中序序列數(shù)組篙耗，前序序列當(dāng)前樹開始節(jié)點(diǎn)的后一位迫筑，
//前序序列當(dāng)前樹的子樹結(jié)束的位置宪赶，中序序列當(dāng)前樹開始的位置，中序序列root位置的前一位)
}
if (mm < mStop) {
root.right = reConstructBinaryTree(pre, in, fLeftSubTreeStop+1, fStop, mm+1, mStop);
//(前序序列數(shù)組脯燃，中序序列數(shù)組搂妻，前序序列當(dāng)前樹的子樹結(jié)束的位置的前一位，
//前序序列中當(dāng)前樹結(jié)束的位置辕棚，中序序列root位置的后一位欲主，中序序列中當(dāng)前樹結(jié)束的位置
}
return root;
}
}
5. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作逝嚎。 隊(duì)列中的元素為int類型扁瓢。
思路：
- 將stack1當(dāng)做入隊(duì)列，將stack2當(dāng)做出隊(duì)列补君，當(dāng)隊(duì)列需要push入隊(duì)列一個(gè)元素的時(shí)候涤妒，直接push到stack1就可以了；當(dāng)隊(duì)列需要pop出隊(duì)列時(shí)
- 首先判斷stack2是否為空赚哗，如果為空，則將stack1中的元素全部pop出來并依次push到stack2中硅堆，再讓stack2來pop一下就可以了屿储；如果不為空，stack2直接pop一下就行渐逃。
import java.util.Stack;
public class Solution {//思路：將stack1當(dāng)做入隊(duì)列够掠，將stack2當(dāng)做出隊(duì)列，當(dāng)隊(duì)列需要push入隊(duì)列一個(gè)元素的時(shí)候茄菊，直接push到stack1就可以了疯潭；當(dāng)隊(duì)列需要pop出隊(duì)列時(shí)
//，首先判斷stack2是否為空面殖，如果為空竖哩，則將stack1中的元素全部pop出來并依次push到stack2中，再讓stack2來pop一下就可以了脊僚；如果不為空相叁，stack2直接pop一下就行。
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.size() == 0) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
if (stack2.size() == 0) {//當(dāng)stack1和stack2都長度為0的時(shí)候辽幌，運(yùn)行到這里還是會(huì)出現(xiàn)stack2的長度為0增淹，所以要做異常處理
System.out.println("stack1和stack2的長度都為0，不能進(jìn)行pop操作乌企，拋出異常");
return -1;
}
return stack2.pop();
}
}
6. 旋轉(zhuǎn)數(shù)組的最小數(shù)字
把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾虑润，我們稱之為數(shù)組的旋轉(zhuǎn)。 輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)加酵，輸出旋轉(zhuǎn)數(shù)組的最小元素拳喻。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)哭当，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0舞蔽，若數(shù)組大小為0荣病，請(qǐng)返回0。
思路：對(duì)一個(gè)n長度的非減排序數(shù)組進(jìn)行旋轉(zhuǎn)有兩種情況：
- 第一：旋轉(zhuǎn)了1～n-1個(gè)數(shù)字渗柿，會(huì)形成兩個(gè)非減排序的子數(shù)組个盆，如： 4 5 和 1 2 3；它的最小值是在第二個(gè)子數(shù)組的開頭朵栖，同時(shí)颊亮，第一個(gè)子數(shù)組的所有元素都大于或者等于第二個(gè)子數(shù)組，可以利用二分查找法來處理陨溅；
- 第二：旋轉(zhuǎn)了0個(gè)數(shù)字终惑，得到的旋轉(zhuǎn)數(shù)組仍然是原數(shù)組：1 2 3 4 5，最小值就是第一個(gè)元素
注意：第二種情況里面：當(dāng)數(shù)組頭節(jié)點(diǎn)=尾節(jié)點(diǎn)=中間節(jié)點(diǎn)的時(shí)候门扇，無法用二分查找來縮小查找范圍雹有，如：0 1 1 1 1 1 ，旋轉(zhuǎn) 0 1 1 1 1變成：1 0 1 1 1 1,臼寄，只能用順序查找
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (null == array || array.length == 0) {
return 0;
}
int n = array.length - 1;
int first = 0;//二分查找的開頭元素位置索引
int min = first;//用一個(gè)新的元素記錄最小值霸奕，是為了方便如果是第二種情況，就不需要循環(huán)直接返回首節(jié)點(diǎn)
int last = n-1;//二分查找的末尾元素位置索引
int middle = 0;//中間節(jié)點(diǎn)位置索引
while (array[first] >= array[last]) {//當(dāng)數(shù)組的開頭節(jié)點(diǎn)大于等于數(shù)組的末尾節(jié)點(diǎn)時(shí)吉拳，需要進(jìn)行循環(huán)判斷
if (last - first == 1) {//當(dāng)二分查找的結(jié)束索引與開始索引之間相鄰的時(shí)候质帅，說明就找到了最小元素，
//而且最小元素是結(jié)束索引上的元素(因?yàn)閒irst指針總會(huì)指向第一個(gè)子數(shù)組留攒，而第二個(gè)子數(shù)組總會(huì)指向第二個(gè)子數(shù)組)
min = last;
break;
}
middle = first + (last-first)/2;
if (array[first] == array[middle] && array[middle] == array[last]) {//此時(shí)無法用二分查找
// return 煤惩。。炼邀。
//此處省略順序查找的方法
}
if (array[middle] >= array[first]) {//當(dāng)中間元素大于等于二分查找數(shù)組的開頭元素時(shí)魄揉，說明中間元素落在了第一個(gè)子數(shù)組中，最小元素要去后面找
first = middle;
}else if (array[middle] <= array[last]) {//否則當(dāng)中間元素小于等于二分查找數(shù)組的末尾元素時(shí)汤善，說明中間元素落在了第二個(gè)子數(shù)組中什猖，最小元素去前面找
last = middle;
}
}
//如果數(shù)組的第一個(gè)元素小于最后一個(gè)元素，說明：非減排序的數(shù)組的旋轉(zhuǎn)數(shù)組是它本身：1 2 3 4 5红淡，這時(shí)第一個(gè)元素就是最小元素
return array[min];
}
}
