剑指offer（1）

题目描述

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

本题知识点：查找&数组

暴力求解：两层for循环，遍历二维数组，比较所有数据public class solution{

    public boolean Find(int target, int [][] array){
　　　　  if (array.length==0 || array[0].length == 0)
　　　　　　   return false;

        int row = array.length -1;
        int col = array[0].length -1;
        int i=0; int j=0;
     
        for(i = 0; i <= row; ++i)
        {
            for(j = 0; j <= col; ++j)
            {
                //暴力遍历比较
                if(target == array[i][j])
                {
                   return true;
                }
            }
        }

        return false;

    }
}

分治法：有题目可以知道，在二维数组中，比当前元素大的元素都放置在该元素的右边和下边；反之，放置在该元素的左边和上边的元素都比其小。
于是，如果当前元素比目标数字大，那我们只需要找其左方和上方的元素；比目标数字小那我们就需要找当前元素的右方和下方即可。
但是，问题在于，当我们寻找当前元素的右方和下方时，右下角的数字会查找两次。为了消掉这不必要的支出，首位比较元素我们可以选择特殊位置例如四个角的元素。
右下角的数字和左上角的数字都有可能被寻找两次，没有这两个方位的元素是二维数组中右上角和左下角的元素。
以右上角为例，需要寻找更大的元素，则行+1；需要更小的元素，则列-1.
同理左下角，需要寻找更大的元素，则列+1；需要更小的元素，则行-1.
代码以右上角为例。

public class solution{
  public boolean Find(int target, int [][] array){
　　　　  if (array.length==0 || array[0].length == 0)
　　　　　　   return false;

        int row = array.length -1;
        int col = array[0].length -1;
        int i = 0; int j = col; //i行 j列
        while(i>=0 && i <= row && j>=0 && j<= col){
            if(target < array[i][j])
            {
                j--;
            }else if(target > array[i][j]){
                i++;
            }else{
                return true;
            }
        }
        return false;
  }
}

题目描述

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

We Are Happy

We%20Are%20Happy

如果不考虑在原来的字符串上替换的话, 那么我们直接再开一个数组，从前往后依次赋值

遇见空格，就填上%20, 否则就填当前字符。

?这个方法要注意一点，一个空格的位置容不下三个字符，所以同时需要将空格后面的字符串右移两个位置?。

import java.util.*;

public class Solution {
    public String replaceSpace(StringBuffer str, int length) {

        String str1 = str.toString();

        char [] strArray = str1.toCharArray();
        int i = length - 1;

        int len = length;

        for(i = length-1; i >= 0; i--){

        　　if(strArray[i] == ‘ ‘){

　　　　　　len += 2;

　　　　　　for(int j = len-1; j > i+2; j--) {

　　　　　　　　strArray[j] = strArray[j-2]

　　　　　　}

　　　　　　strArray[j--] = ‘0‘;

　　　　　　strArray[j--] = ‘2‘;

　　　　　　strArray[j--] = ‘%‘;

　　　　 }

         }

          return new String(strArray);
    }
}

进阶方法：

上面那个方法太暴力了，有没有什么更好的方法呢？

我们的代码，主要消耗的时间在于，如果有多个空格， 那么每遇到一个空格就进行移位

其实前面的移位是没必要的，因为如果再遇到空格，那么之前的移位全是无用功

因此我们可以考虑先遍历一遍字符串, 计数空格的数目,

我们知道了空格的数目，其实就是知道了替换后字符串的长度，那么只需要进行一次替换就可以了

因为我们的工作变为

• 遍历一遍字符串， 统计字符出现的数目, 计算替换后的字符串长度

• 再遍历一遍字符串，完成替换

代码如下

1import java.util.*;
2public class Solution {
3    public String replaceSpace(StringBuffer str) {
4        String str1 = str.toString();
5        if(str1.equals(""))
6            return str1;
7        char [] strArray = str1.toCharArray();
8        int i =0;
9        int lengthSpace = 0;
10        while(i < strArray.length)
11        {
12            if(strArray[i] == ‘ ‘)
13                lengthSpace++;
14            i++;
15        }
16        int newStrLength = strArray.length + lengthSpace*2;
17        char [] newStr = new char[newStrLength];
18        int j = newStrLength-1;
19        i = strArray.length - 1;
20        while(i >= 0)
21        {
22            if(strArray[i] !=  ‘ ‘)
23            {
24                newStr[j--] = strArray[i--];
25            }else{
26                newStr[j--] = ‘0‘;
27                newStr[j--] = ‘2‘;
28                newStr[j--] = ‘%‘;
29                i--;
30            }
31        }
32        return new String(newStr);
33    }
34}

剑指offer（1）

原文：https://www.cnblogs.com/cherry-BAIL/p/12896471.html