[sword finger offer] questions 1-5

Assignment operator function

• Return self reference , Make it possible to wait .

When overloading the flow operator, you also need to return itself References to , Because continuous input or output is required

• When passing parameters, it is declared as a constant reference

Passing values will call the copy construct ,const References avoid modifying arguments

• Free your own memory

Failure to release yourself when assigning values to others leads to memory leakage （new You need to pay special attention to this point in the assignment of the resulting space ）

• Check whether the incoming parameter and the current instance are the same

Assign values to yourself , There was no big problem , But combined with the previous point , You must have released yourself before the assignment , If the parameter passed in is itself （ What we pass on is quotation ）, It means that the memory resource is gone before the assignment , It may cause the program to crash and so on .

Code

According to the book

CMyString& CMyString::operator=(const CMyString& str)// Parameter passing is often quoted , The return value is also a reference 
{
	if (this != &str)// Judge whether it is equal to itself 
	{
		CMyString strTemp(str);// Build a temporary object to exchange resources 
		
		char* pTemp = strTemp.m_pData;
		strTemp.m_pData = m_pData;
		m_pData = pTemp;
	}
	return *this;
}
//strTemp What you get is old resources , function return Then the stack frame is destroyed , That is to say strTemp With the original resources released 

Summary

Realization Singleton Pattern

There are three ways of writing , Corresponding to each other, it can work in a single thread , Multithreading can work but is inefficient , Multithreading can work with high efficiency .

Single thread

Before creating an instance in singleton mode, you should shield all other methods of creating instances fall , For example, put the structure 、 Copy constructor private , Disable assignment overloading （C++11delete keyword ）

class Singleton
{
public:
	static Singleton* GetInstance()
	{
		if (instance == nullptr)
		{
			return new Singleton();
		}
	}
private:
    // The methods of creating instances are all set to private , Only one interface is left 
    ... Disable all construction methods 
	static Singleton* instance;
};
Singleton* Singleton::instance = nullptr;

Multithreading + Inefficient

The methods of creating instances are all set to private , Only one interface is left

class Singleton
{
public:
	static Singleton* GetInstance()
	{
		_mtx.lock();
		if (_instance == nullptr)
		{
			_instance=new Singleton();
		}
		_mtx.unlock();
        return _instance;
	}
private:
    ... Disable all construction methods 
	static mutex _mtx;
	static Singleton* _instance;
};
Singleton* Singleton::_instance = nullptr;

Locking costs a lot , Locking before each inspection leads to low efficiency .

Multithreading + Efficient

Double check writing

class Singleton
{
    
public:
	static Singleton* GetInstance()
	{
    
		if (_instance==nullptr)
		{
    
			_mtx.lock();
			if (_instance == nullptr)
			{
    
				_instance=new Singleton();
			}
			_mtx.unlock();
			return _instance;
		}
		
	}
private:
    ... Disable all methods 
	static mutex _mtx;
	static Singleton* _instance;
};
Singleton* Singleton::_instance = nullptr;

Repeated numbers in an array

The finger of the sword Offer 03. Repeated numbers in an array - Power button （LeetCode）

The main idea of the topic ： Find an arbitrary repeated number from a pile of numbers

Hashtable

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

Indexes

You can treat every position of the array as empty , Then find a number and fill it in , For example, the subscript is 1 The location of is 1 Go fill in .

Go through each number , Check this number , For example, whether to fill in this number , If this number appears after filling, it means that it is repeated , Fill in the right place without filling .

This method is a clever solution , Using the idea of indexing , That is, a position can only correspond to one value , The second occurrence is repetition .

The title is also modified in the book ： What to do without moving the array ？ Two points + Count the number of times to determine the interval of the repeated number .

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
       int i=0;
       while(i<nums.size())
       {
           if(i==nums[i])
           {
               i++;
               continue;
           }
           if(nums[i]!=nums[nums[i]])
           {
               swap(nums[i],nums[nums[i]]);
               continue;// You must quit after the exchange 
           }
           return nums[i];
       }
        return -1;
    }
};

Search in a two-dimensional array

The finger of the sword Offer 04. Search in a two-dimensional array - Power button （LeetCode）

The main idea of the topic ： Each row is incremented from left to right , Each column is incremented from top to bottom .

It's a bit like finding rules , To find the number in the upper right corner . Remember that the number we are looking for is target, Record the number in the upper right corner as right-up.

target>right-up, Get rid of right-up This number is on this line . because right-up Is the maximum number of current rows ,target More than that , It shows that there is no number we need in this line .

target<right-up, Get rid of right-up In this column , Because this number is the smallest tree in its column ,target Smaller than this number , It means that there are no figures we need in this column .

target==right-up. Go straight back to true

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

Replace blank space

The finger of the sword Offer 05. Replace blank space - Power button （LeetCode）

The main idea of the topic ： Replace the space with “%20”

O(n^2) Surely not , Violent movement …

grace , Never obsolete – Green steel shadow

Here's a O(n) Methods

It takes a lot of length to replace a space 2, Count how many spaces there are , You know the length of the replaced string . Then double pointer , Two pointers scan from back to front , Write them down as end1( The initial point is the last position of the old string ),end2( The initial point is to the last position of the new string ),end1 Scan to non space characters ,end2 Copy this character at the position pointed to ,end1 Scan to the space character end2 The pointing position increases from back to front 02% that will do .

class Solution {
    
public:
    string replaceSpace(string s) {
    
        int cnt=0;
        int sz=s.size();
        for(int i=0;i<sz;i++)
        {
    
            if(s[i]==' ')
            {
    
                cnt++;
            }
        }
        int newSize=sz+cnt*2;
        s.resize(newSize+1);
        int end2=newSize-1;
        int end1=sz-1;
        while(end1>=0)
        {
    
            if(s[end1]==' ')
            {
    
                s[end2]='0';end2--;
                s[end2]='2';end2--;
                s[end2]='%';end2--;end1--;
            }
            else
            {
    
                s[end2]=s[end1];
                end2--;
                end1--;
            }
        }
        return s;
    }
};