剑指offer编程题

1，在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

第一种思路：直接遍历全部

public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i = 0;i < array.length;i++) {
            for(int j = 0;j < array[0].length;j++) {
                if(array[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

第二种思路：矩阵是有序的，观察矩阵左上角或者右下角的值两边的值可以看出。
二维数组是有序的，从右上角来看，向左数字递减，向下数字递增。
因此从右上角开始查找，
当要查找数字比右上角数字大时，下移；
当要查找数字比右上角数字小时，左移；
如果出了边界，则说明二维数组中不存在该整数。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = 0;
        int column = array[0].length - 1;
        while(column>=0&&row<array.length) {
            if(array[row][column] == target) {
                return true;
            }else if(array[row][column] > target) {
                column--;
            }else if(array[row][column] < target) {
                row++;
            }
        }
        return false;
    }
}

2，请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。