剑指Offer——二维数组中的查找与空格替换

看书，就是要从书中学到自己欠缺的东西，提升自己。

对于一本书来说，不排除有其客观的质量，但是带给一个人的收获和提升不单单与此相关，更加重要的是，你如何去读这本书，你以一个什么样的心态去读这本书，这就如同你准备一门考试是以要考满分的标准去准备，还是仅仅要求自己及格，两种心态得到的结果必然大不相同。
何老师这本书吸引我的地方就是代码中确实见到很深厚的各种功底，各种规范，而且以一个在公司中有着比较多的经验的开发人员的视角来分析，来作答，让我感触很大。

网上的很多示例代码只是照着文档进行摘抄，不可运行，根本就不是看书的态度，本文对相关的代码进行勘误，添加测试代码等，希望可以帮助你的理解。

二维数组中的查找

题目：

• 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
• 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
  *１　２　８　　９
  *２　４　９　　１２
  *４　７　１０　１３
  *６　８　１１　１５
• 首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，
• 剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，
• 则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
• 运行时间：1 test from find (0 ms total)

二维数组中的查找github地址

#include <vector>
#include <iostream>
#include <gtest/gtest.h>
using namespace std;

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {

        int rows = array.size();
        int columns = array[0].size();
        if (!array.empty() && rows > 0 && columns > 0) {
            int row = 0;
            int col = columns - 1;
            while (row < rows && col >= 0) {
                if (array[row][col] == target) {
                    return true;
                } else if (array[row][col] > target) {
                    col--;
                } else {
                    row++;
                }

            }
            return false;

        } else {
            return false;
        }
    }

};

TEST(find,c2){
    int target = 13;//13,99分别测试
    vector<vector<int> >num =
            {{1,5,10,12,15},{2,8,12,15,17},{4,9,13,16,21},{9,14,18,20,24},{10,18,25,23,30} };

    EXPECT_TRUE((new Solution)->Find(target,num));
}

空格替换

题目：

请实现一个函数，将一个字符串中的空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

问题1：替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换！

问题2：在当前字符串替换，怎么替换才更有效率。

从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下

从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。

实现

思路：从前向后记录‘ ’数目，从后向前替换‘ ’。 重点：从后向前替换的时候的技巧 例如：“we are lucky”

0 1 2 3 4 5 6 7 8 9 10 11

w e a r e l u c k y

可以得知count=2;//空格的个数。 所以在替换的时候7~11的字母要向后移动count×2个位置，

3~5字母要向后移动（count-1）×2个位置。 所以得到 ：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

w e a r e l u c k y

w e a r a r e u c k l u c k y
在替换的时候直接在空格处写入%20了

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

w e a r e l u c k y

w e % 2 0 a r e % 2 0 l u c k y

空格替换github地址

#include <gtest/gtest.h>

using namespace std;

class Solution {
public:
    int replaceSpace(char *str, int length) {

        int spaceNum = 0;
        for (int i = 0; i < length; i++) {
            if (str[i] == ' ') {
                spaceNum++;
            }
        }
        for (int j = length - 1; j >= 0; j--) {
            if (str[j] != ' ') {
                str[j + 2 * spaceNum] = str[j];
            } else {
                spaceNum--;//此处先减除，否则结果错误
                str[j + 2 * spaceNum] = '%';
                str[j + 2 * spaceNum + 1] = '2';
                str[j + 2 * spaceNum + 2] = '0';

            }
        }
        cout << "repalced str is :" << str << endl;
        return spaceNum;
    }
};

TEST(repalce, a1) {
    //本题目前提是预先分配了足够的长度，并且支持space进行扩容，否则程序不会运行成功。
    char buf[30] = {'w', 'e', ' ', 'a', 'r', 'e', ' ', 'l', 'u', 'c', 'k', 'y', '\0'};
    //看打印结果即可
    EXPECT_EQ(2, (new Solution)->replaceSpace(buf, 30));

}