1.在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
【整體思路】
? ? 例如下面的二維數(shù)組就是每行、每列都遞增排序。如果在這個(gè)數(shù)組中查找7，則返回true；如果查找5，由于數(shù)組不含有該數(shù)字，則返回false。
1 ? 2 ? 8 ? 9
2 ? 4 ? 9 ?12
4 ? 7 ?10 ?13
6 ? 8 ?11 ?15
? ? 首先，我們選取右上角的數(shù)字9，由于9大于7，并且9還是第四列的第一個(gè)（也是最小的）數(shù)字，因此7不可能出現(xiàn)在9所在的列。于是我們把這一列從需要考慮的區(qū)域內(nèi)剔除，之后只需要分析剩下的三列(如圖a)。
????在剩下的矩陣中，位于右上角的數(shù)字是8。同樣8大于7，因此8所在的列我們也可以剔除，接下來(lái)只分析剩下的兩列即可（如圖b所示）。
????在由剩余的兩列組成的數(shù)組中，數(shù)字2位于數(shù)組的右上角，2小于7，所以要查找的7可能在2的右邊，也有可能在2的下邊。因?yàn)橹耙呀?jīng)將2右邊的列都剔除了，也就是說(shuō)7不可能出現(xiàn)在2的右邊，因此7只有可能出現(xiàn)在2的下邊。于是把2所在的行剔除，只分析剩下的三行兩列數(shù)字（如圖c所示）。
? ? 在剩下的數(shù)字中，數(shù)字4位于右上角，和前面一樣，我們把數(shù)字4所在的行也剔除，最后剩下兩行兩列數(shù)字（如圖d所示）
? ? 在剩下的兩行兩列數(shù)字中，位于右上角的剛好就是我們要查找的數(shù)字7，于是查找結(jié)束。
? ? 總結(jié)：
????從二維數(shù)組的右上角開始，將數(shù)組元素和target值進(jìn)行比較，有三種情況：①若數(shù)組元素>target值，把數(shù)組的最右邊一列去掉，因?yàn)橛捎谒o數(shù)組的特性target不可能出現(xiàn)在右列；②若數(shù)組元素<target值，把數(shù)組的最上邊一行去掉，因?yàn)橛捎谒^數(shù)組的特性target值不可能出現(xiàn)在上方。③若數(shù)組元素=target值，返回true。
? ??判斷的前提是：row < rows && col >= 0。
? ??所以需要幾個(gè)變量進(jìn)行存儲(chǔ)：①二維數(shù)組的行數(shù)：int rows = array.length；②二維數(shù)組的列數(shù)：int cols = array[0].length;；③當(dāng)前元素所在行int row = 0；④當(dāng)前元素所在列：int col = cols-1;
【代碼】
public class Solution {
????public boolean Find(int target, int [][] array) {
????????int rows = array.length; ? //表示行數(shù)
?????????int cols = array[0].length; ? //表示列數(shù)
?????????int row = 0;?
?????????int col = cols-1;?
?????????while(row=0){
? ? ? ? ? ? if(array[row][col] > target){
? ? ? ? ? ? ? ? col --;
? ? ? ? ? ? }else if(array[row][col] < target){
? ? ? ? ? ? ? ? //else if中的判斷別忘掉寫
? ? ? ? ? ? ? ? row ++;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ?}
????????}
? ? ? ? ?return false;
????}
}
2. 請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy。
【整體思路】
①定義一個(gè)長(zhǎng)度可變的StringBuffer用于存儲(chǔ)新串
②遍歷原字符串。若空格， StringBuffer中增加"%20"，否則，StringBuffer增加原字符串中的第[i]個(gè)字符。
③將StringBuffer轉(zhuǎn)換成字符串，返回。
【代碼】
import java.util.*;
public class Solution {
? ? public String replaceSpace(StringBuffer str) {
? ? StringBuffer newstr = new StringBuffer();
? ? ? ? for(int i=0;i<str.length();i++){
? ? ? ? ? ? if(str.charAt(i)==' '){
? ? ? ? ? ? ? ? newstr.append("%20");
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? newstr.append(str.charAt(i));
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return newstr.toString();
? ? }
}
優(yōu)：時(shí)間復(fù)雜度O(n)，且不用考慮內(nèi)存覆蓋
缺：這種方法空間復(fù)雜度不好，因?yàn)槎x了新的內(nèi)存區(qū)域
