当前位置:网站首页>[sword finger offer] questions 1-5
[sword finger offer] questions 1-5
2022-07-04 22:58:00 【Which bug are you?】
List of articles
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;
}
};
边栏推荐
- Record: how to scroll screenshots of web pages on Microsoft edge in win10 system?
- Unity-VScode-Emmylua配置报错解决
- Prosperity is exhausted, things are right and people are wrong: where should personal webmasters go
- About stack area, heap area, global area, text constant area and program code area
- 页面关闭前,如何发送一个可靠请求
- SPSS installation and activation tutorial (including network disk link)
- 微信公众号解决从自定义菜单进入的缓存问题
- Analog rocker controlled steering gear
- 环境加密技术解析
- Mongodb aggregation operation summary
猜你喜欢
Mongodb aggregation operation summary
攻防世界 MISC 进阶区 Erik-Baleog-and-Olaf
位运算符讲解
共创软硬件协同生态:Graphcore IPU与百度飞桨的“联合提交”亮相MLPerf
Unity修仙手游 | lua动态滑动功能(3种源码具体实现)
The overview and definition of clusters can be seen at a glance
Redis入门完整教程:哈希说明
攻防世界 MISC 进阶区 hit-the-core
【机器学习】手写数字识别
Complete tutorial for getting started with redis: bitmaps
随机推荐
Attack and defense world misc advanced area ditf
Analog rocker controlled steering gear
Redis入门完整教程:Redis Shell
共创软硬件协同生态:Graphcore IPU与百度飞桨的“联合提交”亮相MLPerf
Redis getting started complete tutorial: Geo
9 - class
繁華落盡、物是人非:個人站長該何去何從
Google Earth engine (GEE) -- take modis/006/mcd19a2 as an example to batch download the daily mean, maximum, minimum, standard deviation, statistical analysis of variance and CSV download of daily AOD
【剑指offer】1-5题
Attack and defense world misc advanced zone 2017_ Dating_ in_ Singapore
MYSQL架构——用户权限与管理
小程序vant tab组件解决文字过多显示不全的问题
[machine learning] handwritten digit recognition
【剑指Offer】6-10题
啃下大骨头——排序(二)
Unity-VScode-Emmylua配置报错解决
One of the commonly used technical indicators, reading boll Bollinger line indicators
Breakpoint debugging under vs2019 c release
Prosperity is exhausted, things are right and people are wrong: where should personal webmasters go
微信小程序显示样式知识点总结