一、二维数组的查找
来源：leetcode 剑指offer 04.二维数组的查找
1、题目描述
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2、示例
3、分析
这道题目并不难，如果暴力一点就是遍历查找嘛，这种方式肯定是不可取的。我们还是从这个数组的特点入手，这个二维数组有个特点很重要，每一行从左到右递增，每一列从上到下递增。
那么我们就可以根据这一点设计一种方式，选定一个参考数，比如右上角，等于直接返回false。如果给的target小于这个数，那么右上角这个数的那一列就可以排除，因为列从上到下递增，如果给的target大于这个数，那么这个数所在的那一列就可以排除，这样二维数组被我们不断缩小，每次我们都选取右上角数字，直到找到，或者找不到。
4、代码
bool findNumberIn2DArray(int** matrix, int matrixSize, int* matrixColSize, int target) { //有matrixSize组，每一组*matirColSize个元素 //低效方式--遍历查找 //我们划分半区缩小 //每一行的最后一个是这一行的最大，但也是这一列的最小 //如果我们选定第一行的最后一个数为参考数，如果小于这个数，则剔除它那一列，因为它那一列是递增的 //如果大于这个数，则剔除这一行,每次都选取右上角的数 if(matrix==NULL||matrixSize==0||*matrixColSize==0) return false; int i=0,j=0; while(i<matrixSize&&j<*matrixColSize) { if(target<matrix[i][(*matrixColSize)-j-1]) { //则剔除这一列 j++; } else if(target>matrix[i][*matrixColSize-j-1]) { //剔除这一行 i++; } else { //相等，返回 return true; } } return false; }
这个参数给的不太好懂，我来解释一下，就是matrixSize就是这个二维数组有几个一维数组，对 matrixColSize解引用得到每个一维数组有多少个元素。
二、替换空格
1、题目描述
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
2、示例
3、分析
常见的方式就是我们再开辟一个数组，然后呢，对s数组遍历，遇到空格就输入“%20”，然后它的时间复杂度是O(N),空间复杂度是O(N)。那么现在要求我们将空间复杂度降为O(1),也就是不能额外开辟空间。
我们能不能正着遍历原数组遇到空格就改为“%20”呢？这样显然不行，因为这样会篡改空格后面的字符。所以我们要倒着遍历。
1、遍历扩容原数组
2、双指针，一个tail1指向原数组末尾，一个tail2指向扩容后的数组末尾，当tail1指向的字符为空格时，tail2指向的输入'0'、'2'、'%'.因为我们是倒着遍历，所以要倒着修改，当不是空格时，tail2指向的被赋予tail1指向的字符。
4、代码
char* replaceSpace(char* s) { if(s==NULL) return NULL; //先调整大小 int length=strlen(s); int enlarge=length; for(int i=0;i<length;++i) { if(s[i]==' ') enlarge+=2;//因为空格换成%20加了两个 } char *tmp=(char*)realloc(s,sizeof(char)*(enlarge+1)); if(tmp==NULL) { perror("realloc fail"); exit(-1); } s=tmp; //双指针，一个指针tail1指向原字符串末尾，一个指针tail2指向新扩容的空间末尾 int tail1=length-1,tail2=enlarge-1; s[tail2+1]='\0';//这是个细节 while(tail1>=0) { if(s[tail1]!=' ') { s[tail2--]=s[tail1--]; } else { //遇到空格 s[tail2--]='0'; s[tail2--]='2'; s[tail2--]='%'; tail1--; } } return s; }
注意：
1、先遍历计算出新数组需要的空间，然后扩容，记得扩容的时候给'\0'留一个空间
2、记得先将扩容后的字符数组末尾的下一位赋予'\0'，这是比较细节的地方。
