Leetcode personal question solution (Sword finger offer3-5) 3 Duplicate number in array, 4 Find in 2D array, 5 Replace spaces

The finger of the sword Offer 03. Repeated numbers in an array

  Answer key ：

Method 1 ： Hash

First , Set up a hash table , Storage int and bool

Scan each number of the array from beginning to end , adopt bool Value is not true Determine whether there is this number in the hash table

Code ：

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;
    }
};

result ：

Method 2 ： Sort

It is also easy to find duplicate values by sorting

Code ：

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;
    }
};

result ：

  The finger of the sword Offer 04. Search in a two-dimensional array

  Answer key ：

Method 1 ： Violent solution

Look one by one, line by line , There's nothing to say about this , Two for loop , Complexity O(NM), It will be slower in time

Code ：

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;
    }
};

result ：

Method 2 ： The starting point

The violence algorithm is from the following table （0,0） Start , If we use the method of judgment ？

When matrix[i][j] < target when , perform i++ perhaps j++, It is not easy to do this step , because i++ Later, it is found that the array element is smaller than the current one , Go back to the previous array and proceed to the following table j++.

But if the starting point is located in the lower left corner of the matrix , It's easy to do .

When matrix[i][j] > target when , perform i-- , Look up , The first i OK, you don't have to read it ;
When matrix[i][j] < target when , perform j++ , Look right , The first j The column can be ignored ;
When matrix[i][j] = target when , return true .

Code ：

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;
    }
};

result ：

  The finger of the sword Offer 05. Replace blank space

Answer key ：

Create a new one string type , take s The data in the and the characters that replace spaces are copied , Avoid data shift to the right .

Traversal string s, Determine whether the character is empty , If it is ,str add %20; If not ,str Add characters i.

Code ：

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

result ：