LeetCode个人题解（剑指offer3-5）3.数组中重复的数字，4.二维数组中的查找，5.替换空格

剑指 Offer 03. 数组中重复的数字

 题解：

方法一：哈希

首先，设置一个哈希表，存储int和bool

从头到尾按顺序扫描数组的每一个数字，通过bool值是否为true判断哈希表中是否有该数字

代码：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int,bool> mymap;
        for(auto i:nums)
        {
            if(mymap[i]) return i;
            mymap[i]=true;
        }
        return -1;
    }
};

结果：

方法二：排序

通过排序也可以很容易找到重复的值

代码：

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for(int i=1;i<nums.size();++i)
        if(nums[i]==nums[i-1])
            return nums[i];
        return -1;
    }
};

结果：

 剑指 Offer 04. 二维数组中的查找

 题解：

方法一：暴力求解

一行一列挨个找，这个没啥好说的，两个for循环，复杂度O(NM)，时间上肯定会慢一些

代码：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0) return false;
        for(int i=0;i<matrix.size();++i)
            for(int j=0;j<matrix[0].size();++j)
                if(matrix[i][j]==target)
                    return true;
        return false;
    }
};

结果：

方法二：起始点

暴力算法是从下表（0，0）开始，如果我们用判断的方法呢？

当 matrix[i][j] < target 时，执行 i++或者j++，在这一步不好做，因为i++之后发现小于当前数组元素，又要回到上一个数组下表进行j++。

但是如果起始点定位在矩阵的左下角，就好做了。

当 matrix[i][j] > target 时，执行 i-- ，向上找，第i行可以不用看了；
当 matrix[i][j] < target 时，执行 j++ ，向右找，第 j 列可以不用看了；
当 matrix[i][j] = target 时，返回 true 。

代码：

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0) return false;
        for(int i=0;i<matrix.size();++i)
            for(int j=0;j<matrix[0].size();++j)
                if(matrix[i][j]==target)
                    return true;
        return false;
    }
};

结果：

 剑指 Offer 05. 替换空格

题解：

新建一个string类型，将s中的数据和替换空格的字符都拷贝过去，避免了数据右移。

遍历字符串s，判断是否为空字符，如果是，str加上%20；如果不是，str加上字符i。

代码：

class Solution {
public:
    string replaceSpace(string s) {
        string str;
        for(auto i:s)
            if(i==' ')
                str+="%20";
            else
                str+=i;
        return str;
    }
};

结果：