二维数组中的查找&替换空格
1.在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
【整体思路】
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找7，则返回true；如果查找5，由于数组不含有该数字，则返回false。
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
首先，我们选取右上角的数字9，由于9大于7，并且9还是第四列的第一个（也是最小的）数字，因此7不可能出现在9所在的列。于是我们把这一列从需要考虑的区域内剔除，之后只需要分析剩下的三列(如图a)。
在剩下的矩阵中，位于右上角的数字是8。同样8大于7，因此8所在的列我们也可以剔除，接下来只分析剩下的两列即可（如图b所示）。
在由剩余的两列组成的数组中，数字2位于数组的右上角，2小于7，所以要查找的7可能在2的右边，也有可能在2的下边。因为之前已经将2右边的列都剔除了，也就是说7不可能出现在2的右边，因此7只有可能出现在2的下边。于是把2所在的行剔除，只分析剩下的三行两列数字（如图c所示）。
在剩下的数字中，数字4位于右上角，和前面一样，我们把数字4所在的行也剔除，最后剩下两行两列数字（如图d所示）
在剩下的两行两列数字中，位于右上角的刚好就是我们要查找的数字7，于是查找结束。
总结：
从二维数组的右上角开始，将数组元素和target值进行比较，有三种情况：①若数组元素>target值，把数组的最右边一列去掉，因为由于所给数组的特性target不可能出现在右列；②若数组元素<target值，把数组的最上边一行去掉，因为由于所谓数组的特性target值不可能出现在上方。③若数组元素=target值，返回true。
判断的前提是：row < rows && col >= 0。
所以需要几个变量进行存储：①二维数组的行数：int rows = array.length；②二维数组的列数：int cols = array[0].length;；③当前元素所在行int row = 0；④当前元素所在列：int col = cols-1;
【代码】
public class Solution {
public boolean Find(int target, int [][] array) {
int rows = array.length; //表示行数
int cols = array[0].length; //表示列数
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. 请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
【整体思路】
①定义一个长度可变的StringBuffer用于存储新串
②遍历原字符串。若空格， StringBuffer中增加"%20"，否则，StringBuffer增加原字符串中的第[i]个字符。
③将StringBuffer转换成字符串，返回。
【代码】
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();
}
}
优：时间复杂度O(n)，且不用考虑内存覆盖
缺：这种方法空间复杂度不好，因为定义了新的内存区域
