【剑指offer】1-5题

赋值运算符函数

• 返回自身引用，使得可以连等。

重载流运算符时也需要返回自身 的引用，因为需要连续输入或输出

• 传参时声明为常量引用

传值会调用拷贝构造，const引用避免修改实参

• 释放自身内存

赋值给别人的时候没释放自己导致内存泄漏（new出来的空间赋值需要格外注意这点）

• 检查传入参数和当前实例是不是同一个

自身给自身赋值，本来是没大问题的，可是结合前面点，你在赋值前肯定已经释放了自己，如果传入的参数是自己（我们传的是引用），说明在进行赋值前这块内存的资源就已经没了，可能导致程序崩了啊之类的。

代码

照着书上敲的

CMyString& CMyString::operator=(const CMyString& str)//传参是常引用，返回值也是引用
{
	if (this != &str)//判断与自身是否相等
	{
		CMyString strTemp(str);//构建一个临时对象用于交换资源
		
		char* pTemp = strTemp.m_pData;
		strTemp.m_pData = m_pData;
		m_pData = pTemp;
	}
	return *this;
}
//strTemp拿到的是旧的资源，函数return后这个栈帧就被销毁了，也即strTemp带着原来的资源被释放了

小结

实现Singleton模式

有三种写法，分别对应可以在单线程下工作，多线程下可以工作但是效率低，多线程下可以工作且效率高。

单线程

单例模式创建实例前应该把别的创建实例的办法全部屏蔽 掉，比如把构造、拷贝构造函数私有，把赋值重载禁用（C++11delete关键字）

class Singleton
{
public:
	static Singleton* GetInstance()
	{
		if (instance == nullptr)
		{
			return new Singleton();
		}
	}
private:
    //创建实例的方法全设为私有，只留一个接口
    ...禁用所有构造方法
	static Singleton* instance;
};
Singleton* Singleton::instance = nullptr;

多线程+低效

创建实例的方法全设为私有，只留一个接口

class Singleton
{
public:
	static Singleton* GetInstance()
	{
		_mtx.lock();
		if (_instance == nullptr)
		{
			_instance=new Singleton();
		}
		_mtx.unlock();
        return _instance;
	}
private:
    ...禁用所有构造方法
	static mutex _mtx;
	static Singleton* _instance;
};
Singleton* Singleton::_instance = nullptr;

加锁的开销是很大的，在每次检查之前都进行加锁导致效率低。

多线程+高效

双检查写法

class Singleton
{
    
public:
	static Singleton* GetInstance()
	{
    
		if (_instance==nullptr)
		{
    
			_mtx.lock();
			if (_instance == nullptr)
			{
    
				_instance=new Singleton();
			}
			_mtx.unlock();
			return _instance;
		}
		
	}
private:
    ...禁用所有方法
	static mutex _mtx;
	static Singleton* _instance;
};
Singleton* Singleton::_instance = nullptr;

数组中重复的数字

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）

题目大意：从一堆数字中找出一个任意的重复了的数字

哈希表

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

索引

可以把数组的每个位置都看成空的，然后去找一个数字去填他，比如下标为1的位置用1去填。

遍历每个数字，对于这个数字去进行检查，比如这个数字填没填，填好后还出现这个数字就说明重复了，没填就填到合适的位置去。

这种办法是巧解，利用索引的思想，即一个位置只能对应一个值，第二次出现就是重复。

书上还将题目进行了变形：不移动数组该怎么做？二分+统计次数确定重复的数所在的区间。

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;//交换完必须退出去
           }
           return nums[i];
       }
        return -1;
    }
};

二维数组中的查找

剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode）

题目大意：每一行从左往右递增，每一列从上往下递增。

有点像找规律这题，要找到右上角那个数字。记我们要查找的数字为target，记右上角的数字为right-up.

target>right-up，排除掉right-up这个数所在的这一行。因为right-up是当前行最大的数，target比这个数还大，说明这一行没有我们需要的数字。

target<right-up,排除掉right-up所在的这一列，因为这个数是它所在列最小的树，target比这个数还小，说明这一列没有我们需要的数字。

target==right-up.直接返回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;
    }
};

替换空格

剑指 Offer 05. 替换空格 - 力扣（LeetCode）

题目大意：把空格换成“%20”

O(n^2)肯定是不行的，暴力移动…

优雅，永不过时–青钢影

下面给一个O(n)的方法

替换一个空格需要长度多2，统计有多少个空格，就知道替换后的字符串的长度。然后双指针，两个指针从后往前扫描，分别记为end1(初始指向旧字符串的最后一个位置)，end2(初始指向新字符串的最后一个位置)，end1扫描到非空格字符，end2指向的位置拷贝这个字符即可，end1扫描到空格字符那end2指向的位置就从后往前增加02%即可。

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